有N个男孩，N个女孩。每个女孩可以选择一个没有跟他吵过架的男孩结婚。如果女孩X和女孩Y是朋友，且Y没有和男孩Z吵过架，女孩X同样可以选择男孩Z和自己结婚。另外，如果A和B是朋友，B和C是朋友，那么A和C也必定是朋友。每一轮中，每个女孩还可以额外选择K个自己原本不打算和她配对的男孩配对。一旦所有的女孩都找到了男友，那么他们就可以开始一轮新的游戏了，在每一轮新的游戏中，他们将使用相同的规则进行游戏，但是所有的女孩都不会选择之前选择过的男友了。问他们最多可以进行几轮游戏。
跟HDU 3081基本一样，就是多了一个条件：每一轮中，每个女孩还可以额外选择K个自己原本不打算和她配对的男孩配对。
这里的处理是把每个女孩i拆成两个点，在这两个点之间连一条边(i,i',K),如果女孩i喜欢男孩j，就从i连一条边(i,j,1)，如果不喜欢，就从i'连一条边(i',j,1)，然后的处理跟原来的完全一样。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #define INF 1<<30 6 #define maxn 1000 7 #define maxm 300000 8 using namespace std; 9 10 int v[maxm],next[maxm],w[maxm]; 11 int first[maxn],d[maxn],work[maxn],q[maxn]; 12 int e,S,T; 13 int n,m,K,f; 14 int like[256][256],map[256][256]; 15 void init(){ 16 e = 0; 17 memset(first,-1,sizeof(first)); 18 } 19 20 void add_edge(int a,int b,int c){ 21 //printf("add:%d to %d,cap = %d ",a,b,c); 22 v[e] = b;next[e] = first[a];w[e] = c;first[a] = e++; 23 v[e] = a;next[e] = first[b];w[e] = 0;first[b] = e++; 24 } 25 26 int bfs(){ 27 int rear = 0; 28 memset(d,-1,sizeof(d)); 29 d[S] = 0;q[rear++] = S; 30 for(int i = 0;i < rear;i++){ 31 for(int j = first[q[i]];j != -1;j = next[j]) 32 if(w[j] && d[v[j]] == -1){ 33 d[v[j]] = d[q[i]] + 1; 34 q[rear++] = v[j]; 35 if(v[j] == T) return 1; 36 } 37 } 38 return 0; 39 } 40 41 int dfs(int cur,int a){ 42 if(cur == T) return a; 43 for(int &i = work[cur];i != -1;i = next[i]){ 44 if(w[i] && d[v[i]] == d[cur] + 1) 45 if(int t = dfs(v[i],min(a,w[i]))){ 46 w[i] -= t;w[i^1] += t; 47 return t; 48 } 49 } 50 return 0; 51 } 52 53 int dinic(){ 54 int ans = 0; 55 while(bfs()){ 56 memcpy(work,first,sizeof(first)); 57 while(int t = dfs(S,INF)) ans += t; 58 } 59 return ans; 60 } 61 62 void floyd(){ 63 for(int k = 1;k <= n;k++) 64 for(int i = 1;i <= n;i++) if(map[i][k]) 65 for(int j = 1;j <= n;j++) if(map[k][j]) 66 map[i][j] = 1; 67 68 for(int k = 1;k <= n;k++) 69 for(int i = 1;i <= n;i++) if(map[i][k]) 70 for(int j = 1;j <= n;j++) if(like[k][j]) 71 like[i][j] = 1; 72 } 73 74 bool test(int mid){ 75 init(); 76 for(int i = 1;i <= n;i++) 77 add_edge(S,i,mid),add_edge(i,i+n,K); 78 for(int i = 2*n+1;i <= 3*n;i++) 79 add_edge(i,T,mid); 80 for(int i = 1;i <= n;i++){ 81 for(int j = 1;j <= n;j++) 82 if(like[i][j]) add_edge(i,j+2*n,1); 83 else add_edge(i+n,j+2*n,1); 84 } 85 int ans = dinic(); 86 //printf("ans = %d ",ans); 87 if(ans == mid*n) return true; 88 return false; 89 } 90 int main() 91 { 92 int kase; 93 scanf("%d",&kase); 94 while(kase--){ 95 scanf("%d%d%d%d",&n,&m,&K,&f); 96 S = 0,T = 3*n+1; 97 memset(map,0,sizeof(map)); 98 memset(like,0,sizeof(like)); 99 for(int i = 0;i < m;i++){ 100 int a,b; 101 scanf("%d%d",&a,&b); 102 like[a][b] = 1; 103 } 104 for(int i = 0;i < f;i++){ 105 int a,b; 106 scanf("%d%d",&a,&b); 107 map[a][b] = map[b][a] = 1; 108 } 109 floyd(); 110 int L = 0,R = n,ans = 0; 111 while(L <= R){ 112 int mid = (L+R)>>1; 113 if(test(mid)){ 114 ans = mid; 115 L = mid+1; 116 } 117 else R = mid-1; 118 } 119 printf("%d ",ans); 120 } 121 return 0; 122 }