解題區/解題區 - UVa

UVa 1349 - Optimal Bus Route Design

contents

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

Problem

每一條公車路線都是環狀，要求每一個站只在一條公車路線上，給定站與站之間的連通花費，求公車路線最少為何。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
3 
2 2 3 1 0 
1 1 3 2 0 
1 3 2 7 0  
8 
2 3 3 1 0 
3 3 1 1 4 4 0
1 2 2 7 0 
5 4 6 7 0 
4 4 3 9 0 
7 4 8 5 0 
6 2 5 8 8 1 0
6 6 7 2 0
3 
2 1 0 
3 1 0 
2 1 0
0

Sample Output

1
2
3
7 
25 
N

Solution

看起來先拆點，要求每一個點變成出點跟入點，要求每一個出點都能配對一個入點，這麼一來能保證每一個點都能走出去，進而形成環狀。

那麼這就是一題完美帶權二分匹配判定。

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
#include <stdio.h>
#include <string.h>
#include <queue>
#include <functional>
#include <deque>
#include <algorithm>
using namespace std;
#define MAXN 2048
#define MAXM 1048576
struct Node {
    int x, y, cap, cost;// x->y, v
    int next;
} edge[MAXM];
class MinCost {
public:
    int e, head[MAXN], dis[MAXN], pre[MAXN], record[MAXN], inq[MAXN];
    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++;
    }
    pair<int, 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;
                        pre[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 = pre[x]) {
                int ri = record[x];
                flow = min(flow, edge[ri].cap);
            }
            for(x = t; x != s; x = pre[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 make_pair(mncost, totflow);
    }
    void init(int n) {
        e = 0;
        for (int i = 0; i <= n; i++)
            head[i] = -1;
    }
} g;
int main() {
    int n, x, y, v;
    while (scanf("%d", &n) == 1 && n) {
        g.init(2 * n + 2);
        int source = 2 * n, sink = 2 * n + 1;
        for (int i = 0; i < n; i++) {
            x = i;
            while (scanf("%d", &y) == 1 && y) {
                scanf("%d", &v);
                y--;
                g.Addedge(2*x, 2*y+1, 1, v);
            }
            g.Addedge(source, 2*i, 1, 0);
            g.Addedge(2*i+1, sink, 1, 0);
        }
        pair<int, int> ret = g.mincost(source, sink);
        if (ret.second == n)
            printf("%d\n", ret.first);
        else
            puts("N");
    }
    return 0;
}