Uvaoj 11248 Frequency Hopping(Dinic求最小割)

题意：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[10005];

node ans[10005];
int preCost[20005];
int vis[20005];
int p[20005];
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() - 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<int>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<len; ++i)
                if(g[i].cap == 0 && g[i].flag)
                    pos[cnt++] = i;//得到最小割
            int cc = leave;//第一次Dinic之后，还剩下多少的流量需要流过
            int ret = 0;
            for(int i=0; i<cnt; ++i){
                c = cc;//新的需要流过的流量
                pcnt = 0;
                g[pos[i]].cap = INF;
                memset(vis, 0, sizeof(vis));
                if(Dinic())//如果增广成功，那么这条最小割满足
                       ans[ret++] = node(g[pos[i]].u, g[pos[i]].v);
                for(int j=0; j<pcnt; ++j)
                    g[p[j]].cap = preCost[p[j]];//将Dinic中所经过的边的值恢复成第一次Dinic之后的值！
                g[pos[i]].cap = 0;
            }
            if( ret > 0 ){
                sort(ans, ans+ret, cmp);
                printf("possible option:(%d,%d)", ans[0].x, ans[0].y);
                for(int i=1; i<ret; ++i)
                    printf(",(%d,%d)", ans[i].x, ans[i].y);
                printf("\n");
            }
            else printf("not possible\n");
        }
    }    
    return 0;
}