1과 2를 왕복하는데 한번 갔던 도시는 다시 가지 않을 때 경우의 수를 구하는 문제이다.
길이 양방향 길이므로 2->1로 가는 길이 있다면 1->2로 가는 동일한 경로가 무조건 존재한다.
따라서 source = 1, sink = 2 일 때 들렀던 도시를 check해주며 maximum flow를 구하면 된다.
--------------------------------------------------------------------
어떤 종류인지는 예상이 안되지만 케이스가 추가되어 재채점되었다.
계속해서 틀렸다고 뜨길래 정점을 쪼개는 방식으로(한 도시에 한번만 방문하기 위해) 변경했다.
<코드>
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 <vector>
#include <queue>
#include <algorithm>
using namespace std;
typedef pair<int, int> pii;
int m, p;
struct MF {
struct E {
int u, c;
E *rev;
E(int u, int c) : u(u), c(c) {}
};
int n, s, e;
vector<vector<E *>> g;
vector<bool> check;
MF(int m) {
n = m;
s = 0;
e = 1 + m / 2;
g.resize(n);
check.resize(n);
}
void add_Edge(int u, int v, int c) {
E *ori = new E(v, c);
E *rev = new E(u, 0);
ori->rev = rev;
rev->rev = ori;
g[u].push_back(ori);
g[v].push_back(rev);
}
int bfs() {
vector<bool> ch(n, false);
vector<pii> f(n, { -1,-1 });
queue<int> q;
q.push(s);
ch[s] = true;
while (q.size()) {
int x = q.front();
q.pop();
for (int i = 0; i < g[x].size(); i++) {
if (x == s && g[x][i]->u == e) continue;
if (!ch[g[x][i]->u] && g[x][i]->c && !check[g[x][i]->u]) {
q.push(g[x][i]->u);
ch[g[x][i]->u] = true;
f[g[x][i]->u] = { x, i };
}
}
}
if (!ch[e]) return 0;
int x = e;
int c = 1;
while (f[x].first != -1) {
E *ed = g[f[x].first][f[x].second];
ed->c --;
ed->rev->c ++;
x = f[x].first;
}
return c;
}
int flow() {
int ans = 0;
while (1) {
int f = bfs();
if (!f) break;
ans += f;
}
return ans;
}
};
int main() {
scanf("%d%d", &m, &p);
MF mf(2*m);
mf.add_Edge(0, m, 2e9);
mf.add_Edge(1, 1 + m, 2e9);
for (int i = 2; i < m; i++)
mf.add_Edge(i, i + m, 1);
while (p--) {
int a, b;
scanf("%d%d", &a, &b);
a--; b--;
mf.add_Edge(a + m, b, 1);
mf.add_Edge(b + m, a, 1);
}
printf("%d\n", mf.flow());
return 0;
}
'BOJ' 카테고리의 다른 글
| 1069 집으로 (0) | 2017.08.30 |
|---|---|
| 2570 비숍 (0) | 2017.08.30 |
| 14671 영정이의 청소 (0) | 2017.08.30 |
| 9333 돈 갚기 (0) | 2017.08.30 |
| 1765 닭싸움 팀 정하기 (0) | 2017.08.30 |