1 /*  2 * this code is made by bjfu_song  3 * Problem: 1227  4 * Verdict: Accepted  5 * Submission Date: 2014-10-05 14:53:22  6 * Time: 132MS  7 * Memory: 2340KB  8 */  9 #include<iostream> 10 #include<stdio.h> 11 #include<string.h> 12 #include<algorithm> 13 using namespace std; 14 #include <string.h> 15 #define MAXN 410 16 #define inf 1000000000 17 #define _clr(x) memset(x,-1,sizeof(int)*MAXN) 18  19 int f[1010],f1[MAXN],f2[MAXN]; 20 int n; 21 int w[MAXN][MAXN]; 22 /****************************************************** 23 二分图最佳匹配 （kuhn munkras 算法 O(m*m*n)). 24 邻接矩阵形式 。  返回最佳匹配值，传入二分图大小m,n 25 邻接矩阵 mat ，表示权，match1,match2返回一个最佳匹配,为匹配顶点的match值为-1， 26 一定注意m<=n，否则循环无法终止，最小权匹配可将全职取相反数。 27 初始化：  for(i=0;i<MAXN;i++) 28              for(j=0;j<MAXN;j++) mat[i][j]=-inf; 29 对于存在的边：mat[i][j]=val;//注意不能负值 30 · 可能存在没有匹配的边。 31 ********************************************************/ 32  33 void kuhn_munkras(int m, int n, int mat[][MAXN], int* match1, int* match2) { 34     int s[MAXN], t[MAXN], l1[MAXN], l2[MAXN], p, q, ret = 0, i, j, k; 35  36     for( i=0;i<1010;i++) match1[i] = -1; 37     for (i = 0; i < m; i++) { 38         for (l1[i] = -inf, j = 0; j < n; j++) 39             l1[i] = mat[i][j] > l1[i] ? mat[i][j] : l1[i]; 40     } 41     for (i = 0; i < n; l2[i++] = 0) 42         ; 43     for (_clr(match1), _clr(match2), i = 0; i < m; i++) { 44         for (_clr(t), s[p = q = 0] = i; p <= q && match1[i] < 0; p++) 45             for (k = s[p], j = 0; j < n && match1[i] < 0; j++) 46                 if (l1[k] + l2[j] == mat[k][j] && t[j] < 0) { 47                     s[++q] = match2[j], t[j] = k; 48                     if (s[q] < 0) 49                         for (p = j; p >= 0; j = p) 50                             match2[j] = k = t[j], p = match1[k], match1[k] = j; 51                 } 52         if (match1[i] < 0) { 53             for (i--, p = inf, k = 0; k <= q; k++) 54                 for (j = 0; j < n; j++) 55                     if (t[j] < 0 && l1[s[k]] + l2[j] - mat[s[k]][j] < p) 56                         p = l1[s[k]] + l2[j] - mat[s[k]][j]; 57             for (j = 0; j < n; l2[j] += t[j] < 0 ? 0 : p, j++) 58                 ; 59             for (k = 0; k <= q; l1[s[k++]] -= p) 60                 ; 61         } 62     } 63     for (i = 0; i < m; i++) {// if处理无匹配的情况！！ 64         if (match1[i] < 0) 65             match1[i] = -1; 66         if (mat[i][match1[i]] <= -inf) 67             match1[i] = -1; 68     } 69 } 70  71 int main() 72 { 73     //freopen("in.txt","r",stdin); 74     while(scanf("%d",&n)!=EOF) 75     { 76         for(int i=0;i<n;i++) scanf("%d",&f[i]); //每个孩子的权值 77         for(int i=0;i<MAXN;i++) 78             for(int j=0;j<MAXN;j++) w[i][j] = -inf; 79         for(int i=0; i<n; i++){ 80             int t;scanf("%d",&t); 81             for(int j=1; j<=t; j++){ 82                 int z;scanf("%d",&z); 83                 w[i][z-1] = f[i];  //对第z个孩子的喜爱程度为权值 84             } 85         } 86 //        for(int i=0;i<n;i++){ 87 //          for(int j=0;j<n;j++){ 88 //              printf("%d ",w[i][j]); 89 //          }printf("\n"); 90 //        } 91        // for(int i=0;i<1010;i++) f1[i] = -1; 92  93         kuhn_munkras(n,n,w,f1,f2); 94  95         //printf("%d\n",n); 96  97         for(int i=0; i<n; i++) 98         { 99             if(i) printf(" ");100             if(f1[i]==-1) printf("0");101             else printf("%d",f1[i]+1);102         }103     }104     return 0;105 }