解題區/解題區 - UVa

UVa 1659 - Help Little Laura

contents

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

Problem

平面上有 N 個點，並且給定數條有向邊，在這個遊戲中，必須從某個點出發，沿著邊回到起點。每一條邊最多經過一次，而點可以重複走。

每經過一條邊，可以獲益每單位長 X 的利益，但是使用一條邊的成本為 Y。

請問最大獲益為何？

Sample Input

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

Sample Output

1
2
3
Case 1: 16.00 
Case 2: 0.00 
Case 3: 522.18

Solution

目標將每一個點調整 indeg = outdeg，要將多餘的邊捨去，只要滿足 indeg = outdeg，則可以表示平面上有數個尤拉環道。

接著建造最少費用流的模型，來捨去掉多餘的邊。當存有邊 e(i->j) 時，outdeg[i]++, indeg[j]++，一開始選擇所有 cost(e(i->j)) > 0 的邊，作為初始盤面，對於 cost(e(i->j)) < 0 先不選，選擇獲益為負的結果並不好。

如果 cost(e(i->j)) > 0，建造邊 i->j, flow: 1, cost: cost(e(i->j))，假使在最少費用流中選擇這一條邊時，就會將 deg 數量減少。對於 cost(e(i->j)) < 0 一開始並沒有在盤面上，如果流經這一條邊，則說明將會增加這一條邊。

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
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <queue>
#include <functional>
#include <deque>
#include <algorithm>
using namespace std;
#define eps 1e-8
struct Node {
    int x, y, cap;
    double cost;// x->y, v
    int next;
} edge[1000005];
int e, head[600], prev[600], record[600], inq[600];
double dis[600];
void addEdge(int x, int y, int cap, double 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++;
}
double mincost(int s, int t, int n) {
    double mncost = 0;
    int flow, totflow = 0;
    int i, x, y;
    double oo = 1e+30;
    while(1) {
    	for (int i = 0; i <= n; i++)
    		dis[i] = oo;
        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 = 0x3f3f3f3f;
        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 cases = 0;
    int N, X, Y;
    int x[128], y[128], u;
    while (scanf("%d %d %d", &N, &X, &Y) == 3 && N) {
    	vector<int> g[128];
    	for (int i = 1; i <= N; i++) {
    		scanf("%d %d", &x[i], &y[i]);
    		while (scanf("%d", &u) == 1 && u)
    			g[i].push_back(u);
        } 
        
    	e = 0;
        memset(head, -1, sizeof(head));	
        int deg[128] = {};
        double sumCost = 0;
        for (int i = 1; i <= N; i++) {
            for (int j = 0; j < g[i].size(); j++) {
                u = g[i][j];
                double d = hypot(x[i] - x[u], y[i] - y[u]);
                double cost = d * X - Y;
                if (cost < 0) {
                    addEdge(u, i, 1, -cost);
                } else {
                    sumCost += cost;
                    addEdge(i, u, 1, cost);
                    deg[u]--, deg[i]++;
                }
            }
        }
        int source = 0, sink = N + 1;
        for (int i = 1; i <= N; i++) {
            if (deg[i] > 0)	addEdge(source, i, deg[i], 0);
            if (deg[i] < 0)	addEdge(i, sink, -deg[i], 0);
        }
        double mncost = mincost(source, sink, N+1);
        printf("Case %d: %.2lf\n", ++cases, sumCost - mncost + eps);
    }
    return 0;
}
/*
4 5 1 
0 0 2 3 0 
1 0 3 4 0 
1 1 4 0 
0 1 1 0 
1 2 1 
0 0 0 
10 7 2 
0 0 2 4 0 
5 0 3 0 
5 10 4 10 0 
2 3 5 0 
7 5 6 0 
0 11 1 0 
8 0 10 5 0 
18 3 7 0 
14 5 8 1 0 
12 9 9 0 
0
*/