最大流

POJ 1698 Alice’s Chance

Posted on

这道题本来是放在二分图多重匹配的专题上的……
但是在二分图上没怎么想出来,在网络流上一下子就有了想法……
因为本来二分图问题就是网络流的子问题么……我如是安慰自己……

题意:
一个刚出道的女演员有 n 部电影要拍,一部电影要拍多天,一天只能拍一部,给定每部电影安排的日期,和截止时间,问能否安排妥当。

思路:
这道题在网路流建图上一开始我是这样建的。

记录一周中每天限制周数最大的,作为电影与日期的流量,源点到电影流量为拍摄天数,日期到汇点容量为各自的限制周数。
这里有一个错误的地方,我拿个数据就很容易明白。

3
1 0 0 0 0 0 0 1 1
1 0 0 0 0 0 0 2 2
1 0 0 0 0 0 0 inf inf

实际上因为周数并不是很多,最多为 50 ,完全可以拆分成 50 × 7 个节点,这样反而更容易理解,也更容易写。

AC Code

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

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = (n - 1); (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (st) <= (en); (st)++)
#define rrange(i, st, en) for (int(i) = (en); (en) >= (st); (en)--)
#define fill(ary, num) memset((ary), (num), sizeof((ary)))

using namespace std;

const int maxn = 5000;
const int inf = 0x3f3f3f3f;

int n, m, st, en, idx, sum;
int level[maxn], cur[maxn];
int head[maxn];
bool vis[400];

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

queue<int> que;

inline void addEdge(int u, int v, int flow)
{
    edges[idx].to = v;
    edges[idx].flow = flow;
    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()
{
    while (!que.empty())
        que.pop();
    memset(level, -1, sizeof level);
    que.push(st);
    level[st] = 0;
    int u;
    while (!que.empty()) {
        u = que.front();
        que.pop();
        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.push(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 && 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 <= en; i++)
            cur[i] = head[i];
        while ((cflow = dfs(st, inf)))
            ans += cflow;
    }
    return ans;
}

void createGraph()
{
    memset(head, -1, sizeof head);
    memset(vis, false, sizeof vis);
    st = 0, en = 350 + n + 1, idx = 0, sum = 0;
    int cap, limit, status[10];
    for (int i = 1; i <= n; i++) {
        int ts = 350 + i;
        for (int j = 1; j <= 7; j++)
            scanf("%d", status + j);
        scanf("%d %d", &cap, &limit);
        sum += cap;
        addEdge(st, ts, cap);
        for (int j = 1; j <= 7; j++)
            if (status[j])
                for (int k = 0; k < limit; k++) {
                    addEdge(ts, k * 7 + j, 1);
                    if (!vis[k * 7 + j]) {
                        addEdge(k * 7 + j, en, 1);
                        vis[k * 7 + j] = true;
                    }
                }
    }
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        createGraph();
        if (dinic() == sum)
            puts("Yes");
        else
            puts("No");
    }
    return 0;
}
最大流

SPOJ 962 IM – Intergalactic Map

Posted on

一眼题,但是有个很坑的地方,我看了题目没注意。
就是输入数据会有无效输入……结果贡献了3发wa,还不断尝试开大数组……

传送门

题意:
给你一张无向图,让你从1点出发,经过2点,最后到3点,能否实现。每个点只能去一次。

思路:
肯定是拆点啦,容量设置成1即可。再从2开始跑,看流量能否为2。

AC Code

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

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

int n, m, st, en, idx;
int level[maxn], cur[maxn];
int head[maxn];

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

queue<int> que;

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

bool bfs()
{
    while (!que.empty())
        que.pop();
    memset(level, -1, sizeof level);
    que.push(st);
    level[st] = 0;
    int u;
    while (!que.empty()) {
        u = que.front();
        que.pop();
        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.push(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 && 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;
    scanf("%d", &T);
    while (T--) {
        scanf("%d %d", &n, &m);
        memset(head, -1, sizeof head);
        idx = 0;
        for (int i = 1; i <= n; i++) {
            addEdge(i, i + n, 1);
            addEdge(i + n, i, 0);
        }
        while (m--) {
            scanf("%d %d", &u, &v);
            if (u < 1 || v < 1 || u > n || v > n)
                continue;
            addEdge(u + n, v, 1);
            addEdge(v + n, u, 1);
        }
        st = 2 + n, en = 2 * n + 1;
        addEdge(1 + n, en, 1);
        addEdge(en, 1 + n, 0);
        addEdge(3 + n, en, 1);
        addEdge(en, 3 + n, 0);
        if (dinic() == 2)
            puts("YES");
        else
            puts("NO");
    }
    return 0;
}
最大流

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;
}
最大流

SPOJ 287 Smart Network Administrator

Posted on

坑哭了……
先是一个小地方初始化错误,tle了5发,看到下面说数据很多,还尝试开了输入挂……

然后数组开小,WA了n发

题意:
村通网系列。一个村子只有1号家庭有网络,现在有k家用户想要通网,为了网络质量,在一条街道上的每条网络都必须是不同的网线。问最少需要多少掉网线。(差不多就是这样的,颜色什么的就别管了……)

思路:
这道题我看完第一个想法就是二分,但是因为dinic的复杂度问题不是很敢写。搜了一下题解,居然真的是二分……众所周知dinic的复杂度上限为 O(n^2 * m) 如果是稠密图,最高可达 O(n^4) 二分最多9次,除开重新建图,数据最多500组,n最多500,也就是 500^5 ……

然而结果是 0.69 ,我也不知道是什么单位,在spoj刷题是几百年前了…… ,应该是 s 吧。

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 int inf = 0x3f3f3f3f;

int n, m, k, st, en, idx;
int dis[maxn][maxn];
int level[maxn], cur[maxn], que[maxn * maxn];
int customer[maxn], head[maxn], from[maxn], to[maxn];

struct node {
    int to;
    int nxt;
    int flow;
} edges[2 * maxn * maxn];

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

inline bool scan_d(int& num)
{
    char in;
    bool IsN = false;
    in = getchar();
    if (in == EOF)
        return false;
    while (in != '-' && (in < '0' || in > '9'))
        in = getchar();
    if (in == '-') {
        IsN = true;
        num = 0;
    } else
        num = in - '0';
    while (in = getchar(), in >= '0' && in <= '9') {
        num *= 10, num += in - '0';
    }
    if (IsN)
        num = -num;
    return true;
}

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 && 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;
}

