백준7616 교실로 가는 길

작성일 | In

문제 링크

  • http://icpc.me/7616

사용 알고리즘

  • Network Flow
  • Max Flow

풀이

서로소 경로를 구해야 하므로 Network Flow문제입니다.
K개의 경로만 찾으면 되기 때문에 플로우를 K번만 흘려주면 됩니다.

주의해야 할 점은 플로우를 흘리면서 경로를 동시에 찾아주게 되면 WA를 받게 되는데, 역방향 간선으로 플로우를 주는 경우가 있기 때문입니다.
플로우를 K번 모두 흘린 다음에 경로를 찾아줘야 합니다.

전체 코드

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
#include <bits/stdc++.h>
using namespace std;

struct Edge{
	int v, c, dual;
	Edge(){}
	Edge(int v, int c, int dual) : v(v), c(c), dual(dual) {}
};

vector<Edge> g[10101];
int k, n;
const int s = 1 * 2 + 1;
const int t = 2 * 2;

void addEdge(int s, int e, int x){
	g[s].emplace_back(e, 1, g[e].size());
	g[e].emplace_back(s, 0, g[s].size()-1);
}

void init(){
	for(int i=0; i<10101; i++) g[i].clear();
}

bool flow(){
	int path[10101] = {0};
	int par[10101]; memset(par, -1, sizeof par);
	queue<int> q; q.push(s);
	while(q.size()){
		int now = q.front(); q.pop();
		for(int x=0; x<g[now].size(); x++){
			auto i = g[now][x];
			int nxt = i.v;
			int cap = i.c;
			int dual = i.dual;
			if(par[nxt] == -1 && cap > 0){
				par[nxt] = now;
				path[nxt] = x;
				q.push(nxt);
			}
		}
	}
	if(par[t] == -1) return 0;

	for(int i=t; i!=s; i=par[i]){
		int a = par[i], b = i;
		g[a][path[b]].c --;
		int dual = g[a][path[b]].dual;
		g[b][dual].c ++;
	}
	return 1;
}

void print(){
	int prv = -2, now = s;
	while(now/2 != 2){
		if(now & 1) printf("%d ", now/2);
		prv = now;
		if(now % 2 == 0){
			now = now + 1; continue;
		}
		for(int i=0; i<g[now].size(); i++){
			int nxt = g[now][i].v;
			if(nxt/2 == now/2) continue;
			if(g[now][i].c == 0){
				g[now][i].c = 1;
				now = nxt;
				break;
			}
		}
	}
	printf("%d\n", 2);
}

void solve(int tc){
	init();
	for(int i=1; i<=n; i++){
		addEdge(i*2, i*2+1, 1);
		int j; char c;
		while(1){
			scanf("%d%c", &j, &c);
			addEdge(i*2+1, j*2, 1);
			if(c == '\n') break;
		}
	}

	printf("Case %d:\n", tc);
	for(int i=0; i<k; i++){
		if(!flow()){
			printf("Impossible\n\n"); return;
		}
	}

	for(int i=0; i<k; i++) print();
	printf("\n");
}

int main(){
	int asdf = 1;
	while(1){
		scanf("%d %d", &k, &n);
		if(!k && !n) break;
		solve(asdf++);
	}
}