POJ 2455 Secret Milking Machine

网络流复习计划第三题 传送门
啊，这道题的建图完全是自己想的，虽然花的时间比较长，但是还是算是1A了(交了第一发忘记删了文件输入……)，老实说，A的有点意外呀……

题意：
小气的农场主发现了个大宝贝并把他藏在了n点，他家在1点，总共n个点有若干条路，谨慎的农场主怕自己的宝贝被偷走，于是要从家里出发，结点不重复的走到大宝贝t次。问你在农场主所走的路径中最长的两点距离最短为多少。

思路：
当然还是二分啦！
先是建立距离图。再二分距离，再额外建图，若两点距离小于等于二分值 limit ，则建立双向建边，流量均为 1 。再跑一次dinic，如果总流量大于等于 t ，说明这个limit是满足条件的，我们再尝试缩小它，否则，增大它。

注意： 此题存在重边，存在重边的图，必须用邻接表存储。为什么来着，突然忘了，以后再补

//wordpress的markdown插件有个bug，代码太长的话头文件就显示不了，现在暂时分开……

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

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

int n, m, c, idx, nidx, st, en;
int dis[maxn][maxn];
int level[maxn], cur[maxn], que[maxn * maxn];
int head[maxn], nhead[maxn];

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

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

inline void addNetEdge(int u, int v)
{
    nedges[nidx].to = v;
    nedges[nidx].nxt = nhead[u];
    nedges[nidx].flow = 1;
    nhead[u] = nidx++;

    nedges[nidx].to = u;
    nedges[nidx].nxt = nhead[v];
    nedges[nidx].flow = 1;
    nhead[v] = nidx++;
}

inline void createGragh(int limit)
{
    memset(nhead, -1, sizeof head);
    nidx = 0;
    for (int i = 1; i <= n; i++)
        for (int u = head[i]; ~u; u = edges[u].nxt) {
            if (edges[u].flow <= limit) {
                addNetEdge(i, edges[u].to);
            }
        }
}

bool bfs()
{
    memset(level, -1, sizeof level);
    que[0] = st;
    level[st] = 0;
    int l = 0, r = 1, u, v;
    while (l < r) {
        u = que[l++];
        for (int i = nhead[u]; ~i; i = nedges[i].nxt) {
            v = nedges[i].to;
            if (nedges[i].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& i = cur[u]; ~i; i = nedges[i].nxt) {
        int v = nedges[i].to;
        if (nedges[i].flow > 0 && level[v] == level[u] + 1
            && (cflow = dfs(v, min(low, nedges[i].flow)))) {
            nedges[i].flow -= cflow;
            nedges[i ^ 1].flow += cflow;
            return cflow;
        }
    }
    return 0;
}

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

void init()
{
    idx = 0;
    memset(head, -1, sizeof head);
}

int main()
{
    int u, v, w;
    while (scanf("%d %d %d", &n, &m, &c) != EOF) {
        init();
        int l = 0, r = 0, mid;
        while (m--) {
            scanf("%d %d %d", &u, &v, &w);
            addEdge(u, v, w);
            r = max(r, w);
        }
        while (l <= r) {
            mid = (l + r) >> 1;
            createGragh(mid);
            if (dinic() >= c)
                r = mid - 1;
            else
                l = mid + 1;
        }
        printf("%d\n", r + 1);
    }
    return 0;
}