BAPC - Chess Competition
Source: BAPC12 - Problem C: Chess Competition
Tags: Graph
Problem:
N thí sinh tham gia thi đấu cờ vua, mỗi thí sinh sẽ đấu 1 ván với tất cả các thí sinh còn lại. Thí sinh chiến thắng một ván đấu nhận được 1 điểm, nếu hòa nhận được 0.5 điểm và không nhận được điểm nào nếu thua. Thí sinh có số điểm cao nhất là người chiến thắng cuộc thi, nếu có nhiều thí sinh cùng cao điểm nhất sẽ tổ chức đấu tiếp để tìm ra người chiến thắng.
Hiện tại ta có kết quả thi đấu của một số ván đấu, thể hiện bằng một ma trận 2 chiều N × N, ký tự thứ j của dòng thứ i mang ý nghĩa là:
'1': nếu i thắng j
'0': nếu i thua j
'd': nếu ván đấu hòa
'.': nếu ván đấu chưa được chơi
'x': nếu i = j, một thí sinh không thể đấu với chính họ được
Dựa vào kết quả một số trận đã diễn ra, ban tổ chức muốn xác định xem ai là người có khả năng chiến thắng cuộc thi.
Dòng đầu input là số lượng test. Với mỗi test dòng đầu là số N theo sau là N dòng thể hiện ma trận.
Với mỗi test in ra trên một dòng là số thứ tự của các thí sinh có khả năng thắng cuộc thi (tăng dần).
2 ≤ N ≤ 30.
Ví dụ:
Input:
3
5
x.11d
.x1d1
00x.0
0d.x.
d01.x
7
x00111.
1x01d.d
11x1.00
000x000
0d.1xd1
0.11dxd
.d110dx
7
x00011.
1x00d.d
11x0.0.
111x111
0d.0xd.
0.10dx.
.d.0..x
Output:
1 2
1 2 3 5 6 7
4
Explanation:
Test 1: Nếu 1 hoặc 2 thắng trận của mình, không ai có thể cao điểm hơn họ.
Test 2: Thí sinh số 4 không thắng trận nào hiện tại và cũng không thể đấu thêm ván nào nữa, do đó duy nhất thí sinh này không thể thắng cuộc thi.
Test 3: Các thí sinh còn lại dù có thắng hết trận của mình cũng không thể cao điểm hơn thí sinh 4, do đó 4 là người duy nhất thắng cuộc thi.
Solution:
Với mỗi thí sinh thứ i, ta giả sử i thắng tất cả trận còn lại của mình, gọi số điểm của i lúc này là MaxPoint. Lúc này, nếu có thí sinh nào hiện tại (không tính điểm các ván chưa đấu) có số điểm cao hơn MaxPoint, thí sinh i không thể thắng cuộc thi. Nếu không, vậy điều kiện để i có thể thắng cuộc thi là có một cách diễn ra các ván đấu còn lại sao cho số điểm của người cao điểm nhất không vượt quá MaxPoint. Để kiểm tra được điều này, ta đưa về bài toán Maximum Flow với N + M đỉnh, trong đó ta có N đỉnh là N thí sinh, M đỉnh là M ván đấu chưa đấu. Nối từ đỉnh nguồn Source đến N đỉnh thí sinh với sức chứa tối đa là số điểm tối đa mà thí sinh đó được quyền ghi được, tức là, giả sử điểm hiện tại của thí sinh j là X và còn Y trận chưa đấu, thì số điểm tối đa thí sinh j được phép ghi được là min(MaxPoint - X, Y). Nối từ mỗi đỉnh thí sinh đến đỉnh thể hiện ván đấu chưa đấu của thí sinh đó, với sức chứa tối đa là 1, tức là mỗi thí sinh tối đa chỉ có thể ghi được 1 điểm trong ván đấu đó. Nối M đỉnh ván đấu đến đỉnh thu Sink với sức chứa tối đa là 1, tức là mỗi ván đấu chỉ có thể có tổng điểm của 2 thí sinh chơi ván đấu đó là 1 dù cho kết quả là ai thắng ai thua hay là hòa. Từ đây ta tìm luồng cực đại trong mạng đã tạo, nếu giá trị luồng cực đại là M tức là M ván đấu đều đã được chơi thỏa tất cả điều kiện (được thể hiện bằng sức chứa tối đa của các cung), lúc này i có thể thắng cuộc thi vì đã tìm được cách chơi thỏa mãn điều kiện i vẫn là người cao điểm nhất và M ván đấu đều diễn ra đầy đủ.
Độ phức tạp: O(N^5)
Code: (để thuận tiện, ta nhân 2 vào các giá trị điểm, tức là ván hòa tính 1 điểm và thắng tính 2 điểm, để cho các số liệu đều nguyên, điều này không ảnh hưởng đến kết quả)
#include <stdio.h>
#include <string.h>
#include <vector>
#include <queue>
using namespace std;
int n, m;
char s[35][35];
int cur_point[35], max_can_earn[35], against_i[35];
int c[500][500], f[500][500], trace[500];
bool vis[500];
queue <int> q;
bool find_augment_path() {
memset(trace, -1, sizeof trace);
q.push(0); trace[0] = 0;
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v = 0; v <= n + m + 1; ++v)
if (trace[v] == -1 && c[u][v] - f[u][v]) {
q.push(v); trace[v] = u;
if (v == n + m + 1) {
while (!q.empty()) q.pop();
return true;
}
}
}
return false;
}
void increase_flow() {
int x = 10000;
int v = n + m + 1;
while (v) {
int u = trace[v];
x = min(x, c[u][v] - f[u][v]);
v = u;
}
v = n + m + 1;
while (v) {
int u = trace[v];
f[u][v] += x;
f[v][u] -= x;
v = u;
}
}
int max_flow() {
while (find_augment_path())
increase_flow();
int res = 0;
for (int u = 0; u <= n + m + 1; ++u)
res += f[u][n + m + 1];
return res;
}
void solve() {
scanf("%d", &n);
memset(cur_point, 0, sizeof cur_point);
memset(max_can_earn, 0, sizeof max_can_earn);
for (int i = 1; i <= n; ++i) {
getchar();
for (int j = 1; j <= n; ++j) {
s[i][j] = getchar();
if (s[i][j] == 'd')
cur_point[i] += 1;
else if (s[i][j] == '1')
cur_point[i] += 2;
else if (s[i][j] == '.')
max_can_earn[i] += 2;
}
}
for (int i = 1; i <= n; ++i) {
memset(against_i, 0, sizeof against_i);
memset(c, 0, sizeof c);
memset(f, 0, sizeof f);
m = 0;
for (int u = 1; u < n; ++u)
for (int v = u + 1; v <= n; ++v)
if (s[u][v] == '.') {
if (u == i) ++against_i[v];
else if (v == i) ++against_i[u];
else ++m, c[u][n + m] = c[v][n + m] = 2;
}
for (int u = 1; u <= n; ++u) if (u != i) {
if (cur_point[u] > max_can_earn[i] + cur_point[i])
goto next;
else c[0][u] = min(max_can_earn[i] + cur_point[i] - cur_point[u], max_can_earn[u] - 2 * against_i[u]);
}
for (int u = n + 1; u <= n + m; ++u)
c[u][n + m + 1] = 2;
if (max_flow() == 2 * m) printf("%d ", i);
next:;
}
}
int main() {
int test; scanf("%d", &test);
while (test--) solve(), putchar('\n');
}
Tags: Graph
Problem:
N thí sinh tham gia thi đấu cờ vua, mỗi thí sinh sẽ đấu 1 ván với tất cả các thí sinh còn lại. Thí sinh chiến thắng một ván đấu nhận được 1 điểm, nếu hòa nhận được 0.5 điểm và không nhận được điểm nào nếu thua. Thí sinh có số điểm cao nhất là người chiến thắng cuộc thi, nếu có nhiều thí sinh cùng cao điểm nhất sẽ tổ chức đấu tiếp để tìm ra người chiến thắng.
Hiện tại ta có kết quả thi đấu của một số ván đấu, thể hiện bằng một ma trận 2 chiều N × N, ký tự thứ j của dòng thứ i mang ý nghĩa là:
'1': nếu i thắng j
'0': nếu i thua j
'd': nếu ván đấu hòa
'.': nếu ván đấu chưa được chơi
'x': nếu i = j, một thí sinh không thể đấu với chính họ được
Dựa vào kết quả một số trận đã diễn ra, ban tổ chức muốn xác định xem ai là người có khả năng chiến thắng cuộc thi.
Dòng đầu input là số lượng test. Với mỗi test dòng đầu là số N theo sau là N dòng thể hiện ma trận.
Với mỗi test in ra trên một dòng là số thứ tự của các thí sinh có khả năng thắng cuộc thi (tăng dần).
2 ≤ N ≤ 30.
Ví dụ:
Input:
3
5
x.11d
.x1d1
00x.0
0d.x.
d01.x
7
x00111.
1x01d.d
11x1.00
000x000
0d.1xd1
0.11dxd
.d110dx
7
x00011.
1x00d.d
11x0.0.
111x111
0d.0xd.
0.10dx.
.d.0..x
Output:
1 2
1 2 3 5 6 7
4
Explanation:
Test 1: Nếu 1 hoặc 2 thắng trận của mình, không ai có thể cao điểm hơn họ.
Test 2: Thí sinh số 4 không thắng trận nào hiện tại và cũng không thể đấu thêm ván nào nữa, do đó duy nhất thí sinh này không thể thắng cuộc thi.
Test 3: Các thí sinh còn lại dù có thắng hết trận của mình cũng không thể cao điểm hơn thí sinh 4, do đó 4 là người duy nhất thắng cuộc thi.
Solution:
Với mỗi thí sinh thứ i, ta giả sử i thắng tất cả trận còn lại của mình, gọi số điểm của i lúc này là MaxPoint. Lúc này, nếu có thí sinh nào hiện tại (không tính điểm các ván chưa đấu) có số điểm cao hơn MaxPoint, thí sinh i không thể thắng cuộc thi. Nếu không, vậy điều kiện để i có thể thắng cuộc thi là có một cách diễn ra các ván đấu còn lại sao cho số điểm của người cao điểm nhất không vượt quá MaxPoint. Để kiểm tra được điều này, ta đưa về bài toán Maximum Flow với N + M đỉnh, trong đó ta có N đỉnh là N thí sinh, M đỉnh là M ván đấu chưa đấu. Nối từ đỉnh nguồn Source đến N đỉnh thí sinh với sức chứa tối đa là số điểm tối đa mà thí sinh đó được quyền ghi được, tức là, giả sử điểm hiện tại của thí sinh j là X và còn Y trận chưa đấu, thì số điểm tối đa thí sinh j được phép ghi được là min(MaxPoint - X, Y). Nối từ mỗi đỉnh thí sinh đến đỉnh thể hiện ván đấu chưa đấu của thí sinh đó, với sức chứa tối đa là 1, tức là mỗi thí sinh tối đa chỉ có thể ghi được 1 điểm trong ván đấu đó. Nối M đỉnh ván đấu đến đỉnh thu Sink với sức chứa tối đa là 1, tức là mỗi ván đấu chỉ có thể có tổng điểm của 2 thí sinh chơi ván đấu đó là 1 dù cho kết quả là ai thắng ai thua hay là hòa. Từ đây ta tìm luồng cực đại trong mạng đã tạo, nếu giá trị luồng cực đại là M tức là M ván đấu đều đã được chơi thỏa tất cả điều kiện (được thể hiện bằng sức chứa tối đa của các cung), lúc này i có thể thắng cuộc thi vì đã tìm được cách chơi thỏa mãn điều kiện i vẫn là người cao điểm nhất và M ván đấu đều diễn ra đầy đủ.
Độ phức tạp: O(N^5)
Code: (để thuận tiện, ta nhân 2 vào các giá trị điểm, tức là ván hòa tính 1 điểm và thắng tính 2 điểm, để cho các số liệu đều nguyên, điều này không ảnh hưởng đến kết quả)
#include <stdio.h>
#include <string.h>
#include <vector>
#include <queue>
using namespace std;
int n, m;
char s[35][35];
int cur_point[35], max_can_earn[35], against_i[35];
int c[500][500], f[500][500], trace[500];
bool vis[500];
queue <int> q;
bool find_augment_path() {
memset(trace, -1, sizeof trace);
q.push(0); trace[0] = 0;
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v = 0; v <= n + m + 1; ++v)
if (trace[v] == -1 && c[u][v] - f[u][v]) {
q.push(v); trace[v] = u;
if (v == n + m + 1) {
while (!q.empty()) q.pop();
return true;
}
}
}
return false;
}
void increase_flow() {
int x = 10000;
int v = n + m + 1;
while (v) {
int u = trace[v];
x = min(x, c[u][v] - f[u][v]);
v = u;
}
v = n + m + 1;
while (v) {
int u = trace[v];
f[u][v] += x;
f[v][u] -= x;
v = u;
}
}
int max_flow() {
while (find_augment_path())
increase_flow();
int res = 0;
for (int u = 0; u <= n + m + 1; ++u)
res += f[u][n + m + 1];
return res;
}
void solve() {
scanf("%d", &n);
memset(cur_point, 0, sizeof cur_point);
memset(max_can_earn, 0, sizeof max_can_earn);
for (int i = 1; i <= n; ++i) {
getchar();
for (int j = 1; j <= n; ++j) {
s[i][j] = getchar();
if (s[i][j] == 'd')
cur_point[i] += 1;
else if (s[i][j] == '1')
cur_point[i] += 2;
else if (s[i][j] == '.')
max_can_earn[i] += 2;
}
}
for (int i = 1; i <= n; ++i) {
memset(against_i, 0, sizeof against_i);
memset(c, 0, sizeof c);
memset(f, 0, sizeof f);
m = 0;
for (int u = 1; u < n; ++u)
for (int v = u + 1; v <= n; ++v)
if (s[u][v] == '.') {
if (u == i) ++against_i[v];
else if (v == i) ++against_i[u];
else ++m, c[u][n + m] = c[v][n + m] = 2;
}
for (int u = 1; u <= n; ++u) if (u != i) {
if (cur_point[u] > max_can_earn[i] + cur_point[i])
goto next;
else c[0][u] = min(max_can_earn[i] + cur_point[i] - cur_point[u], max_can_earn[u] - 2 * against_i[u]);
}
for (int u = n + 1; u <= n + m; ++u)
c[u][n + m + 1] = 2;
if (max_flow() == 2 * m) printf("%d ", i);
next:;
}
}
int main() {
int test; scanf("%d", &test);
while (test--) solve(), putchar('\n');
}
Nhận xét
Đăng nhận xét