最大流

POJ 2391 Ombrophobic Bovines

Posted on

又是一些细节问题……
如果以我现在的水平去现场赛写网络流的题目,就算我会建图,我觉得还是挺悬的。

这里提前简单说一下dinic算法的最低上限的情况。
dinic的最高上限是 O ( \( V^2 E \) ) ,这是谁都知道的,然而对于一些特殊的图还有一些更低的上限。

在具有单位容量的网络中,Dinic算法可以在更短的时间内输出结果。每条阻塞流可以在 O ( E ) 的时间内构建,并且阶段的数量不超过 O( \( \sqrt E \) )或 O ( \( \sqrt[3] { V ^ 2 } \) )。此时算法的复杂度为 O ( \( min { ( \sqrt E , \sqrt[3] { V ^ 2 } ) } \) E )。
在二分图匹配问题的网络中,阶段的数量不超过 O ( \( \sqrt V \) ),算法的时间复杂度不超过 O ( \( \sqrt V E \) )。这种算法又被叫做Hopcroft-Karp算法。更普遍的情况是,这种复杂度对unit网络 — 网络中的顶点要么与源点相连,要么与汇点相连,要么是一个顶点的单一外向边,并且所有的容量限制都是整数。 —— 节选自 WIKI

简单说对于二分图,其上限为 不超过 O ( \( \sqrt V E \) ) 。

题意:
n个牛棚里面,各自有多头牛和空位,空为供给牛躲避。在牛棚之间总共有m条路并给定其长度。问让每头牛都有地方躲避最少需要多少时间。

思路:
floyd+二分+dinic
对于距离进行二分,距离最高 \(10^{12} \) 大约是 \(2^ {40} \) 。单次dinic 为 \(\sqrt {200} \) × 1500 复杂度完全足够!
然而我在不知道对于二分图的复杂度居然如此之低,我根本不敢去想到对这么大的范围进行二分。
不不不,我的确想到了,但是被我一下子就否定了。

注: 注意数据范围

AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>

using namespace std;
const int maxn = 1010;
const long long inf = 0x3f3f3f3f3f3f3f3f;

int n, m, idx, st, en;
int dis[maxn][maxn];
int level[maxn], cur[maxn], que[maxn * maxn];
int head[maxn];
long long mat[maxn / 2][maxn / 2];
int cow[maxn], cap[maxn];

struct node {
    long long flow;
    int to;
    int nxt;
} edges[100005];

void addEdge(int u, int v, long long f)
{
    edges[idx].to = v;
    edges[idx].flow = f;
    edges[idx].nxt = head[u];
    head[u] = idx++;

    edges[idx].to = u;
    edges[idx].flow = 0;
    edges[idx].nxt = head[v];
    head[v] = idx++;
}

bool bfs()
{
    memset(level, -1, sizeof level);
    que[0] = st;
    level[st] = 0;
    int l = 0, r = 1, u;
    while (l < r) {
        u = que[l++];
        for (int id = head[u]; ~id; id = edges[id].nxt) {
            int v = edges[id].to;
            if (edges[id].flow && level[v] == -1) {
                level[v] = level[u] + 1;
                que[r++] = v;
            }
        }
    }
    return level[en] != -1;
}

int dfs(int u, long long low)
{
    int cflow;
    if (u == en)
        return low;
    for (int& id = cur[u]; ~id; id = edges[id].nxt) {
        int v = edges[id].to;
        if (edges[id].flow > 0 && level[v] == level[u] + 1
            && (cflow = dfs(v, min(low, edges[id].flow)))) {
            edges[id].flow -= cflow;
            edges[id ^ 1].flow += cflow;
            return cflow;
        }
    }
    return 0;
}

int dinic()
{
    int ans = 0, cflow;
    while (bfs()) {
        for (int i = 0; i <= 2 * n; i++)
            cur[i] = head[i];
        while ((cflow = dfs(st, inf)))
            ans += cflow;
    }
    return ans;
}

