6102번: Earthquake Damage 2 - 최적화 필요

https://www.acmicpc.net/problem/6102


참고: http://contest.usaco.org/TESTDATA/MAR09.damage2.htm

#include<stdio.h>
#include<vector>
using namespace std;
const int MAX_P = 3000;
vector<pair<int, bool>> adj[MAX_P * 2 + 1];
int p, c, n, res;
bool ck[MAX_P * 2 + 1], sink[MAX_P * 2 + 1];
bool dfs(int h) {
    if (sink[h]) return true;
    ck[h] = true;
    for (auto &t : adj[h]) {
        if (!ck[t.first] && t.second&&dfs(t.first)) {
            t.second = false;
            adj[t.first].push_back({ h,true });
            return true;
        }
    }
    return false;
}
int main() {
    scanf("%d %d %d", &p, &c, &n);
    for (int i = 0, x, y; i < c; i++) {
        scanf("%d %d", &x, &y);
        adj[x + p].push_back({ y,true });
        adj[y + p].push_back({ x,true });
    }
    for (int i = 1; i <= p; i++) adj[i].push_back({ i + p,true });
    for (int i = 0, x; i < n; i++) scanf("%d", &x), sink[x] = true;
    while (dfs(p + 1)) fill(ck, ck + 2 * p + 1, false), res++;
    printf("%d", res);
    return 0;
}