UVa(1658)，Admiral，海军上将，拆点，MCMF

题目链接：https://uva.onlinejudge.org/external/16/1658.pdf

题意：求1到N的两条路(不能相交)，距离和最小。

分析：

第一次做拆点，有点意思。刚开始一直出不了结果，原来是初始化少了一点。

注意的是：我想我的建图方法较刘汝佳的方法有一点小区别，加一个源点S,和汇点T，刘汝佳的方法是把2—v-1拆掉。

然后这里拆点有些技巧。还是阳哥教我的。

UVa(1658)，Admiral，海军上将，拆点，MCMF

#include <iostream>

#include <stdio.h>

#include <cstring>

#include <vector>

#include <queue>

#define INF 0x3f3f3f3f

using namespace std;

const int maxn =  + ;

struct Edge

{

    int from,to,cap,flow,cost;

    Edge() {}

    Edge(int a,int b,int c,int d,int e):from(a),to(b),cap(c),flow(d),cost(e) {}

};

struct MCMF

{

    int n,m,s,t;

    vector<Edge> edges;

    vector<int> g[maxn];

    int inq[maxn];

    int d[maxn];

    int p[maxn];

    int a[maxn];

    void init(int n)

    {

        this->n =n;

        for(int i=; i<n; i++)g[i].clear();

        edges.clear();

    }

    void addedge(int from,int to,int cap,int cost)

    {

        Edge e1= Edge(from,to,cap,,cost), e2= Edge(to,from,,,-cost);

        edges.push_back(e1);

        edges.push_back(e2);

        m=edges.size();

        g[from].push_back(m-);

        g[to].push_back(m-);

    }

    bool spfa(int s,int t, int & flow,int & cost)

    {

        for(int i=; i<n; i++)

            d[i]=INF;

        memset(inq,,sizeof(inq));

        d[s]=;

        inq[s]=;

        p[s]=;

        a[s]=INF;

        queue<int>q;

        q.push(s);

        while(!q.empty())

        {

            int u=q.front();

            q.pop();

            inq[u]=;

            for(int i=; i<g[u].size(); i++)

            {

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

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

                {

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

                    p[e.to]=g[u][i];

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

                    if(!inq[e.to])

                    {

                        q.push(e.to);

                        inq[e.to]=;

                    }

                }

            }

        }

        if(d[t]==INF)

            return false;

        flow+=a[t];

        cost+=a[t]*d[t];

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

        {

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

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

        }

        return true;

    }

    int  MincostMaxflow(int s,int t)

    {

        int flow=,cost =;

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

        return cost;

    }

} sol;

int main()

{

    freopen("input.txt","r",stdin);

    int n, m;

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

    {

        int s = ,t = *n+;

        sol.init(t+);

        for(int i=;i<=n;i++)

            sol.addedge(i+n,i,,);

        sol.addedge(,+n,,);

        sol.addedge(n,*n,,);

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

        {

            int u,v,c;

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

            sol.addedge(u,v+n,,c);

        }

        sol.addedge(,,,);

        sol.addedge(*n,t,,);

        printf("%d\n",sol.MincostMaxflow(,t));

    }

    return ;

}

秒客网

UVa(1658)，Admiral，海军上将，拆点，MCMF

相关文章