HDU 4265 Science!

题意：有n个人n个位置。给出一个n*n的矩阵，第i行第j列表示第i个人可以做第j个位置。现在要求每个人都找到一个不同的位置，当他们全部找到各自的位置时，一轮结束，他们可以开始新的一轮。在新的一轮里，每个人同样会去找位置，但是每个人都不会去找原先已经坐过的位置。问一共可以进行多少轮这样的匹配，并输出每一轮的匹配方案。

如果不要求输出匹配方案，那好办，跟那个婚姻匹配的一样的办法。现在问题的关键是要求输出每一轮匹配的方案。于是。。就跑了n遍dinic。

首先，二分一个mid（轮次），从S到每个人i连一条边(S,i,mid)，再从每个位置j到T连一条边(j,T,mid),如果i可以选择j的话，连一条边(i,j,1)，跑最大流得到maxflow，如果maxflow=n*mid的话，说明可以进行这样的mid轮。

现在我们已经知道一共可以进行ans轮的匹配了，现在输出每一轮的匹配方案。首先，按上述的构图方案，令mid=ans再构一次图，跑最大流，删掉所有从人i出发没有流量流向位置j的边。然后再做ans这样的操作：(1)以mid=1构图(2)dinic(3)记录下所有从人i出发有流量流向位置j的边的起点终点，也就是每个人对应的位置，并输出(4)删掉这些已经流过的边

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 #define INF 1<<30
  6 #define maxn 210
  7 #define maxm 30000
  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,n;
 13 char map[90][90];
 14 int res[90];
 15 
 16 void init(){
 17     e = 0;
 18     memset(first,-1,sizeof(first));
 19 }
 20 
 21 void add_edge(int a,int b,int c){
 22     //printf("add:%d to %d,cap = %d
",a,b,c);
 23     v[e] = b;next[e] = first[a];w[e] = c;first[a] = e++;
 24     v[e] = a;next[e] = first[b];w[e] = 0;first[b] = e++;
 25 }
 26 
 27 int bfs(){
 28     int rear = 0;
 29     memset(d,-1,sizeof(d));
 30     d[S] = 0;q[rear++] = S;
 31     for(int i = 0;i < rear;i++){
 32         for(int j = first[q[i]];j != -1;j = next[j])
 33             if(w[j] && d[v[j]] == -1){
 34                 d[v[j]] = d[q[i]] + 1;
 35                 q[rear++] = v[j];
 36                 if(v[j] == T)   return 1;
 37             }
 38     }
 39     return 0;
 40 }
 41 
 42 int dfs(int cur,int a){
 43     if(cur == T)    return a;
 44     for(int &i = work[cur];i != -1;i = next[i]){
 45         if(w[i] && d[v[i]] == d[cur] + 1)
 46             if(int t = dfs(v[i],min(a,w[i]))){
 47                 w[i] -= t;w[i^1] += t;
 48                 return t;
 49             }
 50     }
 51     return 0;
 52 }
 53 
 54 int dinic(){
 55     int ans = 0;
 56     while(bfs()){
 57         memcpy(work,first,sizeof(first));
 58         while(int t = dfs(S,INF))   ans += t;
 59     }
 60     return ans;
 61 }
 62 
 63 void bulid(int mid){
 64     init();
 65     for(int i = 1;i <= n;i++)
 66         add_edge(S,i,mid),add_edge(i+n,T,mid);
 67     for(int i = 1;i <= n;i++){
 68         for(int j = 1;j <= n;j++)   if(map[i][j] == 'Y')
 69             add_edge(i,j+n,1);
 70     }
 71 }
 72 
 73 void del(int val){
 74     for(int i = 1;i <= n;i++)
 75         for(int j = first[i];j != -1;j = next[j])
 76             if(v[j] != S && w[j] == val)    map[i][v[j]-n] = 'N';
 77 }
 78 
 79 int main()
 80 {
 81     while(scanf("%d",&n) == 1){
 82         if(!n) break;
 83         S = 0,T = 2*n+1;
 84         for(int i = 1;i <= n;i++)
 85             scanf("%s",map[i]+1);
 86         int L = 0,R = n,ans = 0;
 87         while(L <= R){
 88             int mid = (L+R)>>1;
 89             bulid(mid);
 90             if(dinic() == mid*n){
 91                 ans = mid,L = mid+1;
 92             }else{
 93                 R = mid-1;
 94             }
 95         }
 96         printf("%d
",ans);
 97         bulid(ans);
 98         dinic();
 99         del(1);
100         while(ans--){
101             bulid(1);
102             dinic();
103             for(int i = 1;i <= n;i++){
104                 for(int j = first[i];j != -1;j = next[j]){
105                     if(v[j] != S && w[j] == 0){
106                         res[v[j]-n] = i;break;
107                     }
108                 }
109             }
110             for(int i = 1;i < n;i++)
111                 printf("%d ",res[i]);
112             printf("%d
",res[n]);
113             del(0);
114         }
115     }
116     return 0;
117 }

View Code