inline void resetGraph(int len)
{
    memset(head, -1, sizeof head);
    idx = 0;
    for (int i = 0; i < m; i++) {
        addEdge(from[i], to[i], len);
        addEdge(to[i], from[i], len);
    }
    for (int i = 0; i < k; i++) {
        addEdge(customer[i], 0, 1);
        addEdge(0, customer[i], 0);
    }
}

int main()
{
    int T;
    scan_d(T);
    while (T--) {
        scan_d(n);
        scan_d(m);
        scan_d(k);
        st = 1, en = 0;
        for (int i = 0; i < k; i++)
            scan_d(customer[i]);
        for (int i = 0; i < m; i++) {
            scan_d(from[i]);
            scan_d(to[i]);
        }
        int l = 0, r = k, mid;
        while (l <= r) {
            mid = (l + r) >> 1;
            resetGraph(mid);
            if (dinic() >= k)
                r = mid - 1;
            else
                l = mid + 1;
        }
        printf("%d\n", r + 1);
    }
    return 0;
}

最大流

ZOJ 2760 How Many Shortest Path

Posted on

暑假集训第一天,早上看了一下支配树,结果表示完全不会,看不懂……不得不回老本写起了网络流

题意:
给你一个距离矩阵,问你完全不重叠的最短路数目。

思路:
完全不重叠,意为每条边只能走一次,我以网络流建模,对于每条在最短路径内的边的流量设置为1,跑出来的结果即题意所求。这个很自然想得到吧
关键就在于如何判断一条边是否属于最短路径。
这里给出一种比较好的方法,对于一条边 ( u , v ) ,如果 min ( st , u ) + ( u,v ) + min ( v , en ) 等于最短路径长度,那么这条边就属于最短路径 这也是很显然的

注: 如果起点与终点相同,则直接输出inf ,本人英语不好,看了一下题意我还意淫成了 如果存在( st , en ) 就输出inf。
结果我tle了4发……
因为一直wa我看了一下其他题解,居然有人以自环>=0为理由A不了……我感觉很奇怪。如果自环权值非负,那么正权值自环必定不在最短路径中,而零自环加不加都没有任何影响。

其他的就是代码美丑的问题了。

AC code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
using namespace std;
const int maxn = 105;
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 mat[maxn][maxn];
int diss[maxn], dist[maxn], cpmat[maxn][maxn];

struct node {
    int flow;
    int to;
    int nxt;
} edges[4 * maxn * maxn];

void addEdge(int u, int v, int f)
{
    edges[idx].to = v;
    edges[idx].flow = f;
    edges[idx].nxt = head[u];
    head[u] = 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 <= n; i++)
            cur[i] = head[i];
        while ((cflow = dfs(st, inf)))
            ans += cflow;
    }
    return ans;
}

void spfa(int s, int* dis, int sp[maxn][maxn])
{
    bool vis[maxn];
    int que[maxn];
    memset(vis, false, sizeof vis);
    for (int i = 0; i <= n; i++)
        dis[i] = inf;
    dis[s] = 0;
    vis[s] = true;
    int l = 0, r = 1;
    que[0] = s;
    while (l < r) {
        int u = que[l++];
        vis[u] = 0;
        for (int v = 1; v <= n; v++) {
            if (dis[v] > dis[u] + sp[u][v]) {
                dis[v] = dis[u] + sp[u][v];
                if (!vis[v]) {
                    vis[v] = 1;
                    que[r++] = v;
                }
            }
        }
    }
}

bool createGraph()
{
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cpmat[i][j] = mat[j][i];
    memset(head, -1, sizeof head);
    idx = 0;
    st++, en++;
    spfa(st, diss, mat);
    spfa(en, dist, cpmat);
    //printf("dist --> %d %d %d %d\n", dist[1], dist[2], dist[3], dist[4]);
    int min_len = diss[en];
    if (min_len == inf)
        return false;
    for (int u = 1; u <= n; u++)
        for (int v = 1; v <= n; v++) {
            if (diss[u] + mat[u][v] + dist[v] == min_len) {
                //printf("%d %d %d %d %d\n", diss[u], mat[u][v], dist[v], u, v);
                addEdge(u, v, 1);
                addEdge(v, u, 0);
            }
        }
    return true;
}

int main()
{
    int len;
    while (scanf("%d", &n) != EOF) {
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++) {
                scanf("%d", &len);
                mat[i][j] = len < 0 ? inf : len;
            }
        scanf("%d %d", &st, &en);
        if (st == en) {
            puts("inf");
            continue;
        }
        if (createGraph())
            printf("%d\n", dinic());
        else
            puts("0");
    }
    return 0;
}