MYF

UVa 1658 Admiral

Posted on | In | | Visitors

题目链接

UVa 1658

方法：拆点法 + 最小费用最大流

题目分析

题目大意

给出一个有向带权图，求从起点到终点的两条不相交路径使得权值和最小。

解析

把除起点和终点以外的点拆成两个点i和i’，然后在这两点之间连一条容量为1，费用为0的边。这样就保证了每个点最多经过一次。

其他有向边的容量也是1

然后求从起点到终点的流量为2(这样就保证了是两条路径)的最小费用流。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <iomanip>
#include <bitset>
#include <cstring>
#include <iostream>
#include <iosfwd>
#include <deque>
#include <algorithm>
#define Memset(a,val) memset(a,val,sizeof(a))
#define PI acos(-1.0)
#define PB push_back
#define MP make_pair
#define rt(n)       (i == n ? '\n' : ' ')
#define hi         printf("Hi----------\n")
#define IN freopen("input.txt","r",stdin);
#define OUT freopen("output.txt","w",stdout);
#define debug(x) cout<<"Debug : ---"<<x<<"---"<<endl;
#define debug2(x,y) cout<<"Debug : ---"<<x<<" , "<<y<<"---"<<endl;
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;

const int mod=1000000007;
const int INF=0x3f3f3f3f;
const double eps=1e-8;

const int Vmax=2005; //需要拆点的话记得加倍
namespace MCMF{
    struct Edge{
        int from,to,cap,flow,cost;
        Edge(int u,int v,int c,int f,int w):from(u),to(v),cap(c),flow(f),cost(w){}
    };
    
    int n,m;
    vector<Edge>edges;
    vector<int>G[Vmax];
    int inq[Vmax];  //是否在队列中
    int d[Vmax];    //Bellman-Ford
    int p[Vmax];    //上一条弧
    int a[Vmax];    //可改进量
    
    void init(int _Vsz){
        n=_Vsz;
        for(int i=0;i<=n;i++) G[i].clear();
        edges.clear();
    }
    
    void adde(int from,int to,int cap,int cost){
        edges.push_back(Edge(from, to, cap, 0, cost));
        edges.push_back(Edge(to, from, 0, 0, -cost));
        m=edges.size();
        G[from].push_back(m-2);
        G[to].push_back(m-1);
    }
    
    bool SPFA(int s,int t,int& flow,long long& cost){
        for(int i=0;i<=n;i++) d[i]=INF;
        memset(inq, 0, sizeof(inq));
        d[s]=0;
        inq[s]=1;
        p[s]=0;
        a[s]=INF;
        
        queue<int>q;
        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.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]=1;
                    }
                }
            }
        }
        if(d[t]==INF) return false; //s-t 不联通，失败退出
        flow+=a[t];
        cost+=(long long)d[t]*(long long)a[t];
        for(int u=t;u!=s;u=edges[p[u]].from){
            edges[p[u]].flow+=a[t];
            edges[p[u]^1].flow-=a[t];
        }
        return true;
    }
    
    int MincostMaxflow(int s,int t,long long& cost){
        int flow=0;
        cost=0;
        while(SPFA(s, t, flow, cost));
        return flow;
    }
}
int main(){
    int n,m,x,y,w;
    while (scanf("%d%d",&n,&m)!=EOF) {
        // 拆点
        MCMF::init(2*n);
        MCMF::adde(1, n+1, 2, 0);
        MCMF::adde(n, 2*n, 2, 0);
        for (int i=2; i<n; i++) {
            MCMF::adde(i, i+n, 1, 0);
        }
        
        //加边
        for (int i=1; i<=m; i++) {
            scanf("%d%d%d",&x,&y,&w);
            MCMF::adde(x+n, y, 1, w);
        }
        
        //求结果
        ll mc;
        MCMF::MincostMaxflow(1, n+n, mc);
        cout<<mc<<endl;
    }
    return 0;
}