• 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(0x7fffffff) ;
    12. int n,m,c;
    13. int S,T;
    14. int H[105],X[32005],P[32005],flow[32005],tot,cap[32005];
    15. int floww[32005];
    16. inline void add(int x,int y,int z ){
    17. 	P[++tot]=y;X[tot]=H[x];H[x]=tot;flow[tot]=cap[tot]=z;
    18. }
    19. int d[105];
    20. queue<int> q;
    21. bool belong[105];
    22. bool bfs(){
    23. 	memset(d,0,sizeof d);
    24. 	d[S]=1;q.push(S);
    25. 	int k;
    26. 	while(!q.empty()){
    27. 		k=q.front();q.pop();
    28. 		for(int i=H[k];i;i=X[i]){
    29. 			if(flow[i]>0&&!d[P[i]]){
    30. 				d[P[i]]=d[k]+1;
    31. 				q.push(P[i]);
    32. 			}
    33. 		}
    34. 	}
    35. 	return d[T];
    36. }
    37. int dfs(int x,int a){
    38. 	if(x==T||a==0) return a;
    39. 	int f=a,tmp;
    40. 	for(int i=H[x];i;i=X[i]){
    41. 		if(flow[i]>0&&d[P[i]]==d[x]+1){
    42. 			tmp=dfs(P[i],min(flow[i],a));
    43. 			a-=tmp;
    44. 			flow[i]-=tmp;
    45. 			flow[i^1]+=tmp;
    46. 			if(!a) break;
    47. 		}
    48. 	}
    49. 	if(f==a) d[x]=0-1;
    50. 	return f-a;
    51. }
    52. long long Dinic(long long flows){
    53. 	long long f=flows;
    54. 	while(f<c&&bfs()) f+=dfs(S,inf);
    55. 	return f;
    56. }
    57. int main(){
    58. 	#ifdef LOCAL
    59. 	freopen("in.txt","r",stdin) ;
    60. 	freopen("out.txt","w",stdout) ;
    61. 	#endif
    62. 	int kase(0);
    63. 	while(scanf("%d%d%d",&n,&m,&c),n|m|c){
    64. 		memset(belong,0,sizeof belong);
    65. 		tot=1;kase++;
    66. 		S=1,T=n;
    67. 		memset(H,0,sizeof H);
    68. 		for(int i=0,x,y,z;i<m;i++){
    69. 			scanf("%d%d%d",&x,&y,&z);
    70. 			add(x,y,z);
    71. 			add(y,x,0);
    72. 		}
    73. 		long long maxflow;
    74. 		if((maxflow=Dinic(0))>=c){
    75. 			printf("Case %d: possible\n",kase);continue;
    76. 		}
    77. 		belong[S]=1;
    78. 		q.push(S);int k;
    79. 		while(!q.empty()){
    80. 			k=q.front();q.pop();
    81. 			for(int i=H[k];i;i=X[i]){
    82. 				if(flow[i]>0&&!belong[P[i]]) {
    83. 					belong[P[i]]=1;
    84. 					q.push(P[i]);
    85. 				}
    86. 			}
    87. 		}
    88. 		memcpy(floww,flow,sizeof flow);
    89. 		bool ok=0;
    90. 		bool fit=1;
    91. 		int C[105],t;
    92. 		for(int i=1;i<=n;i++){
    93. 			t=0;
    94. 			for(int j=H[i];j;j=X[j]){
    95. 				if((belong[P[j]]^belong[i])&&cap[j]>0){
    96. 					memcpy(flow,floww,sizeof flow);
    97. 					flow[j]=inf;
    98. 					if(Dinic(maxflow)>=c){
    99. 						C[t++]=P[j];
    100. 					}
    101. 				}
    102. 			}
    103. 			sort(C,C+t);
    104. 			if(t>0&&!ok){
    105. 				ok=1;printf("Case %d: possible option",kase);
    106. 			}
    107. 			for(int j=0;j<t;j++){
    108. 				if(fit)fit=0,putchar(':');else putchar(',');
    109. 				printf("(%d,%d)",i,C[j]);
    110. 			}
    111. 		}
    112. 		if(ok) putchar('\n');
    113. 		else printf("Case %d: not possible\n",kase);
    114. 	}
    115. 	return 0 ;
    116. }
    117.