[UVA 11248] Frequency Hopping

题目大意

给个带权无向图，求能不能修改一条边流量到INF来让1到N的最大流达到C，能的话输出方案。

解题报告

这组卡掉了我的wa程序

Input:
20 7 100
1 9 78
9 20 110
9 1 43
4 20 116
5 4 101
5 20 11
9 5 50
0 0 0
Output:
Case 1: possible option:(1,9)

当然这道题可以用超神的循环版isap直接搞(没学过最好学一下,不要像我一样天天被卡常…)。

网上有很多题解都是比较暴力的做法，可以卡得跑M次最大流,这复杂度明显不科学。
而且最大流优化得不好( 比如我 )或者被出题人卡就会无限Tle
接下来说一个没出现过的新的更高效做法，只需要跑N*2次最大流:
首先抛出最大流后发现只有修改必然存在于最小割内的边增大容量才有作用，但是我们不能枚举每条边，这样会被卡到M遍最大流
预处理出最小割左边的所有节点在跑完最大流后从S出发能汇聚在那里的最大流量和从最小割右边每个节点从T出发能汇聚在那里的最大流量，就可以通过枚举两边的点来判断最大流能否增大到C了。
JeremyGuo想出的这个方法，但是代码好像很难实现的样子( 于是他果断追随题解写了暴力 )

提供代码具体实现思路:
1.构建原图
2.1->N跑最大流，记为flow
3.dfs染色s集和t集，找出存在于确定的最小割两端的所有点，分别存入vset[0](s集边界)和vset[1](t集边界)
4.保存残余网络到storage
5.枚举vset[0]内每个点u，连接无流量上限的边u->N，跑1->N的最大流，流量相当于最多能在u点汇聚多少流量，保存在vflow[u]，跑完后从storage恢复残余网络。
6.反向建图
7.N->1跑最大流，保留残余网络到storage
8.枚举vset[1]内每个点u，连接无流量上限的边u->1，跑N->1的最大流，流量相当于最多能在u点汇聚多少流量，保存在vflow[u]，跑完后从storage恢复残余网络。
9.枚举每条边u->v，但是此时不需要重复跑最大流啦！检查u在s中并且v在t中并且min(vflow[u], vflow[v])+flow >= C就可以啦。
10.检查你的细节！注意清零！

代码

建图一脸恶心。

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>

const int INF = 0x3f3f3f3f;
using std :: min;
using std :: max;

namespace isap {
    const int MAXD = 120;
    const int MAXE = 44000;
    struct Node {
        int v, w, nxt, bk;
    } d[MAXE];
    int head[MAXD], etot;
    inline int addEdge (int a, int b, int c) {
        etot ++;
        d[etot].v = b;
        d[etot].w = c;
        d[etot].bk = etot + 1;
        d[etot].nxt = head[a];
        head[a] = etot;
        etot ++;
        d[etot].v = a;
        d[etot].w = 0;
        d[etot].bk = etot - 1;
        d[etot].nxt = head[b];
        head[b] = etot;
        //printf("%d to %d: %d\n", a, b, c);
        return etot;
    }

    int S, T, N;
    int dis[MAXD], vd[MAXD];
    int seq[MAXD+100];
    void bfs (int s) {
        int l, r;
        memset(dis, 0x3f, sizeof dis);
        dis[seq[l=r=0] = s] = 0;
        while(l <= r) {
            int u = seq[l++];
            for(int e = head[u]; e; e = d[e].nxt)
                if(dis[d[e].v] > dis[u]+1) {
                    dis[d[e].v] = dis[u]+1;
                    seq[++r] = d[e].v;
                }
        }
    }
    int dfs (int u, int val) {
        if(u == T) return val;
        int rest = val;
        for(int e = head[u]; e; e = d[e].nxt)
            if(d[e].w && dis[d[e].v]+1 == dis[u]) {
                int t = dfs(d[e].v, min(rest, d[e].w));
                rest -= t;
                d[e].w -= t;
                d[d[e].bk].w += t;
                if(!rest) return val;
                if(dis[S] >= N) return val - rest;
            }
        if(val == rest) {
            if(!(--vd[dis[u]])) {dis[S] = N; return 0;}
            dis[u] = N;
            for(int e = head[u]; e; e = d[e].nxt)
                if(d[e].w) dis[u] = min(dis[u], dis[d[e].v]+1);
            vd[dis[u]]++;
            return 0;
        }
        return val - rest;
    }
    int sap (int s, int t, int n) {
        S = s, T = t, N = n;
        memset(vd, 0, sizeof vd);
        bfs(T);
        for(int i = 1; i<=N; i++)
            if(dis[i] < N) vd[dis[i]] ++;
        int flow = 0;
        while(dis[S] < N) flow += dfs(S, INF);
        return flow;
    }
    void clear () {
        S = T = N = 0;
        memset(head, 0, sizeof head);
        etot = 0;
    }
}

