题意:N个boy和N个girl,每个女孩可以和与自己交友集合中的男生配对子;如果两个女孩是朋友,则她们可以和对方交友集合中的男生配对子;如果女生a和女生b是朋友,b和c是朋友,则a和c也是朋友.每一轮配对结束后(每个人都找到自己的对象),在开始新的一轮配对.求最大能进行多少轮完整的游戏.
分析:用最大流解决该问题,若假设能进行k轮游戏,则由源点向每个女生建一条容量为k的边,每个男生也向汇点建一条容量为k的边,对于每个女生,向其能够配对的男生连一条容量为1的边.最后跑出最大流若为n*k则表示游戏能够进行k轮.
确定了这点之后,二分搜答案.
还有一个问题就是,如何通过伙伴关系来确定女生能配对的所有男生? 有并查集和传递闭包两种方法,复杂度是差不多.属于一个集合中的女生,则她们的匹配对象集合就是所有人对象集合的并集.
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<stack>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN=10010;//点数的最大值
const int MAXM=400010;//边数的最大值
#define captype int
struct SAP_MaxFlow{
struct EDGE{
int to,next;
captype cap;
}edg[MAXM];
int eid,head[MAXN];
int gap[MAXN];
int dis[MAXN];
int cur[MAXN];
int pre[MAXN];
void init(){
eid=0;
memset(head,-1,sizeof(head));
}
void AddEdge(int u,int v,captype c,captype rc=0){
edg[eid].to=v; edg[eid].next=head[u];
edg[eid].cap=c; head[u]=eid++;
edg[eid].to=u; edg[eid].next=head[v];
edg[eid].cap=rc; head[v]=eid++;
}
captype maxFlow_sap(int sNode,int eNode, int n){//n是包括源点和汇点的总点个数，这个一定要注意
memset(gap,0,sizeof(gap));
memset(dis,0,sizeof(dis));
memcpy(cur,head,sizeof(head));
pre[sNode] = -1;
gap[0]=n;
captype ans=0;
int u=sNode;
while(dis[sNode]<n){
if(u==eNode){
captype Min=INF ;
int inser;
for(int i=pre[u]; i!=-1; i=pre[edg[i^1].to])
if(Min>edg[i].cap){
Min=edg[i].cap;
inser=i;
}
for(int i=pre[u]; i!=-1; i=pre[edg[i^1].to]){
edg[i].cap-=Min;
edg[i^1].cap+=Min;
}
ans+=Min;
u=edg[inser^1].to;
continue;
}
bool flag = false;
int v;
for(int i=cur[u]; i!=-1; i=edg[i].next){
v=edg[i].to;
if(edg[i].cap>0 && dis[u]==dis[v]+1){
flag=true;
cur[u]=pre[v]=i;
break;
}
}
if(flag){
u=v;
continue;
}
int Mind= n;
for(int i=head[u]; i!=-1; i=edg[i].next)
if(edg[i].cap>0 && Mind>dis[edg[i].to]){
Mind=dis[edg[i].to];
cur[u]=i;
}
gap[dis[u]]--;
if(gap[dis[u]]==0) return ans;
dis[u]=Mind+1;
gap[dis[u]]++;
if(u!=sNode) u=edg[pre[u]^1].to; //退一条边
}
return ans;
}
}F;
bool G[205][205];
int fa[105];
int Find(int x){
return fa[x]==-1? x:fa[x] = Find(fa[x]);
}
void Union(int x,int y)
{
x = Find(x), y = Find(y);
if(x!=y) fa[x] = y;
}
bool check(int n,int limit){
F.init();
int st =0,ed = 2*n+1;
for(int i=1;i<=n;++i){
for(int j = n+1;j<=2*n;++j){
if(G[i][j]) F.AddEdge(i,j,1);
}
}
for(int i=1;i<=n;++i) F.AddEdge(st,i,limit);
for(int i=n+1;i<=2*n;++i) F.AddEdge(i,ed,limit);
int res = F.maxFlow_sap(st,ed,2*n+2);
return res == n*limit;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
int T; scanf("%d",&T);
int n,m,f,u,v,tmp;
while(T--){
scanf("%d %d %d",&n,&m,&f);
memset(G,0,sizeof(G));
memset(fa,-1,sizeof(fa));
for(int i =1;i<=m;++i){
scanf("%d %d",&u,&v);
G[u][v+n] = 1;
}
for(int i=1;i<=f;++i){
scanf("%d %d",&u,&v);
Union(u,v);
}
for(int i=1;i<=n;++i){
for(int j=i+1;j<=n;++j){
if(Find(i)==Find(j)){
for(int k=n+1;k<=2*n;++k){
G[i][k] = G[j][k] = (G[i][k] || G[j][k]);
}
}
}
}
int L = 0,R =100,mid,ans=0;
while(L<=R){
mid =(L+R)>>1;
if(check(n,mid)){
ans = mid;
L= mid+1;
}
else {
R= mid-1;
}
}
printf("%d
",ans);
}
return 0;
}