二分搜索最大容量即为答案。详见代码：/********************************************************* 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;}elser=mid-1;}printf("%d\n",ans);}return 0;}
，每年的情人节圣诞节除夕，也和他共度。甚至连吵架也是重复的，
