「poj 2135」Farm Tour (最小费用最大流)

poj 2135
题意：一个无向图，起点终点固定，来回一次，不重复任何一条道路，求最小道路数(就是路径长度)

这种最短路没法解决的可以想想网络流，因为网络流的最小费用和最短路有相似点，而可以通过容量等方式限制最短路的形式。

设一个超级源和一个超级汇，超级源连$1$点边$(cap=2, w=0)$, $n$点连超级汇边$(cap=2, w=0)$
然后对于图中的一条边$(x,y)$，连边$(cap=1,w=v_{x,y})$
这个容量就是限制路径条数的，相当于走了一次以后即割断不能再走，而连接超级源汇的边容量为$2$，为的是找到两条路径。

知识点：
1、最短路没法解决的可以想想网络流，因为网络流的最小费用和最短路有相似点，而可以通过容量等方式限制最短路的形式。

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db long double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {

    const int INF = 2147483647ll;

    struct edge {
        int u, v, cap, w, nxt;
    } ed[500000 + 5];

    int n, m, hd[10000 + 5], en, s, t, ans, V;
    int incf[10000 + 5], dis[10000 + 5], pre[10000 + 5], vis[10000 + 5];

    int ID(int x, int y) {return (x - 1) * m + y;}
    void ins_c(int u, int v, int cap, int w) {
        ed[++en] = (edge){u, v, cap, w, hd[u]}, hd[u] = en;
        ed[++en] = (edge){v, u, 0, -w, hd[v]}, hd[v] = en;
    }

    queue<int > q;
    bool spfa() {
        for (int i = 0; i <= V; ++i) incf[i] = INF, dis[i] = INF, pre[i] = -1, vis[i] = 0;
        vis[s] = 1, dis[s] = 0, q.push(s);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            vis[u] = 0;
            for (int i = hd[u]; i >= 0; i = ed[i].nxt) {
                edge &e = ed[i];
                if (e.cap && dis[u] != -INF && dis[e.v] > dis[u] + e.w) {
                    dis[e.v] = dis[u] + e.w;
                    incf[e.v] = min(incf[u], e.cap);
                    pre[e.v] = i;
                    if (!vis[e.v]) vis[e.v] = 1, q.push(e.v);
                }
            }
        }
        return dis[t] != INF;
    }
    void update() {
        int now = pre[t];
        while (now != -1) {
            ed[now].cap -= incf[t], ed[now ^ 1].cap += incf[t];
            now = pre[ed[now].u];
        }
        ans += incf[t] * dis[t];
    }

    void clean() {
        ans = 0, en = -1, ms(hd, -1);
    }
    int solve() {

        clean();

        scanf("%d%d", &n, &m);

        s = n + 1, t = V = n + 2;
        ins_c(s, 1, 2, 0);
        ins_c(n, t, 2, 0);

        for (int x, y, v, i = 1; i <= m; ++i) {
            scanf("%d%d%d", &x, &y, &v);
            ins_c(x, y, 1, v), ins_c(y, x, 1, v);
        }

        while (spfa()) update();

        cout << ans;

        return 0;
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}