首页 > itarticle > poi 2010 bridges 题解 题解： 代码：

poi 2010 bridges 题解 题解： 代码：

admin 11月 13, 2020 0

题目描述

San Bytecisco is a beautifully situated coastal town. It consists of img small, yet densely populated islands, numbered from img to img. Certain islands are connected with bridges, used for (bidirectional) road traffic. Each pair of islands can be connected with at most one bridge. The islands are connected in such a way that every island can be reached from every other by using the bridges only.

Byteasar and Bytie are going for a bike trip in San Bytecisco. The will start their ride at the island no. 1. They intend to visit every island, while passing along every bridge once and ending the trip where it began, i.e., the island no. 1. Being quite seasoned riders, they expect some serious trouble from… the wind! After all, it is very windy along the coast, and especially so on the bridges between the islands. Obviously, depending on its speed and direction, the wind makes it hard to cross the bridge in different extent for either direction. For simplicity we will assume for every bridge and direction of crossing, the opposing wind speed is constant.

Help Byteasar and Bytie to find a route as they desire that will in addition be the least tiresome. Byteasar and Bytie agreed on the maximum opposing wind speed as a measure of a route’s tiresomeness.

Input

In the first line of the standard input there are two integers separated by a single space: img and img (img, img), denoting the number of islands and the number of bridges in San Bytecisco respectively. The islands are numbered from 1 to img, while the bridges from 1 to img. The following img lines specify the bridges. The line no. img contains four integers img, img, img, img (img, img, img), separated by single spaces. These denote that the bridge no. img connects the islands no. img and img. The opposing wind speeds are img when one goes moves from img to img, and img if one goes from img to img.

Output

If there is no route satisfying the requirements of the daring two riders, the first and only line of the standard output should hold the word NIE (no in Polish). Otherwise, the output should have two lines, specifying the least tiresome route over San Bytecisco. The first line should hold the maximum opposing wind speed for that route, i.e., the number we wish to minimize. The second line should hold img integers, separated by single spaces, giving the numbers of successive bridges one crosses on the least tiresome route.

Should there be more than one least tiresome route, your program can pick one arbitrarily.

题解：

这道题裸的混合图求欧拉回路，直接搞就完了，输出方案的时候倒着输出即可。

代码：

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
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
 
using namespace std;
typedef long long LL;
typedef double LF;
typedef complex <LF> cd;
#define clr(x, y) memset(x, y, sizeof(x))
#define INF 707185547
const int MAXN = 1e4 + 15;
const int MAXM = 1e6 + 15;
struct {int from, to, nxt, c;}g[MAXM << 1];
int head[MAXN], cnt, du[MAXN], dd[MAXN], cur[MAXN], n, m, a[MAXN], b[MAXN], c[MAXN], d[MAXN], s, t, tot = 0, e[1005][1005], ans[MAXN], len = 0;
queue <int> q;
inline void add(int u, int v, int c){g[++ cnt] = (Edge){u, v, head[u], c}; head[u] = cnt;}
inline void add_edge(int u, int v, int c){add(u, v, c); add(v, u, 0);}
inline int read(){
    int r = 0, z = 1; char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-') z = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9'){r = r * 10 + ch - '0'; ch = getchar();}
    return r * z;
}
bool bfs(){
    clr(dd, -1);
    q.push(s); dd[s] = 0;
    while(!q.empty()){
        int u = q.front(); q.pop();
        for(int i = head[u]; ~i; i = g[i].nxt){
            int v = g[i].to;
            if(g[i].c && dd[v] == -1){
                dd[v] = dd[u] + 1;
                q.push(v);
            }
        }
    }
    return dd[t] != -1;
}
int dfs(int u, int flow){
    if(u == t) return flow;
    int ret = 0;
    for(int& i = cur[u]; ~i; i = g[i].nxt){
        int v = g[i].to;
        if(g[i].c && dd[v] == dd[u] + 1){
            int tmp = dfs(v, min(flow, g[i].c));
            flow -= tmp; g[i].c -= tmp;
            ret += tmp; g[i ^ 1].c += tmp;
            if(!flow) break;
        }
    }
    if(!ret) dd[u] = -1;
    return ret;
}
int dinic(){
    int ans = 0;
    while(bfs()){
        for(int i = 1; i <= n + 2; i ++) cur[i] = head[i];
        ans += dfs(s, INF);
    }
    return ans;
}
bool pd(int mid){
    clr(head, -1); cnt = -1;
    s = n + 1, t = n + 2;
    for(int i = 1; i <= m; i ++){
        if(c[i] > mid) return 0;
        if(d[i] <= mid) add_edge(a[i], b[i], 1);
    }
    for(int i = 1; i <= n; i ++){
        if(du[i] > 0) add_edge(s, i, du[i] / 2);
        else if(du[i] < 0) add_edge(i, t, -du[i] / 2);
    }
    if(dinic() == tot / 2) return 1;
    return 0;
}
void dfs(int x){
    for(int i = 1; i <= n; i ++){
        if(e[x][i]){
            e[x][i] = 0;
            dfs(i);
        }
    }
    ans[++ len] = x;
}
void print(int mid){
    for(int i = 0; i <= cnt; i += 2){
        if(g[i].from == s || g[i].to == t) continue;
        if(g[i].c == 0) e[g[i].to][g[i].from] = 1;
        else e[g[i].from][g[i].to] = 1;
    }
    for(int i = 1; i <= m; i ++){
        if(c[i] <= mid && d[i] > mid) e[a[i]][b[i]] = 1;
    }
    
    for(int i = 1; i <= n; i ++){
        for(int j = 1; j <= n; j ++){
            if(e[i][j]) printf("%d --> %dn", i, j);
        }
    }
    */
    dfs(1);//printf("n");
}
void work(){
    clr(head, -1);
    n = read(), m = read();
    for(int i = 1; i <= m; i ++){
        a[i] = read(), b[i] = read(), c[i] = read(), d[i] = read();
        if(d[i] < c[i]){swap(a[i], b[i]); swap(c[i], d[i]);}
        du[a[i]] ++; du[b[i]] --;
    }
    for(int i = 1; i <= n; i ++){
        if(du[i] % 2 != 0){printf("NIEn"); return ;}
        tot += abs(du[i]) / 2;
    }
    int l = 1, r = 1000;
    while(l < r){
        int mid = (l + r) >> 1;
        if(pd(mid)) r = mid;
        else l = mid + 1;
    }
    printf("%dn", l);
    int nonsense = pd(l); print(l);
    clr(e, 0);
    for(int i = 1; i <= m; i ++){
        e[a[i]][b[i]] = e[b[i]][a[i]] = i;
    }
    for(int i = len; i > 1; i --){
        printf("%d ", e[ans[i]][ans[i - 1]]);
    } printf("n");
}
int main(){
    work();
    return 0;
}
微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能