1 #include<cstdio> 2 #include<cstring> 3 #define mt(a,b) memset(a,b,sizeof(a)) 4 const int inf=0x3f3f3f3f; 5 class Kuhn_Munkras { ///二分图最佳匹配O(ln*ln*rn)邻接阵 6     typedef int typec;///边权的类型 7     static const int MV=1024;///点的个数 8     int ln,rn,s[MV],t[MV],ll[MV],rr[MV],p,q,i,j,k; 9     typec mat[MV][MV];10 public:11     int lmatch[MV],rmatch[MV];12     void init(int tln,int trn) { ///传入ln左部点数，rn右部点数，要求ln<=rn，下标0开始13         ln=tln;14         rn=trn;15         for(i=0; i<ln; i++)16             for(j=0; j<rn; j++)17                 mat[i][j]=-inf;18     }19     void add(int u,int v,typec w) {///最小权匹配可将权值取相反数20         mat[u][v]=w;21     }22     typec solve() {///返回最佳匹配值，-1表示无法匹配23         typec ret=0;24         for (i=0; i<ln; i++) {25             for (ll[i]=-inf,j=0; j<rn; j++)26                 ll[i]=mat[i][j]>ll[i]?mat[i][j]:ll[i];27             if( ll[i] == -inf ) return -1;// 无法匹配！28         }29         for (i=0; i<rn; rr[i++]=0);30         mt(lmatch,-1);31         mt(rmatch,-1);32         for (i=0; i<ln; i++) {33             mt(t,-1);34             for (s[p=q=0]=i; p<=q&&lmatch[i]<0; p++)35                 for (k=s[p],j=0; j<rn&&lmatch[i]<0; j++)36                     if (ll[k]+rr[j]==mat[k][j]&&t[j]<0) {37                         s[++q]=rmatch[j],t[j]=k;38                         if (s[q]<0)39                             for (p=j; p>=0; j=p)40                                 rmatch[j]=k=t[j],p=lmatch[k],lmatch[k]=j;41                     }42             if (lmatch[i]<0) {43                 for (i--,p=inf,k=0; k<=q; k++)44                     for (j=0; j<rn; j++)45                         if(t[j]<0&&ll[s[k]]+rr[j]-mat[s[k]][j]<p)46                             p=ll[s[k]]+rr[j]-mat[s[k]][j];47                 for (j=0; j<rn; rr[j]+=t[j]<0?0:p,j++);48                 for (k=0; k<=q; ll[s[k++]]-=p);49             }50         }51         for (i=0; i<ln; i++) {52             if( lmatch[i] < 0 ) return -1;53             if( mat[i][lmatch[i]] <= -inf ) return -1;54             ret+=mat[i][lmatch[i]];55         }56         return ret;57     }58 } gx;59 int a[512];60 int main() {61     int t,n,m;62     while(~scanf("%d",&t)) {63         while(t--) {64             scanf("%d",&n);65             for(int i=0; i<n; i++) {66                 scanf("%d",&a[i]);67                 a[i]*=a[i];68             }69             gx.init(n,n<<1);70             for(int i=0,j; i<n; i++) {71                 scanf("%d",&m);72                 while(m--) {73                     scanf("%d",&j);74                     gx.add(i,j-1,a[i]);75                 }76                 gx.add(i,i+n,0);77             }78             int flag=gx.solve();79             for(int i=0; i<n; i++) {80                 int ans=0;81                 if(gx.lmatch[i]<n) {82                     ans=gx.lmatch[i]+1;83                 }84                 printf("%d ",ans);85             }86             puts("");87         }88     }89     return 0;90 }