void createGraph(long long len)
{
    memset(head, -1, sizeof head);
    idx = 0;
    for (int i = 1; i <= n; i++) {
        addEdge(i, i + n, inf);
        addEdge(st, i, cow[i]);
        addEdge(i + n, en, cap[i]);
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (mat[i][j] <= len)
                addEdge(i, j + n, inf);
}

int main()
{
    int u, v;
    long long ans, len;
    while (scanf("%d %d", &n, &m) != EOF) {
        memset(mat, 0x3f, sizeof mat);
        long long le = 0, ri = 0, mid, sum = 0;
        ans = -1, st = 0, en = n + n + 1;
        for (int i = 1; i <= n; i++) {
            scanf("%d %d", &cow[i], &cap[i]);
            sum += cow[i];
        }
        for (int i = 0; i < m; i++) {
            scanf("%d %d %lld", &u, &v, &len);
            mat[u][v] = mat[v][u] = min(mat[u][v], len);
        }
        for (int k = 1; k <= n; k++)
            for (int i = 1; i <= n; i++)
                for (int j = 1; j <= n; j++)
                    mat[i][j] = min(mat[i][j], mat[i][k] + mat[k][j]);
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++) {
                if (mat[i][j] != inf)
                    ri = max(ri, mat[i][j]);
            }
        while (le <= ri) {
            mid = (le + ri) >> 1;
            createGraph(mid);
            if (dinic() >= sum)
                ans = mid, ri = mid - 1;
            else
                le = mid + 1;
        }
        printf("%lld\n", ans);
    }
    return 0;
}
最大流

POJ 1637 Sightseeing tour

Posted on

kuangbin把这道题的难度设置为 crazy …… 搞得我都不太敢刷……

题意:
混合图中欧拉回路的判定

思路:
这道题是真的不好想,最后还是去看了题解,因为比较典型 好吧是我菜
混合图欧拉回路无法用普通的定理去判定,不行可以试试……网络流建模给出的思想是将无向边任意转化成有向边,再去通过变换无向边的方向来实现欧拉回路。

建图方式:
+ 对无向边建立你所设定的方向,容量为1
+ 对于每个点,如果入度与出度差的绝对值为奇数,则不存在欧拉回路。 ( 因为反转一条边,则两个点的入度出度差各自变化 2 )
+ 否则 ,对于每个点如果 入度>出度 则为 汇点,与超级汇点容量为 ( 入度 - 出度 ) / 2 ,反之则为源点,与超级源点容量为 ( 出度 - 入度 ) / 2 。

跑一遍dinic即可。

残余网络中流量不为0的边即为反转边。这样求出欧拉路径也不算什么难事了。

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>

using namespace std;
const int maxn = 410;
const int inf = 0x3f3f3f3f;

int n, m, idx, st, en;
int dis[maxn][maxn];
int level[maxn], cur[maxn], que[maxn * maxn];
int head[maxn];
int indegree[maxn], outdegree[maxn], subdegree[maxn];

struct node {
    int flow;
    int to;
    int nxt;
} edges[20005];

void addEdge(int u, int v, int f)
{
    edges[idx].to = v;
    edges[idx].flow = f;
    edges[idx].nxt = head[u];
    head[u] = idx++;

    edges[idx].to = u;
    edges[idx].flow = 0;
    edges[idx].nxt = head[v];
    head[v] = idx++;
}

bool bfs()
{
    memset(level, -1, sizeof level);
    que[0] = st;
    level[st] = 0;
    int l = 0, r = 1, u;
    while (l < r) {
        u = que[l++];
        for (int id = head[u]; ~id; id = edges[id].nxt) {
            int v = edges[id].to;
            if (edges[id].flow && level[v] == -1) {
                level[v] = level[u] + 1;
                que[r++] = v;
            }
        }
    }
    return level[en] != -1;
}

int dfs(int u, int low)
{
    int cflow;
    if (u == en)
        return low;
    for (int& id = cur[u]; ~id; id = edges[id].nxt) {
        int v = edges[id].to;
        if (edges[id].flow > 0 && level[v] == level[u] + 1
            && (cflow = dfs(v, min(low, edges[id].flow)))) {
            edges[id].flow -= cflow;
            edges[id ^ 1].flow += cflow;
            return cflow;
        }
    }
    return 0;
}

int dinic()
{
    int ans = 0, cflow;
    while (bfs()) {
        for (int i = 0; i <= 2 * n; i++)
            cur[i] = head[i];
        while ((cflow = dfs(st, inf)))
            ans += cflow;
    }
    return ans;
}

int main()
{
    int T, u, v, op;
    scanf("%d", &T);
    while (T--) {
        scanf("%d %d", &n, &m);
        memset(head, -1, sizeof head);
        memset(indegree, 0, sizeof indegree);
        memset(outdegree, 0, sizeof outdegree);
        idx = 0;
        st = 0, en = n + 1;
        for (int i = 0; i < m; i++) {
            scanf("%d %d %d", &u, &v, &op);
            if (u == v)
                continue;
            outdegree[u]++;
            indegree[v]++;
            if (!op)
                addEdge(u, v, 1);
        }
        bool flag = true;
        int sum = 0;
        for (int i = 1; i <= n; i++) {
            if (outdegree[i] > indegree[i]) {
                if ((outdegree[i] - indegree[i]) & 1) {
                    flag = false;
                    break;
                } else {
                    addEdge(0, i, (outdegree[i] - indegree[i]) / 2);
                    sum += (outdegree[i] - indegree[i]);
                }
            } else if (outdegree[i] < indegree[i]) {
                if ((indegree[i] - outdegree[i]) & 1) {
                    flag = false;
                    break;
                } else
                    addEdge(i, n + 1, (indegree[i] - outdegree[i]) / 2);
            }
        }
        if (!flag)
            puts("impossible");
        else {
            if (dinic() == sum / 2)
                puts("possible");
            else
                puts("impossible");
        }
    }
    return 0;
}
最大流

