vjudge传送门[here]

题目大意:给一个有(3≤v≤1000)个点e（3≤e≤10000）条边的有向加权图，求1~v的两条不相交（除了起点和终点外没有公共点）的路径，使权值和最小。

正解是吧2到v-1的每个点拆成两个点，中间连一条容量为1，费用为0的边，然后求1到v的流量为2的最小费用流就行了。

### Code

```  1 /**
2  * Uva
3  * Problem#1658
4  * Accepted
5  */
6 #include<iostream>
7 #include<cstdio>
8 #include<cctype>
9 #include<cstring>
10 #include<cstdlib>
11 #include<fstream>
12 #include<sstream>
13 #include<algorithm>
14 #include<map>
15 #include<set>
16 #include<queue>
17 #include<vector>
18 #include<stack>
19 using namespace std;
20 typedef bool boolean;
21 #define INF 0xfffffff
22 #define smin(a, b) a = min(a, b)
23 #define smax(a, b) a = max(a, b)
24 template<typename T>
26     char x;
27     int aFlag = 1;
28     while(!isdigit((x = getchar())) && x != ‘-‘ && ~x);
29     if(x == -1){
30         return false;
31     }
32     if(x == ‘-‘){
33         x = getchar();
34         aFlag = -1;
35     }
36     for(u = x - ‘0‘; isdigit((x = getchar())); u = (u << 1) + (u << 3) + x - ‘0‘);
37     ungetc(x, stdin);
38     u *= aFlag;
39     return true;
40 }
41
42 ///map template starts
43 typedef class Edge{
44     public:
45         int end;
46         int next;
47         int cap;
48         int flow;
49         int cost;
50         Edge(const int end = 0, const int next = 0, const int cap = 0, const int flow = 0, const int cost = 0):end(end), next(next), cap(cap), flow(flow), cost(cost){}
51 }Edge;
52
53 typedef class MapManager{
54     public:
55         int ce;
56         int *h;
57         Edge *edge;
58         MapManager(){}
59         MapManager(int points, int limit):ce(0){
60             h = new int[(const int)(points + 1)];
61             edge = new Edge[(const int)(limit + 1)];
62             memset(h, 0, sizeof(int) * (points + 1));
63         }
64         inline void addEdge(int from, int end, int cap, int flow, int cost){
65             edge[++ce] = Edge(end, h[from], cap, flow, cost);
66             h[from] = ce;
67         }
68         inline void addDoubleEdge(int from, int end, int cap, int cost){
69             addEdge(from, end, cap, 0, cost);
70             addEdge(end, from, cap, cap, -cost);
71         }
72         Edge& operator [](int pos){
73             return edge[pos];
74         }
75         inline int reverse(int pos){
76             return (pos & 1) ? (pos + 1) : (pos - 1);
77         }
78         inline void clean(){
79             delete[] h;
80             delete[] edge;
81             ce = 0;
82         }
83 }MapManager;
84 #define m_begin(g, i) (g).h[(i)]
85 /// map template ends
86
87 int n, m;
88 MapManager g;
89
90 inline boolean init(){
93     g = MapManager(n * 2, m * 2 + n * 2);
94     for(int i = 1, a, b, w; i <= m; i++){
98         g.addDoubleEdge(a + n, b, 1, w);
99     }
100     for(int i = 1; i <= n; i++){            //拆点
101         g.addDoubleEdge(i, i + n, 1, 0);
102     }
103     return true;
104 }
105
106 int* dis;
107 boolean* visited;
108 int* last;
109 int* laste;
110 int* mflow;
111 int cost;
112 int s, t;
113 queue<int> que;
114 int sizee;
115
116 inline void spfa(){
117     memset(dis, 0x7f, sizeof(int) * (sizee));
118     memset(visited, false, sizeof(boolean) * (sizee));
119     que.push(s);
120     last[s] = 0;
121     dis[s] = 0;
122     laste[s] = 0;
123     mflow[s] = INF;
124     visited[s] = true;
125     while(!que.empty()){
126         int e = que.front();
127         que.pop();
128         visited[e] = false;
129         for(int i = m_begin(g, e); i != 0; i = g[i].next){
130             int &eu = g[i].end;
131             if(dis[e] + g[i].cost < dis[eu] && g[i].flow < g[i].cap){
132                 dis[eu] = dis[e] + g[i].cost;
133                 last[eu] = e;
134                 laste[eu] = i;
135                 mflow[eu] = min(g[i].cap - g[i].flow, mflow[e]);
136                 if(!visited[eu] && eu != t){
137                     que.push(eu);
138                     visited[eu] = true;
139                 }
140             }
141         }
142     }
143     for(int i = t; i != s; i = last[i]){
144         g[laste[i]].flow += mflow[t];
145         g[g.reverse(laste[i])].flow -= mflow[t];
146         cost += mflow[t] * g[laste[i]].cost;
147     }
148 }
149
150 inline void minCostFlow(){
151     s = 1 + n, t = n, sizee = 2 * n + 1;
152     dis = new int[(const int)(sizee)];
153     visited = new boolean[(const int)(sizee)];
154     last = new int[(const int)(sizee)];
155     laste = new int[(const int)(sizee)];
156     mflow = new int[(const int)(sizee)];
157     spfa();
158     spfa();
159 }
160
161 inline void solve(){
162     cost = 0;
163     minCostFlow();
164     printf("%d\n", cost);
165     g.clean();
166 }
167
168 int main(){
169     while(init()){
170         solve();
171     }
172     return 0;
173 }```

(0)
(0)

0条