uva 11248 Frequency Hopping

题目大意：给定一个有向网络，每条边均有一个容量。

问是否存在一个从点1到点N。流量为C的流。假设不存在，能否够恰好改动一条弧的容量，使得存在这种流。

解题思路：先依照题目给出的边建好图，然后跑一发最大流，得到原始最大流C1，假设C1==C或者C==0时。能够直接输出possible。假设不存在这种流。那么開始找割边，将这些割边的容量添加C，再求最大流。假设能够，那么要输出全部的方案。改动全部割边后，仍没有符合条件的流，输出 not possible。

优化：1）第一次跑最大流的每条边的流量情况，能够留着，接下来能够在它的基础上增广。2）每次求最大流，不用求完，当流符合条件即>=C时，就可以返回成功。

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <cstdlib>

#include <queue>

using namespace std;

typedef long long ll;

const int N = 505;

const int M = 20005;

const ll INF = 1e18;

int n, e, s, t ;

ll c;

struct Edge{

    int from, to;

    ll cap, flow;

};

int cmp(Edge a, Edge b) {

    if (a.from != b.from) return a.from < b.from;

    else return a.to < b.to;

}

struct Dinic{

    vector<Edge> edges, tempOE;

    vector<int> G[M];

    vector<int> MCut;

    Edge rec[M];

    int vis[N], d[N];

    int cur[M];

    ll ans;

    void init() {

        ans = 0;

        for (int i = 0; i < e; i++) G[i].clear();

        edges.clear();

    }

    void addEdge(int from, int to, ll cap) {

        edges.push_back((Edge){from, to, cap, 0});

        edges.push_back((Edge){to, from, 0, 0});

        int m = edges.size();

        G[from].push_back(m - 2);

        G[to].push_back(m - 1);

    } 

    int BFS() {

        memset(vis, 0, sizeof(vis));

        queue<int> Q;

        Q.push(s);

        d[s] = 0;

        vis[s] = 1;

        while (!Q.empty()) {

            int u = Q.front(); Q.pop();

            for (int i = 0; i < G[u].size(); i++) {

                Edge &e = edges[G[u][i]];

                if (!vis[e.to] && e.cap > e.flow) {

                    vis[e.to] = 1;

                    d[e.to] = d[u] + 1;

                    Q.push(e.to);

                }

            }

        }

        return vis[t];

    }

    ll DFS(int u, ll a) {

        if (u == t || a == 0) return a;

        ll flow = 0, f;

        for (int &i = cur[u]; i < G[u].size(); i++) {

            Edge &e = edges[G[u][i]];

            if (d[u] + 1 == d[e.to] && (f = DFS(e.to, min(a, e.cap - e.flow))) > 0) {

                e.flow += f;

                edges[G[u][i]^1].flow -= f;

                flow += f;

                a -= f;

                if (a == 0) break;

            }

        }

        return flow;

    }

    bool MF() {

        while (BFS()) {

            memset(cur, 0, sizeof(cur));

            ans += DFS(s, INF);

            if (ans >= c) return true; //不用完整地求最大流，当流量大于等于c时，该改动就是可行的

        }

        return false;

    }

    void getMincut() { //求最小割

        MCut.clear();

        for (int i = 0; i < edges.size(); i += 2) {

            if (vis[edges[i].from] && !vis[edges[i].to]) {

                MCut.push_back(i);

            }

        }

    }

    int solve() {

        int cnt = 0;

        tempOE.clear();

        getMincut();

        ll f = ans; //求完初始最大流，记录当前总流量

        int es = edges.size();

        for (int i = 0; i < es; i++) tempOE.push_back(edges[i]); //记录初始最大流每条边的情况

        int cs = MCut.size();

        for (int i = 0; i < cs; i++) {

            edges[MCut[i]].cap = edges[MCut[i]].flow + c;

            if (MF()) {

                rec[cnt++] = edges[MCut[i]]; //若将该边的容量加上c之后。总流量大于等于c。则改动该边是可行方案。记录该边

            }

            ans = f; //每改动一条边。且检验完之后，恢复初始状态

            edges.clear();

            for (int i = 0; i < es; i++) edges.push_back(tempOE[i]);

        }

        return cnt;

    }

}din;

void input() {

    s = 1, t = n;

    int u, v;

    ll cap;

    for (int i = 0; i < e; i++) {

        scanf("%d %d %lld", &u, &v, &cap);

        din.addEdge(u, v, cap);

    }

}

void solve() {

    if (din.MF() || c == 0) {

        printf("possible\n");

        return;

    }

    int cnt = din.solve();

    if (!cnt) {

        printf("not possible\n");

        return;

    }

    sort(din.rec, din.rec + cnt, cmp); //记得排序

    printf("possible option:(%d,%d)", din.rec[0].from, din.rec[0].to);

    for (int i = 1; i < cnt; i++) {

        printf(",(%d,%d)", din.rec[i].from, din.rec[i].to);

    }

    puts("");

}

int main() {

    int Case = 1;

    while (scanf("%d %d %lld", &n, &e, &c) == 3) {

        if (!n && !e && !c) break;

        din.init();

        printf("Case %d: ", Case++);

        input();

        solve();

    }

    return 0;

}