hust 1024 dance party

 

dance party

Time Limit: 2 Sec   Memory Limit: 128 MB
Submissions: 324   Solved: 112

Description

You are organizing a dance party. The party will be attended by n boys and n girls. There will be several rounds of dancing.
In each round, you divide the guests into n dancing pairs. Each guest must be in exactly one pair, and each pair must contain one boy and one girl. Each boy must dance with a different girl in every round. Some boys and girls like each other and some do not. During the party, each boy agrees to dance with at most k girls he doesn't like. Similarly, each girl agrees to dance with at most k boys she doesn't like. 
You are given the each pairs of boys and girls who agree to dance with each other .Find out the maximum number of rounds you can organize.

Input

The first line contains a integer t,which means there are t cases followed.
For each case,the first line contain three integer n,m,k ,which means there are n boys and n girls attending the party and m pairs of boys and girls who agree to dance with each other,and each boy or girl agrees to dance with at most k girls or boys he or she doesn't like.At last ,there are m lines with two integers a,b which means boy a and girl b agree to dance with each other.
（0<n<=100,0<m<=n*n,0<k<100,0<a,b<=n）

Output

The output cotains only one integer which means the maximum number of rounds you can organize.

Sample Input

2
2 4 0
1 1
2 2
2 1
1 2
3 7 0
1 1
1 2
1 3
2 1
2 2
3 1
3 3

Sample Output

2
2

HINT

 

Source

lshmouse

[ Submit][ Status][ Discuss]

 

HOME Back

 

 

/* 好久没真正做网络流，水了 刚开始竟没想到用二分来空间完美匹配 WA了一次后，用二分来控制完美匹配，即可 */ #include<cstdio> #include<cstring> const int N=500; const int M=50000; const int inf=0x7fffffff; int head[N]; bool map[101][101]; struct Edge { int v,next,w; } edge[M]; int cnt,n,s,t,m,k; int tt; void addedge(int u,int v,int w) { edge[cnt].v=v; edge[cnt].w=w; edge[cnt].next=head[u]; head[u]=cnt++; edge[cnt].v=u; edge[cnt].w=0; edge[cnt].next=head[v]; head[v]=cnt++; } int sap() { int pre[N],cur[N],dis[N],gap[N]; int flow=0,aug=inf,u; bool flag; for(int i=0; i<n; i++) { cur[i]=head[i]; gap[i]=dis[i]=0; } gap[s]=n; u=pre[s]=s; while(dis[s]<n) { flag=0; for(int &j=cur[u]; j!=-1; j=edge[j].next) { int v=edge[j].v; if(edge[j].w>0&&dis[u]==dis[v]+1) { flag=1; if(edge[j].w<aug) aug=edge[j].w; pre[v]=u; u=v; if(u==t) { flow+=aug; while(u!=s) { u=pre[u]; edge[cur[u]].w-=aug; edge[cur[u]^1].w+=aug; } aug=inf; } break; } } if(flag) continue; int mindis=n; for(int j=head[u]; j!=-1; j=edge[j].next) { int v=edge[j].v; if(edge[j].w>0&&dis[v]<mindis) { mindis=dis[v]; cur[u]=j; } } if((--gap[dis[u]])==0) break; gap[dis[u]=mindis+1]++; u=pre[u]; } return flow; } bool solve(int mid) { n=tt; s=0; t=n*4+1; cnt=0; memset(head,-1,sizeof(head)); for(int i=1; i<=n; i++) { addedge(s,i,mid); addedge(i+3*n,t,mid); } for(int i=1; i<=n; ++i) { addedge(i,i+n,k); addedge(i+2*n,i+3*n,k); } for(int i=1; i<=n; ++i) for(int j=1; j<=n; ++j) { addedge(i+n,j+2*n,1); if(map[i][j]==1) addedge(i,j+3*n,1); } n=4*n+2; if(sap()==mid*tt) return true; else return false; } int main() { int T; int a,b; scanf("%d",&T); while(T--) { memset(map,0,sizeof(map)); scanf("%d%d%d",&n,&m,&k); for(int i=1;i<=m;i++) { scanf("%d%d",&a,&b); map[a][b]=1; } int front=0,rear=n; int ans=front; tt=n; while(front<=rear) { int mid=(front+rear)>>1; if(solve(mid)) { ans=mid; front=mid+1; } else rear=mid-1; } printf("%d/n",ans); } return 0; }