题意：有n个男生和n个女生，玩结婚游戏，由女生选择男生；女生可以选择不会和她吵架的男生以及不会和她闺蜜吵架的男生，闺蜜的闺蜜也是闺蜜。问你最多可以进行多少轮，每一轮每个女生只能选择一个之前她没选过的男生。
思路：显然最少进行0轮，最多进行n轮，所以我们可以对轮数进行二分；源点到女生连一条容量为轮数的边，女生到她可选择的男生之间连一条容量为1的边，男生到汇点同样连一条容量为轮数的边，然后跑最大流判断是否满流。找到最大的轮数。要注意的是，每次跑最大流的时候都要重新建图。至于闺蜜的问题用一个并查集就可以了。
代码：
#include<stdio.h>
#include<string.h>
#define min(x,y) (x)<(y)?(x):(y)
const int N=,M=N*N,INF=0x3f3f3f3f;
int n,l,r,s,t;
int c[N][N],tmpc[N][N];
int fa[N];
int h[N],gap[N];
int find(int a)
{
if(fa[a]!=a) return fa[a]=find(fa[a]);
return a;
}
void union_(int a,int b)
{
a=find(a),b=find(b);
if(a!=b) fa[a]=b;
}
int dfs(int u,int flow)
{
if(u==t) return flow;
int a,v,cc=flow,minh=t;
for(v=;v<=t;v++)
{
if(c[u][v])
{
if(h[v]==h[u]-)
{
a=min(c[u][v],flow);
a=dfs(v,a);
c[u][v]-=a;
cc-=a;
c[v][u]+=a;
if(h[s]>t) return flow-cc;
if(!cc) break;
}
minh=min(minh,h[v]);
}
}
if(cc==flow)
{
if(--gap[h[u]]==) h[s]=t+;
++gap[h[u]=minh+];
}
return flow-cc;
}
int isap()
{
memset(gap,,sizeof(gap));
memset(h,,sizeof(h));
int ans=;gap[]=t+;
while(h[s]<=t)
ans+=dfs(s,INF);
return ans;
}
int bin()
{
int l=,r=n,mid,i,j,ans;
while(l<=r)
{
mid=(l+r)>>;
for(i=;i<=n;i++)
c[s][i]=mid,c[i+n][t]=mid;
for(i=;i<=n;i++)
for(j=n+;j<=n+n;j++)
c[i][j]=tmpc[i][j];
if(mid*n==isap())
{
ans=mid;
l=mid+;
}
else
r=mid-;
}
return ans;
}
int main()
{
int T,m,k,i,j,x,y;
scanf("%d",&T);
while(T--)
{
scanf("%d%d%d",&n,&m,&k);
memset(c,,sizeof(c));
s=,t=n*+;
for(i=;i<=n;i++)
fa[i]=i;
while(m--)
{
scanf("%d%d",&x,&y);
c[x][y+n]=;
}
while(k--)
{
scanf("%d%d",&x,&y);
union_(x,y);
for(i=;i<=n;i++)
{
if(find(i)==find(x))
{
for(j=n+;j<=n+n;j++)
{
if(c[i][j]&&!c[x][j])
c[x][j]=;
}
}
if(find(i)==find(y))
{
for(j=n+;j<=n+n;j++)
{
if(c[i][j]&&!c[y][j])
c[y][j]=;
}
}
}
}
for(i=;i<=n;i++) for(j=n+;j<=n+n;j++) tmpc[i][j]=c[i][j];
printf("%d\n",bin());
}
return ;
}