题意：1到n节点（节点之间有一定的容量），需要流过C的流量，问是否可以？如果可以输出possible， 否则如果可以扩大任意一条边的容量
可以达到目的，那么输出possible option：接着输出每一条可以达到目的的边（按升序），再否则输出not possible
思路：先求一次最大流，如果流量至少为C，则直接输出possible，否则需要修改的弧一定在最小割里！
接着吧这些弧（最小割里的）的容量设为无穷大，然后在求最大流，看最大流的流量能否满足是C即可，如果满足了，那就把这一条边记录下来
分析：最大流的程序没有必要完全的执行完毕，知道当前的流量>=C那么就可以中止最大流的程序！
还有就是第一次的最大流程序如果没有找到>=C的最大流，那么此时的流量留着，下一次在最小割里扩容的时候，总是接着第一次Dinic的流量
继续寻找....
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#define N 105
#define INF 2000000005
using namespace std; struct EDGE{
int u, v, nt, cap;
bool flag;
bool vis;
EDGE(){}
EDGE(int u, int v, int nt, int cap, bool flag):u(u), v(v), nt(nt), cap(cap), flag(flag){}
}; struct node{
int x, y;
node(){}
node(int x, int y) : x(x), y(y){}
}; int pos[]; node ans[];
int preCost[];
int vis[];
int p[];
int pcnt;
int cnt; vector<EDGE>g;
int first[N]; int d[N];
int n, e, c; void addEdge(int u, int v, int c){
g.push_back(EDGE(u, v, first[u], c, true));
first[u] = g.size() - ;
g.push_back(EDGE(v, u, first[v], , false));
first[v] = g.size() - ;
} bool bfs(){
memset(d, , sizeof(d));
d[] = ;
queue<int>q;
q.push();
while(!q.empty()){
int u = q.front();
q.pop();
for(int i = first[u]; ~i; i = g[i].nt){
int v = g[i].v;
if(!d[v] && g[i].cap > ){
d[v] = d[u] + ;
q.push(v);
}
}
}
if(d[n] == ) return false;
return true;
} bool cmp(node a, node b){
if(a.x == b.x)
return a.y < b.y;
return a.x < b.x;
} int leave; int dfs(int u, int totf){
int flow = ;
if(u ==n || totf==) return totf;
for(int i = first[u]; ~i; i = g[i].nt){
int v = g[i].v;
if(d[v] == d[u] + && g[i].cap > ){
int ff = dfs(v, min(totf-flow, g[i].cap));
if(ff > ){
if(!vis[i]){
p[pcnt++]=i;
preCost[i] = g[i].cap;
vis[i] = ;
}
g[i].cap -= ff; if(!vis[i^]){
p[pcnt++]=i^;
preCost[i^] = g[i^].cap;
vis[i^] = ;
}
g[i^].cap += ff;
flow += ff; if(flow >= leave){
flow = leave;
return flow;
} if(totf == flow) break;
}
else d[v] = -;
}
}
return flow;
} bool Dinic(){
leave = c;
while(bfs()){
leave -= dfs(, INF);
if(leave == ) break;
}
if(leave == ) return true;
return false;
} int main(){
int cas = ;
while(scanf("%d%d%d", &n, &e, &c)){
if(!n) break;
memset(first, -, sizeof(first));
g.clear();
cnt = ;
while(e--){
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
addEdge(x, y, z);
}
printf("Case %d: ", ++cas);//这一块差点没有把我气死...居然有一个空格，没有看清楚啊...一直PE. if(n==){
printf("possible\n");
continue;
} if(Dinic()) printf("possible\n");
else{
int len = g.size();
for(int i=; i<len; ++i)
if(g[i].cap == && g[i].flag)
pos[cnt++] = i;//得到最小割
int cc = leave;//第一次Dinic之后，还剩下多少的流量需要流过
int ret = ;
for(int i=; i<cnt; ++i){
c = cc;//新的需要流过的流量
pcnt = ;
g[pos[i]].cap = INF;
memset(vis, , sizeof(vis));
if(Dinic())//如果增广成功，那么这条最小割满足
ans[ret++] = node(g[pos[i]].u, g[pos[i]].v);
for(int j=; j<pcnt; ++j)
g[p[j]].cap = preCost[p[j]];//将Dinic中所经过的边的值恢复成第一次Dinic之后的值！
g[pos[i]].cap = ;
}
if( ret > ){
sort(ans, ans+ret, cmp);
printf("possible option:(%d,%d)", ans[].x, ans[].y);
for(int i=; i<ret; ++i)
printf(",(%d,%d)", ans[i].x, ans[i].y);
printf("\n");
}
else printf("not possible\n");
}
}
return ;
}