POJ 1815 Friendship

Posted on

感觉网络流的题目总是莫名奇妙的卡在数组大小上
数组开小,既能WA,又能TLE,也真实神奇……

题意:
给你一张图,让你求出最小割集,并按照字典序输出。

思路:
老套的思路,那些discuss里的奇淫巧计看了一下貌似全都被推翻了……
枚举+最大流,尝试删点,如果流量减少,则为割点。

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>

//#define DEBUG1 1

using namespace std;
const int maxn = 410;
const int inf = 0x3f3f3f3f;

int n, idx, st, en;
int dis[maxn][maxn];
int level[maxn], cur[maxn], que[maxn * maxn];
int head[maxn];
int point[maxn];
int mat[maxn][maxn];
int ans[maxn];

struct node {
    int flow;
    int to;
    int nxt;
} edges[20005];

void addEdge(int u, int v, int f)
{
    edges[idx].to = v;
    edges[idx].flow = f;
    edges[idx].nxt = head[u];
    head[u] = idx++;

    edges[idx].to = u;
    edges[idx].flow = 0;
    edges[idx].nxt = head[v];
    head[v] = idx++;
}

bool bfs()
{
    memset(level, -1, sizeof level);
    que[0] = st;
    level[st] = 0;
    int l = 0, r = 1, u;
    while (l < r) {
        u = que[l++];
        for (int id = head[u]; ~id; id = edges[id].nxt) {
            int v = edges[id].to;
            if (edges[id].flow && level[v] == -1) {
                level[v] = level[u] + 1;
                que[r++] = v;
            }
        }
    }
    return level[en] != -1;
}

int dfs(int u, int low)
{
    int cflow;
    if (u == en)
        return low;
    for (int& id = cur[u]; ~id; id = edges[id].nxt) {
        int v = edges[id].to;
        if (edges[id].flow > 0 && level[v] == level[u] + 1
            && (cflow = dfs(v, min(low, edges[id].flow)))) {
            edges[id].flow -= cflow;
            edges[id ^ 1].flow += cflow;
            return cflow;
        }
    }
    return 0;
}

int dinic()
{
    int ans = 0, cflow;
    while (bfs()) {
        for (int i = 0; i <= 2 * n; i++)
            cur[i] = head[i];
        while ((cflow = dfs(st, inf)))
            ans += cflow;
    }
    return ans;
}

void CreateGraph()
{
    memset(head, -1, sizeof head);
    idx = 0;
    for (int i = 1; i <= n; i++) {
        point[i] = idx;
        addEdge(i, i + n, 1);
        for (int j = i + 1; j <= n; j++) {
            if (mat[i][j]) {
                addEdge(i + n, j, inf);
                addEdge(j + n, i, inf);
            }
        }
    }
#ifdef DEBUG1
    for (int u = 1; u <= 2 * n; u++) {
        printf("u : %d -----> ", u);
        for (int id = head[u]; ~id; id = edges[id].nxt) {
            printf("%d ", edges[id].to);
        }
        puts("");
    }
#endif
}

int main()
{
    while (scanf("%d %d %d", &n, &st, &en) != EOF) {
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                scanf("%d", &mat[i][j]);
        if (mat[st][en] == 1) {
            puts("NO ANSWER!");
            continue;
        }
        st += n;
        CreateGraph();
        int max_flow = dinic(), top = 0;
        printf("%d\n", max_flow);
        for (int i = 1; i <= n && max_flow; i++) { 
            if (i == st - n || i == en)
                continue;
            CreateGraph();
            for (int j = 0; j < top; j++)
                edges[point[ans[j]]].flow = 0;
            edges[point[i]].flow = 0;
            int tmp = dinic();
            //printf("%d: flow %d\n", i, tmp);
            if (tmp != max_flow - 1)
                edges[point[i]].flow = 1;
            else {
                max_flow--;
                ans[top++] = i;
            }
        }
        for (int i = 0; i < top; i++)
            printf("%d%c", ans[i], i == top - 1 ? '\n' : ' ');
    }
    return 0;
}