uva 1658 Admiral

题目大意：在图中找出两条没有交集的线路，要求这两条线路的费用最小。

解题思路：还是拆点建图的问题。

首先每一个点都要拆成两个点。比如a点拆成a->a’。起点和终点的两点间的容量为2费用为0，保证了仅仅找出两条线路。其余点的容量为1费用为0，保证每点仅仅走一遍，两条线路无交集。然后依据题目给出的要求继续建图。每组数据读入a, b, c， 建立a’到b的边容量为1， 费用为c。图建完之后，用bellman-ford来实现MCMF。

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <cstdlib>

#include <queue>

using namespace std;

typedef long long ll;

const int N = 2005;

const int INF = 0x3f3f3f3f;

int n, m, s, t;

int a[N], pre[N], d[N], inq[N]; 

struct Edge{

    int from, to, cap, flow;

    ll cos;

};

vector<Edge> edges;

vector<int> G[N];

void init() {

    for (int i = 0; i < 2 * n; i++) G[i].clear();

    edges.clear();

}

void addEdge(int from, int to, int cap, int flow, ll cos) {

    edges.push_back((Edge){from, to, cap, 0, cos});

    edges.push_back((Edge){to, from, 0, 0, -cos});

    int m = edges.size();

    G[from].push_back(m - 2);

    G[to].push_back(m - 1);

}

void input() {

    addEdge(1, n + 1, 2, 0, 0);

    for (int i = 2; i <= n - 1; i++) {

        addEdge(i, i + n, 1, 0, 0);

    }

    addEdge(n, 2 * n, 2, 0, 0);

    int u, v;

    ll c;

    for (int i = 0; i < m; i++) {

        scanf("%d %d %lld", &u, &v, &c);

        addEdge(u + n, v, 1, 0, c);

    }

}

int BF(int s, int t, int& flow, ll& cost) {

    queue<int> Q;

    memset(inq, 0, sizeof(inq));

    memset(a, 0, sizeof(a));

    memset(pre, 0, sizeof(pre));

    for (int i = 0; i <= 2 * n + 1; i++) d[i] = INF;

    d[s] = 0;

    a[s] = INF;

    inq[s] = 1;

    int flag = 1;

    pre[s] = 0;

    Q.push(s);

    while (!Q.empty()) {

        int u = Q.front(); Q.pop();

        inq[u] = 0;

        for (int i = 0; i < G[u].size(); i++) {

            Edge &e = edges[G[u][i]];

            if (e.cap > e.flow && d[e.to] > d[u] + e.cos) {

                d[e.to] = d[u] + e.cos;

                a[e.to] = min(a[u], e.cap - e.flow);

                pre[e.to] = G[u][i];

                if (!inq[e.to]) {

                    inq[e.to] = 1;

                    Q.push(e.to);

                }

            }

        }

        flag = 0;

    }

    if (d[t] == INF) return 0;

    flow += a[t];

    cost += (ll)d[t] * (ll)a[t];

    for (int u = t; u != s; u = edges[pre[u]].from) {

        edges[pre[u]].flow += a[t];

        edges[pre[u]^1].flow -= a[t];

    }

    return 1;

}

int MCMF(int s, int t, ll& cost) {

    int flow = 0;

    cost = 0;

    while (BF(s, t, flow, cost));

    return flow;

}

int main() {

    while (scanf("%d %d", &n, &m) == 2) {

        s = 1, t = 2 * n;

        ll cost;

        init();

        input();

        MCMF(s, t, cost);

        printf("%lld\n", cost);

    }

    return 0;

}