PowerOJ 1683 费用流

图论 费用流

PowerOJ 1683 费用流

从起点到终点，求两条边不相交的路径，使得总长度最短。输出最短的总长度

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e3 + 5;
const int maxm = 1e5 + 5;
struct EDGE
{
    int to, next, flow, cost;
    EDGE() {}
    EDGE(int to, int next, int flow, int cost) : to(to), next(next), flow(flow), cost(cost) {}
} edge[maxm];
int head[maxn], edgecnt, maxNodeNum;
void init()
{
    memset(head, -1, sizeof(head));
    edgecnt = 0;
    maxNodeNum = 0;
}
void AddEdge(int st, int en, int flow, int cost)
{
    edge[edgecnt] = EDGE(en, head[st], flow, cost);
    head[st] = edgecnt++;
    edge[edgecnt] = EDGE(st, head[en], 0, -cost);
    head[en] = edgecnt++;
    maxNodeNum = max(maxNodeNum, max(st, en));
}
int pre[maxn], dis[maxn];
bool SPFA(int st, int en)
{
    static bool vis[maxn];
    memset(dis, 0x7F, sizeof(int) * (maxNodeNum + 1));
    dis[st] = 0;
    queue<int> q;
    q.push(st);
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        vis[u] = 0;
        for (int i = head[u]; ~i; i = edge[i].next)
        {
            int v = edge[i].to;
            if (edge[i].flow && dis[v] > dis[u] + edge[i].cost)
            {
                if (!vis[v])
                {
                    vis[v] = true;
                    q.push(v);
                }
                dis[v] = dis[u] + edge[i].cost;
                pre[v] = i;
            }
        }
    }
    return dis[en] != 0x7F7F7F7F;
}
pair<int, int> solve(int st, int en, int maxFlow = INT_MAX)
{
    int cost = 0, flow = 0;
    while (SPFA(st, en))
    {
        int d = maxFlow - flow;
        for (int u = en; u != st; u = edge[pre[u] ^ 1].to)
            d = min(d, edge[pre[u]].flow);
        flow += d;
        for (int u = en; u != st; u = edge[pre[u] ^ 1].to)
        {
            edge[pre[u]].flow -= d;
            edge[pre[u] ^ 1].flow += d;
            cost += edge[pre[u]].cost * d;
        }
        if (flow == maxFlow) break;
    }
    return make_pair(cost, flow);
}
int main()
{
    int n, m;
    while (~scanf("%d %d", &n, &m))
    {
        init();
        while (m--)
        {
            int f, t, j;
            scanf("%d %d  %d", &f, &t, &j);
            AddEdge(f, t, 1, j);
            AddEdge(t, f, 1, j);
        }
        AddEdge(0, 1, 2, 0);
        printf("%d\n", solve(0, n).first);
    }
    return 0;
}