• Source 
    1. #include <cstdio>
    2. #include <cstring>
    3. #include <algorithm>
    4. #include <queue>
    5. //  by zrt
    6. //  problem:
    7. //  无论你在什么时候开始，重要的是开始以后就不要停止。
    8. using namespace std ;
    9. typedef long long LL ;
    10. const double eps(1e-10) ;
    11. const int inf(0x3f3f3f3f) ;
    12. int n,S,T;
    13. int in[105];
    14. int H[105],X[40000],P[40000],flow[40000],tot;
    15. inline void add(int x,int y,int z){
    16. 	P[++tot]=y;X[tot]=H[x];H[x]=tot;flow[tot]=z;
    17. }
    18. int m;
    19. int d[105];
    20. queue<int> q;
    21. bool bfs(){
    22. 	memset(d,0,sizeof d);
    23. 	d[S]=1;q.push(S);int x;
    24. 	while(!q.empty()){
    25. 		x=q.front();q.pop();
    26. 		for(int i=H[x];i;i=X[i]){
    27. 			if(flow[i]>0&&!d[P[i]]){
    28. 				d[P[i]]=d[x]+1;q.push(P[i]);
    29. 			}
    30. 		}
    31. 	}
    32. 	return d[T];
    33. }
    34. int dfs(int x,int a){
    35. 	if(x==T||a==0) return a;
    36. 	int tmp,f=a;
    37. 	for(int i=H[x];i;i=X[i]){
    38. 		if(flow[i]>0&&d[P[i]]==d[x]+1){
    39. 			tmp=dfs(P[i],min(flow[i],a));
    40. 			a-=tmp;
    41. 			flow[i]-=tmp;
    42. 			flow[i^1]+=tmp;
    43. 			if(!a) break;
    44. 		}
    45. 	}
    46. 	if(f==a) d[x]=-1;
    47. 	return f-a;
    48. }
    49. int Dinic(){
    50. 	int f(0);
    51. 	while(bfs()) f+=dfs(S,inf);
    52. 	return f;
    53. }
    54. int stk[105],top;
    55. void dfs(int x){
    56. 	stk[top++]=x;
    57. 	for(int j=H[x];j;j=X[j]){
    58. 		if(!(j&1)&&P[j]<=n&&flow[j^1]>0){
    59. 			flow[j^1]--;
    60. 			dfs(P[j]);
    61. 			break;
    62. 		//	printf("#%d %d %d\n",x,P[j],flow[j^1]);
    63. 		}
    64. 	}
    65. }
    66. int main(){
    67. 	#ifdef LOCAL
    68. 	freopen("in.txt","r",stdin) ;
    69. 	freopen("out.txt","w",stdout) ;
    70. 	#endif
    71. //	S=104,T=103;
    72. 	while(~scanf("%d",&n)){
    73. 		S=104,T=103;
    74. 		memset(in,0,sizeof in);
    75. 		memset(H,0,sizeof H);
    76. 		tot=1;
    77. 		for(int i=1;i<=n;i++){
    78. 			scanf("%d",&m);
    79. 			in[i]-=m;
    80. 			for(int j=0,x;j<m;j++){
    81. 				scanf("%d",&x);
    82. 				in[x]++;
    83. 				add(i,x,inf);
    84. 				add(x,i,0);
    85. 			}
    86. 		}
    87.  
    88. 		int ans(0);
    89. 		for(int i=1;i<=n;i++){
    90. 			if(in[i]>0) add(S,i,in[i]),add(i,S,0);
    91. 			else if(in[i]<0) add(i,T,-in[i]),add(T,i,0),ans-=in[i];//绝对满载 
    92. 		}
    93.  
    94. 	//	swap(S,T);//反向最大流 
    95. 		ans-=Dinic();
    96. 		printf("%d\n",ans); 
    97. 	//	memset(in,0,sizeof in);
    98. 		for(int i=1;i<=n;i++){
    99. 			for(int j=H[i];j;j=X[j]){
    100. 				if((j&1)&&P[j]<=n){
    101. 					in[P[j]]-=flow[j];
    102. 					in[i]+=flow[j];
    103. 					flow[j]++;
    104. 				}
    105. 			}
    106. 		}
    107. 		for(int i=1;i<=n;i++){
    108. 			while(in[i]<0){
    109. 				top=0;
    110.  
    111. 				dfs(i);
    112. 				if(top>1){
    113. 					in[i]++;
    114. 					in[stk[top-1]]--;
    115. 					printf("%d",stk[0]);
    116. 					for(int j=1;j<top;j++) printf(" %d",stk[j]);
    117. 					puts("");
    118. 				}
    119. 			}
    120. 		}
    121.  
    122. 	}
    123. 	return 0 ;
    124. }
    125.