• 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.  
    13. int n,m,k,S,T;
    14. int h[55],x[405],p[405],_tot;
    15. int H[2600],P[50000],X[50000],flow[50000],cap[50000],tot;
    16. inline void add(int x,int y,int z){
    17. 	P[++tot]=y;X[tot]=H[x];H[x]=tot;cap[tot]=flow[tot]=z;
    18. }
    19. inline void _add(int _x,int y){
    20. 	p[++_tot]=y;x[_tot]=h[_x];h[_x]=_tot;
    21. }
    22. queue<int> q;
    23. int d[2600];
    24. bool bfs(){
    25. 	memset(d,0,sizeof d);
    26. 	d[S]=1;int x;q.push(S);
    27. 	while(!q.empty()){
    28. 		x=q.front();q.pop();
    29. 		for(int i=H[x];i;i=X[i]){
    30. 			if(flow[i]>0&&!d[P[i]]){
    31. 				d[P[i]]=d[x]+1;
    32. 				q.push(P[i]);
    33. 			}
    34. 		}
    35. 	}
    36. 	return d[T];
    37. }
    38. int dfs(int x,int a){
    39. 	if(x==T||a==0) return a;
    40. 	int f=a,tmp;
    41. 	for(int i=H[x];i;i=X[i]){
    42. 		if(flow[i]>0&&d[P[i]]==d[x]+1){
    43. 			tmp=dfs(P[i],min(flow[i],a));
    44. 			a-=tmp;
    45. 			flow[i]-=tmp;
    46. 			flow[i^1]+=tmp;
    47. 			if(!a) break;
    48. 		}
    49. 	}
    50. 	if(f==a) d[x]=-1;
    51. 	return f-a;
    52. }
    53. int Dinic(int f){
    54. 	while(f<k&&bfs()) f+=dfs(S,k-f);
    55. 	return f;
    56. }
    57. bool ans[51][51];
    58. struct N{
    59. 	int x,y;
    60. }Q[2600];
    61. int pos[55][2];
    62. int main(){
    63. 	#ifdef LOCAL
    64. 	freopen("in.txt","r",stdin) ;
    65. 	freopen("out.txt","w",stdout) ;
    66. 	#endif
    67. 	while(~scanf("%d%d%d%d%d",&n,&m,&k,&S,&T)){
    68. 		tot=_tot=1;memset(h,0,sizeof h);memset(H,0,sizeof H);
    69. 		for(int i=0,x,y;i<m;i++){
    70. 			scanf("%d%d",&x,&y);
    71. 			_add(x,y);_add(y,x);
    72. 		}
    73. 		int flows(0);
    74. 		for(int t=1;;t++){
    75. 			for(int i=1;i<=n;i++){
    76. 				add(i+(t-1)*n,i+t*n,inf);
    77. 				add(i+t*n,i+(t-1)*n,0);
    78. 				for(int j=h[i];j;j=x[j]){
    79. 					add(i+(t-1)*n,p[j]+t*n,1);
    80. 					add(p[j]+t*n,i+(t-1)*n,0);
    81. 				}
    82. 			}
    83. 			add(T+t*n,T,inf);
    84. 			add(T,T+t*n,0);
    85. 			for(int i=1;i<=k;i++){
    86. 				pos[i][0]=S;
    87. 			}
    88. 			if((flows=Dinic(flows))==k){
    89. 				printf("%d\n",t);
    90. 				for(int i=0;i<t;i++){
    91. 					int num(0);
    92. 					memset(ans,0,sizeof ans);
    93. 					for(int j=1;j<=n;j++){
    94. 						for(int k=H[j+i*n];k;k=X[k]){
    95. 							if(cap[k]&&!flow[k]){
    96. 								ans[j][P[k]-(i+1)*n]=1;
    97. 							}
    98. 						}
    99. 					}
    100. 					for(int j=1;j<=n;j++){
    101. 						for(int k=1;k<=n;k++){
    102. 							if(ans[j][k]&&!ans[k][j]){
    103. 								Q[num].x=j,Q[num].y=k;num++;
    104. 							}
    105. 						}
    106. 					}
    107. 					printf("%d",num);
    108. 					for(int ps=0;ps<num;ps++){
    109. 						for(int j=1;j<=k;j++){
    110. 							if(pos[j][i&1]==Q[ps].x){
    111. 								pos[j][i&1]=0;
    112. 								pos[j][(i&1)^1]=Q[ps].y;
    113. 								printf(" %d %d",j,Q[ps].y);
    114. 								break;
    115. 							}
    116. 						}
    117. 					}
    118. 					for(int j=1;j<=k;j++){
    119. 						if(pos[j][i&1]) pos[j][(i&1)^1]=pos[j][i&1];
    120. 					}
    121. 					puts("");
    122. 				}
    123. 				break;
    124. 			}
    125. 		}
    126. 	}
    127. 	return 0 ;
    128. }
    129.