解題區►解題區 - UVa

UVa 11972 - Round Trip

contents

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

Problem

給一張圖，從起點 c 出發，每一條邊最多經過一次，最後回到 c。中間可以經過哪些節點。

Sample Input

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

Sample Output

1
2
Case 1: 2 3 4 5 6
Case 2: none

Solution

窮舉所有可能做最大流，從起點 c 到指定的點 v，如果存在最大流 maxflow >= 2 表示至少兩條，因此可以拉成一個環，表示 v 可以在環上。

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
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
using namespace std;
#define MAXN 128
struct Node {
    int x, y;
	int cap, flow;// x->y, v
    int next;
} edge[10005];
int e, head[MAXN], prev[MAXN], record[MAXN];
int level[MAXN], visited[MAXN];
void addEdge(int x, int y, int v) {
    edge[e].x = x, edge[e].y = y, edge[e].cap = v, edge[e].flow = 0;
    edge[e].next = head[x], head[x] = e++;
    edge[e].x = y, edge[e].y = x, edge[e].cap = 0, edge[e].flow = 0;
    edge[e].next = head[y], head[y] = e++;
}
bool buildLevelGraph(int s, int t) {
    memset(level, 0, sizeof(level));
    queue<int> Q;
    Q.push(s), level[s] = 1;
    while(!Q.empty()) {
        int tn = Q.front();
        Q.pop();
        for(int i = head[tn]; i != -1; i = edge[i].next) {
            int y = edge[i].y;
            if(edge[i].cap > edge[i].flow && level[y] == 0) {
                level[y] = level[tn] + 1;
                Q.push(y);
            }
        }
    }
    return level[t] > 0;
}
int constructBlockingFlow(int s, int t) {
    int ret = 0;
    stack<int> stk;
    memset(visited, 0, sizeof(visited));
    stk.push(s);
    while(!stk.empty()) {
        int now = stk.top();
        if(now != t) {
            for(int i = head[now]; i != -1; i = edge[i].next) {
                int y = edge[i].y;
                if(visited[y] || level[y] != level[now] + 1)
                    continue;
                if(edge[i].cap > edge[i].flow) {
                    stk.push(y), prev[y] = now, record[y] = i;
                    break;
                }
            }
            if(stk.top() == now)
                stk.pop(), visited[now] = 1;
        } else {
            int flow = 0x3f3f3f3f, bottleneck;
            for(int i = t; i != s; i = prev[i]) {
                int ri = record[i];
                flow = min(flow, edge[ri].cap - edge[ri].flow);
            }
            for(int i = t; i != s; i = prev[i]) {
                int ri = record[i];
                edge[ri].flow += flow;
                edge[ri^1].flow -= flow;
                if(edge[ri].cap - edge[ri].flow == 0)
                    bottleneck = prev[i];
            }
            while(!stk.empty() && stk.top() != bottleneck)
                stk.pop();
            ret += flow;
        }
    }
    return ret;
}
int maxflowDinic(int s, int t) {
    int flow = 0;
    while(buildLevelGraph(s, t))
        flow += constructBlockingFlow(s, t);
    return flow;
}
vector<int> maxflowCut(int s, int t, int n) {
	buildLevelGraph(s, t);
	vector<int> ret;
	for (int i = 1; i <= n; i++) {
		for (int j = head[i]; j != -1; j = edge[j].next) {
			if (level[edge[j].x] && !level[edge[j].y] && edge[j].cap > 0 && edge[j].cap == edge[j].flow)
				ret.push_back(j);
		}
	}
	return ret;
}
int clearflow() {
	for (int i = 0; i < e; i++)
		edge[i].flow = 0;
}
int main() {
    int n, m, c;
    int x, y, v;
    int cases = 0;
    int testcase;
    scanf("%d", &testcase);
    while(testcase--) {
    	scanf("%d %d %d", &n, &m, &c);
        e = 0;
        memset(head, -1, sizeof(head));
        for(int i = 0; i < m; i++) {
        	scanf("%d %d", &x, &y);
        	addEdge(x, y, 1);
        	addEdge(y, x, 1);
        }
        printf("Case %d: ", ++cases);
        int f = 0;
        for (int i = 1; i <= n; i++) {
        	if (i == c)	continue;
        	clearflow();
        	int flow = maxflowDinic(c, i);
        	if (flow >= 2) {
        		if (f)	putchar(' ');
        		printf("%d", i);
        		f = 1;
        	}
        }
        if (f == 0)
        	puts("none");
        else
        	puts("");
    }
    return 0;
}
/*
2
6 7 1
1 2
1 3
2 6
4 6
2 5
5 3
4 2
2 1 2
1 2
*/