解題區/解題區 - UVa

UVa 12821 - Double Shortest Paths

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

給一張圖，點與點之間有條有向路徑，每條路徑上有兩個權重，第一次從起點到終點經過這條邊時，消耗 d，而如果在第二次經過時，將消耗 d + a。保證 d <= d+a。(第二次經過同一條邊時，困難度會增加。)

求兩條從起點到終點的路徑花費最小。

Sample Input

1
2
3
4
5
6
7
8
9
10
4 4
1 2 5 1
2 4 6 0
1 3 4 0
3 4 9 1
4 4
1 2 5 10
2 4 6 10
1 3 4 10
3 4 9 10

Sample Output

1
2
Case 1: 23
Case 2: 24

Solution

直接套用最少費用流，對於輸入給定的一條邊 u->v，增加兩條容量為 1，路徑花費分別為 d 和 d+a，求起點到終點流量 = 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
#include <stdio.h>
#include <string.h>
#include <queue>
#include <deque>
using namespace std;
struct Node {
    int x, y, cap, cost;// x->y, v
    int next;
} edge[100005];
int e, head[505], dis[505], prev[505], record[505], inq[505];
void addEdge(int x, int y, int cap, int cost) {
    edge[e].x = x, edge[e].y = y, edge[e].cap = cap, edge[e].cost = cost;
    edge[e].next = head[x], head[x] = e++;
    edge[e].x = y, edge[e].y = x, edge[e].cap = 0, edge[e].cost = -cost;
    edge[e].next = head[y], head[y] = e++;
}
int mincost(int s, int t) {
    int mncost = 0, flow, totflow = 0;
    int i, x, y;
    while(1) {
        memset(dis, 63, sizeof(dis));
        int oo = dis[0];
        dis[s] = 0;
        deque<int> Q;
        Q.push_front(s);
        while(!Q.empty()) {
            x = Q.front(), Q.pop_front();
            inq[x] = 0;
            for(i = head[x]; i != -1; i = edge[i].next) {
                y = edge[i].y;
                if(edge[i].cap > 0 && dis[y] > dis[x] + edge[i].cost) {
                    dis[y] = dis[x] + edge[i].cost;
                    prev[y] = x, record[y] = i;
                    if(inq[y] == 0) {
                        inq[y] = 1;
                        if(Q.size() && dis[Q.front()] > dis[y])
                            Q.push_front(y);
                        else
                            Q.push_back(y);
                    }
                }
            }
        }
        if(dis[t] == oo)
            break;
        flow = oo;
        for(x = t; x != s; x = prev[x]) {
            int ri = record[x];
            flow = min(flow, edge[ri].cap);
        }
        for(x = t; x != s; x = prev[x]) {
            int ri = record[x];
            edge[ri].cap -= flow;
            edge[ri^1].cap += flow;
            edge[ri^1].cost = -edge[ri].cost;
        }
        totflow += flow;
        mncost += dis[t] * flow;
    }
    return mncost;
}
int main() {
    int n, m, cases = 0;
    int x, y, d, a;
    while(scanf("%d %d", &n, &m) == 2) {
        e = 0;
        memset(head, -1, sizeof(head));
        int source = n + 1, sink = n + 2;
        for (int i = 0; i < m; i++) {
        	scanf("%d %d %d %d", &x, &y, &d, &a);
        	addEdge(x, y, 1, d);
        	addEdge(x, y, 1, d + a);
        }
        addEdge(source, 1, 2, 0);
        addEdge(n, sink, 2, 0);
        printf("Case %d: %d\n", ++cases, mincost(source, sink));
    }
    return 0;
}
/*
4 4
1 2 5 1
2 4 6 0
1 3 4 0
3 4 9 1
4 4
1 2 5 10
2 4 6 10
1 3 4 10
3 4 9 10
*/