template<int MAXD, int MAXE> struct DGraph {
    struct Node {
        int v, nxt;
    } d[MAXE];
    int head[MAXD], etot;
    inline int addEdge (int a, int b) {
        etot ++;
        d[etot].v = b;
        d[etot].nxt = head[a];
        head[a] = etot;
        return etot;
    }
    Node & operator [] (int index) {
        return d[index];
    }
    void clear () {
        etot = 0;
        memset(head, 0, sizeof head);
    }
} ;
DGraph<110, 41000> res;

namespace storage {
    isap :: Node d[isap :: MAXE];
    int head[isap :: MAXD], etot, S, T, N;
    void save () {
        S = isap :: S, T = isap :: T, N = isap :: N, etot = isap :: etot;
        memcpy(d, isap :: d, (sizeof isap::d[0])*(etot+3));
        memcpy(head, isap :: head, (sizeof isap::head[0])*(N+3));
    }
    void reverse () {
        isap :: S = S, isap :: T = T, isap :: N = N, isap :: etot = etot;
        memcpy(isap :: d, d, (sizeof isap::d[0])*(etot+3));
        memcpy(isap :: head, head, (sizeof isap::head[0])*(N+3));
    }
}

const int MAXN = 120;
int N, M, C;
int tag[MAXN];
int pcol;
void paint (int u) {
    if(tag[u]) return ;
    tag[u] = pcol;
    for(int e = res.head[u]; e; e = res[e].nxt)
        paint(res[e].v);
}
#include <vector>
using std :: vector;
vector<int> vset[2];
int side[11000];
int vflow[11000];
int inp[11000][3];
inline bool pCompare (std :: pair<int, int> a, std :: pair<int, int> b) {
    if(a.first == b.first) return a.second < b.second;
    return a.first < b.first;
}
vector<std :: pair<int, int> > ans;

inline int getInt () {
    int ret; char ch;
    while((ch = getchar()) < '0' || ch > '9') ;
    ret = ch - '0';
    while((ch = getchar()) >= '0' && ch <= '9') ret *= 10, ret += ch - '0';
    return ret;
}

int main () {
    //freopen("ans.txt", "w", stdout);
    int tc = 0;
    while(~scanf("%d%d%d", &N, &M, &C)) {
        if(!N && !M && !C) break;
        isap :: clear();
        for(int i = 1; i<=M; i++) {
            inp[i][0] = getInt(), inp[i][1] = getInt(), inp[i][2] = getInt();
            isap :: addEdge(inp[i][0], inp[i][1], inp[i][2]);
        }
        int flow = isap :: sap(1, N, N);
        printf("Case %d: ", ++tc);
        if(flow >= C) {puts("possible"); continue ;}
        memset(side, 0, sizeof side); memset(vflow, 0, sizeof vflow);
        res.clear();
        for(int i = 1; i<=N; i++)
            for(int e = isap::head[i]; e; e = isap::d[e].nxt)
                if((e&1) && isap::d[e].w)
                    res.addEdge(i, isap::d[e].v);
        memset(tag, 0, sizeof tag);
        pcol = 1, paint(1);
        res.clear();
        for(int i = 1; i<=N; i++)
            for(int e = isap::head[i]; e; e = isap::d[e].nxt)
                if((e&1) && isap::d[e].w)
                    res.addEdge(isap::d[e].v, i);
        pcol = 2, paint(N);
        vset[0].clear(), vset[1].clear();
        for(int u = 1; u<=N; u++) // 找到唯一最小割边上的所有点
            if(tag[u]) for(int e = isap::head[u]; e; e = isap::d[e].nxt)
                if((tag[isap::d[e].v]|tag[u]) == 3)
                {vset[tag[u]==2].push_back(u); side[u] = tag[u]; break;}
        storage :: save();
        for(vector<int>::iterator it = vset[0].begin(); it!=vset[0].end(); it++) {
            isap :: addEdge(*it, N, INF);
            vflow[*it] = isap :: sap(1, N, N);
            storage :: reverse();
        }
        isap :: clear();
        for(int i = 1; i<=M; i++)
            isap :: addEdge(inp[i][1], inp[i][0], inp[i][2]);
        isap :: sap(N, 1, N);
        storage :: save();
        for(vector<int>::iterator it = vset[1].begin(); it!=vset[1].end(); it++) {
            isap :: addEdge(*it, 1, INF);
            vflow[*it] = isap :: sap(N, 1, N);
            storage :: reverse();
        }
        ans.clear();
        for(int i = 1; i<=M; i++) {
            int u = inp[i][0], v = inp[i][1];
            if(side[u] == 1 && side[v] == 2 && min(vflow[u], vflow[v]) >= C-flow)
                ans.push_back(std :: make_pair(u, v));
        }
        if(ans.size() == 0) {puts("not possible"); continue ;}
        std :: sort(ans.begin(), ans.end(), pCompare);
        printf("possible option:");
        for(vector<std :: pair<int, int> >::iterator it = ans.begin(); it != ans.end(); it++)
            if(it != ans.begin()) printf(",(%d,%d)", (*it).first, (*it).second);
            else printf("(%d,%d)", (*it).first, (*it).second);
        putchar('\n');
    }
    //fclose(stdout);
    //system("notepad ans.txt");
}