新年第一篇，又花了一早上，真是蠢啊!

二分+网络流

之前对于讨论哪些人是朋友的时候复杂度过高

直接n3的暴力虽然看起来复杂度高，其实并不是每次都成立

#include
     
      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
      
        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\n",res);    }    return 0;}