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