Algorithm/알고스팟
algospot - matchfix
jhg0406
2020. 2. 17. 19:15
|
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
|
//algospot - matchfix
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define INF 2000000000
int N, M;
vector<int> base;
vector<vector<int>> capa, flow;
int bot;
void init()
{
cin >> N >> M;
base = vector<int>(N);
capa = flow = vector<vector<int>>(N+M+2, vector<int>(N+M+2, 0));
cin >> base[0];
bot = base[0];
for(int i = 1; i<N; ++i)
{
cin >> base[i];
if(bot <= base[i])
bot = base[i]+1;
}
capa[M+1][M+N+1] = bot - base[0];
for(int i = M+2; i<=M+N; ++i)
capa[i][N+M+1] = bot - base[i - M - 1] -1;
int x, y;
for(int i = 1; i<=M; ++i)
{
cin >> x >> y;
capa[0][i] = capa[i][M+x+1] = capa[i][M+y+1] = 1;
}
}
void adjust()
{
for(int i = M+1; i<=M+N; ++i)
++capa[i][M+N+1];
++bot;
}
bool networkFlow(int source, int sink)
{
int count = 0;
while(true)
{
vector<int> parent(N+M+2, -1);
queue<int> q;
q.push(source);
parent[source] = source;
while(!q.empty() && parent[sink] == -1)
{
int here = q.front(); q.pop();
for(int there = 0; there<=N+M+1; ++there)
if(capa[here][there] - flow[here][there] > 0 && parent[there] == -1)
{
q.push(there);
parent[there] = here;
}
}
if(parent[sink] == -1)
if(count < M)
{
adjust();
continue;
}
else
break;
int amt = INF;
for(int p = sink; p != source; p = parent[p])
amt = min(amt, capa[parent[p]][p] - flow[parent[p]][p]);
for(int p = sink; p != source; p = parent[p])
{
flow[parent[p]][p] += amt;
flow[p][parent[p]] -= amt;
}
++count;
}
if(capa[M+1][M+N+1] - flow[M+1][M+N+1] > 0)
return false;
return true;
}
int main()
{
int C; cin >> C;
for(int tn = 0; tn< C; ++tn)
{
init();
if(networkFlow(0, N+M+1))
cout << bot << "\n";
else
cout << -1 << "\n";
}
}
|
cs |
https://algospot.com/judge/problem/read/MATCHFIX
algospot.com :: MATCHFIX
승부조작 문제 정보 문제 한때 세계대회 준우승까지 하며 최강의 프로그래머로 칭송 받았던 J씨는 성적이 떨어진 이후 유혹을 이기지 못하고 승부 조작의 세계에 손을 댔습니다. 프로그래밍 대회의 마당발로 알려졌던 J씨인만큼 승부 조작의 규모는 상당해서, 알고스팟 컵 결승 리그에 진출한 N명의 선수 모두를 승부 조작에 참여시켰습니다. 결승 리그는 여러 번의 1:1 경기로 이루어집니다. 경기를 하면 무승부 없이 항상 승부가 나며, 모든 경기가 끝난 후 승수가 가장
algospot.com
MATCHFIX
testcase 1번을 그래프로 모델링 한 사진입니다.
w를 최소의 크기로 잡고, 유량 알고리즘이 막힐때마다 선수들과 sink사이의 간선들의 capacity를 1씩 올려주어 최초로 source에서 나가는 간선의 capacity - flow가 모두 0이 되는 순간의 w가 답이 됩니다.
