백준3980 선발 명단

작성일 | In

문제 링크

  • http://icpc.me/3980

문제 출처

  • 2010 GCPC G번

사용 알고리즘

  • MCMF

풀이

왼쪽에는 선수를, 오른쪽에는 포지션을 배치해줍니다. 용량은 1, 비용은 Si,j인 간선으로 선수와 포지션을 이어주면 이분 그래프처럼 나옵니다.
왼쪽에 있는 정점들을 source와 연결하고, 오른쪽에 있는 sink와 연결하고 MCMF를 돌리면 됩니다.

그러나 이 문제에서는 최소 비용이 아닌 최대 비용을 요구하므로 비용에 -1을 곱해서 저장해주어야 합니다.

전체 코드

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

int bias = 12;
int f[33][33];
int d[33][33];
int c[33][33];
vector<int> g[33];
int s = 24, t = 25;

int inque[33];
int dist[33];
int par[33];

void init(){
	memset(f, 0, sizeof f);
	memset(d, 0, sizeof d);
	memset(c, 0, sizeof c);
	for(int i=0; i<33; i++) g[i].clear();
	memset(inque, 0, sizeof inque);
	memset(dist, 0x3f, sizeof dist);
	memset(par, -1, sizeof par);
}

int mcmf(){
	int ret = 0;
	while(1){
		memset(inque, 0, sizeof inque);
		memset(dist, 0x3f, sizeof dist);
		memset(par, -1, sizeof par);

		queue<int> q;
		q.push(s); inque[s] = 1;
		dist[s] = 0;
		while(!q.empty()){
			int now = q.front(); q.pop(); inque[now] = 0;
			for(auto nxt : g[now]){
				if(c[now][nxt] - f[now][nxt] > 0 && dist[nxt] > dist[now] + d[now][nxt]){
					dist[nxt] = dist[now] + d[now][nxt];
					par[nxt] = now;
					if(!inque[nxt]){
						q.push(nxt); inque[nxt] = 1;
					}
				}
			}
		}
		if(par[t] == -1) break;
		for(int i=t; i!=s; i=par[i]){
			int a = par[i], b = i;
			f[a][b]++; f[b][a]--;
			ret += d[a][b];
		}
	}
	return -ret;
}

void solve(){
	init();
	for(int i=1; i<=11; i++){
		for(int j=bias+1; j<=bias+11; j++){
			cin >> d[i][j]; d[i][j] *= -1;
			if(!d[i][j]) continue;
			c[i][j] = 1;
			g[i].push_back(j); g[j].push_back(i);
			d[j][i] = -d[i][j];
		}
	}

	for(int i=1; i<=11; i++){
		g[s].push_back(i); g[i].push_back(s);
		c[s][i] = 1;
	}
	for(int i=bias+1; i<=bias+11; i++){
		g[i].push_back(t); g[t].push_back(i);
		c[i][t] = 1;
	}

	cout << mcmf() << "\n";
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int asdf; cin >> asdf;
	while(asdf--) solve();
}