学步园

题意：
n个男孩n个女孩，女孩选男孩，每个女孩都要选到不同的人
k对女孩有相同选择标准，
女孩每轮都选择没选过的男孩，
问总共能选几轮。
思路：
女孩1..n，男孩n+1..2*n编号
由女孩到男孩建容量为1的边
起点st=2*n+1，到1..n建边；
n+1..2*n到终点ed=2*n+2建边
二分搜索最大容量即为答案。详见代码：
/*********************************************************
  file name: hdu3081.cpp
  author : kereo
  create time:  2015年02月17日 星期二 22时23分44秒
*********************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<stack>
#include<cmath>
#include<string>
#include<algorithm>
using namespace std;
typedef long long ll;
const int sigma_size=26;
const int N=200+50;
const int MAXN=100000+50;
const int inf=0x3fffffff;
const double eps=1e-8;
const int mod=1000000000+7;
#define L(x) (x<<1)
#define R(x) (x<<1|1)
#define PII pair<int, int>
#define mk(x,y) make_pair((x),(y))
int n,m,k,edge_cnt,top;
int fa[N];
int head[N],que[N],s[N],cur[N],gap[N],dep[N];
struct Edge{
    int v,cap,flow,next;
}edge[MAXN];
PII mp[MAXN];
void init(){
    edge_cnt=top=0;
    memset(head,-1,sizeof(head));
}
void addedge(int u,int v,int cap){
    edge[edge_cnt].v=v; edge[edge_cnt].cap=cap; 
    edge[edge_cnt].flow=0; edge[edge_cnt].next=head[u]; head[u]=edge_cnt++;
    edge[edge_cnt].v=u; edge[edge_cnt].cap=0;
    edge[edge_cnt].flow=0; edge[edge_cnt].next=head[v]; head[v]=edge_cnt++;
}
int findset(int x){
    return fa[x] == x ?  x : fa[x]=findset(fa[x]);
}
void Union(int x,int y){
    int fx=findset(x);
    int fy=findset(y);
    if(fx == fy)
        return ;
    fa[fx]=fy;
}
void bfs(int st,int ed){
    int front=0,rear=0;
    memset(gap,0,sizeof(gap));
    memset(dep,-1,sizeof(dep));
    dep[ed]=0; gap[0]=1; que[rear++]=ed;
    while(front!=rear){
        int u=que[front++];
        for(int i=head[u];i!=-1;i=edge[i].next){
            int v=edge[i].v;
            if(dep[v]!=-1)
                continue;
            dep[v]=dep[u]+1; gap[dep[v]]++; que[rear++]=v;
        }
    }
}
int isap(int st,int ed){
    bfs(st,ed);
    memcpy(cur,head,sizeof(head));
    int ans=0,u=st;
    while(dep[st]<2*n+2){
        if(u == ed){
            int Min=inf,inser;
            for(int i=0;i<top;i++){
                if(edge[s[i]].cap-edge[s[i]].flow<Min){
                    Min=edge[s[i]].cap-edge[s[i]].flow;
                    inser=i;
                }
            }
            for(int i=0;i<top;i++)
                edge[s[i]].flow+=Min,edge[s[i]^1].flow-=Min;
            ans+=Min; top=inser;
            u=edge[s[top]^1].v;
            continue;
        }
        int flag=0,v;
        for(int i=cur[u];i!=-1;i=edge[i].next){
            v=edge[i].v;
            if(edge[i].cap>edge[i].flow && dep[v]+1 == dep[u]){
                flag=1; cur[u]=i;
                break;
            }
        }
        if(flag){
            s[top++]=cur[u]; u=v;
            continue;
        }
        int d=2*n+2;
        for(int i=head[u];i!=-1;i=edge[i].next){
            int v=edge[i].v;
            if(edge[i].cap>edge[i].flow && dep[v]<d){
                cur[u]=i,d=dep[v];
            }
        }
        gap[dep[u]]--;
        if(!gap[dep[u]])
            return ans;
        dep[u]=d+1; gap[dep[u]]++;
        if(u!=st)
            u=edge[s[--top]^1].v;
    }
    return ans;
}
void Graph(int cap){
    init();
    int Map[N][N];
    memset(Map,0,sizeof(Map));
    for(int i=1;i<=n;i++){
        addedge(0,i,cap);
        addedge(i+n,2*n+1,cap);
    }
    for(int i=1;i<=m;i++){
        int u=mp[i].first;
        int v=mp[i].second;
        for(int j=1;j<=n;j++){
            if(findset(u) == findset(j)){
                if(Map[j][v])
                    continue;
                Map[j][v]=1;
                addedge(j,n+v,1);
            }
        }
    }
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        init();
        scanf("%d%d%d",&n,&m,&k);
        for(int i=1;i<=n;i++)
            fa[i]=i;
        for(int i=1;i<=m;i++){
            int u,v;
            scanf("%d%d",&u,&v);
            mp[i]=mk(u,v);
        }
        for(int i=0;i<k;i++){
            int u,v;
            scanf("%d%d",&u,&v);
            Union(u,v);
        }
        int ans=0,l=0,r=n;
        while(l<=r){
            int mid=(l+r)>>1;
            Graph(mid);
            int res=isap(0,2*n+1);
            if(res>=n*mid){
                ans=mid;
                l=mid+1;
            }
            else
                r=mid-1;
        }
        printf("%d\n",ans);
    }
	return 0;
}