hdu3081 Marriage Match II

新年第一篇，又花了一早上，真是蠢啊!
二分+网络流
之前对于讨论哪些人是朋友的时候复杂度过高
直接n3的暴力虽然看起来复杂度高，其实并不是每次都成立

#include<bits/stdc++.h>
using namespace std;
const int N = 205;
const int INF = 0x3f3f3f3f;
#define sz(X) ((int)X.size())

int A[N], B[N];
int mp[N][N];
int f[N];
int find(int x) { return f[x] == x? x : f[x] = find(f[x]); }
/***********Dinic*********/
int s, t;
struct Edge {
    int from, to, cap, flow, nx;
    Edge(int a=0, int b=0, int c=0, int d=0, int e=0):from(a), to(b), cap(c), flow(d),nx(e){}
}E[N*N];
int head[N], tot;
bool vis[N];
int d[N];
int cur[N];
void init() {
    tot = 0; memset(head,-1,sizeof(head));
}
void add(int from, int to, int cap) {
    E[tot] = Edge(from,to,cap,0,head[from]); head[from] = tot++;
    E[tot] = Edge(to,from,0,0,head[to]); head[to] = tot++;
}
bool bfs() {
    memset(vis, 0, sizeof(vis));
    queue<int> Q;
    Q.push(s);
    d[s] = 0;
    vis[s] = 1;
    while(!Q.empty()) {
        int x = Q.front(); Q.pop();
        for(int i = head[x]; ~i; i = E[i].nx) {
            Edge& e = E[i];
            if(!vis[e.to] && e.cap > e.flow) {
                vis[e.to] = 1;
                d[e.to] = d[x] + 1;
                Q.push(e.to);
            }
        }
    }
    return vis[t];
}
int dfs(int x, int a) {
    if(x == t || a == 0) return a;
    int flow = 0, f;
    for(int& i = cur[x]; ~i; i = E[i].nx) {
        Edge& e = E[i];
        if(d[x]+1 == d[e.to] && (f = dfs(e.to, min(a, e.cap-e.flow))) > 0) {
            e.flow += f;
            E[i^1].flow -= f;
            flow += f;
            a -= f; if(a == 0) break;
        }
    }
    return flow;
}
int Maxflow(int start, int ed) {
    s = start; t = ed;
    int flow = 0;
    while(bfs()) {
        for(int i = s; i <= t; ++i) cur[i] = head[i];
        flow += dfs(s, INF);
    }
    return flow;
}

int main() {
    int n,m,l;
    int _; scanf("%d",&_);
    while(_--) {
        memset(mp,0,sizeof(mp));
        scanf("%d %d %d",&n,&m,&l);
        for(int i = 0; i <= n; ++i) f[i] = i;
        for(int i = 0; i < m; ++i) {
            int a, b; scanf("%d %d",&a,&b);
            mp[a][b] = 1;
        }
        for(int i = 0; i < l; ++i) {
            int c,d; scanf("%d %d",&c,&d);
            int t1 = find(c); int t2 = find(d);
            if(t1 != t2) f[t1] = t2;
        }
        for(int i = 1; i <= n; ++i) {
            for(int j = 1; j <= n; ++j) {
                if(find(i) == find(j)) {
                    for(int k = 1; k <= n; ++k) {
                        if(mp[i][k]) mp[j][k] = 1;
                    }
                }
            }
        }
        int s = 0; int t = 2*n+1;

        int l = 0; int r = n; int res;
        while(l <= r) {
            int mid = (l + r)>>1;
            init();
            for(int i = 1; i <= n; ++i) add(s,i,mid);
            for(int i = 1; i <= n; ++i) add(i+n,t,mid);
            for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= n; ++j) {
                if(mp[i][j]) {
                    add(i,j+n, 1);
                }
            }
            int tt = Maxflow(s, t);
            if(tt != mid*n) r = mid-1;
            else { l = mid+1; res = mid; }
        }
        printf("%d
",res);

    }
    return 0;
}