解題區/解題區 - UVa

UVa 10186 - Euro Cup 2000

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

給定 N 個隊伍，兩兩隊伍比賽兩次，已知部分比賽結果，勝者得三分，平手各得一分，輸者 零分。請問在剩餘比賽中，每個隊伍的最佳排名與最糟排名。

重點：剩下的比賽最多十場。

Sample Input

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
2
A
B
1
A B 1 0
5
Ger
Tur
Fin
Nor
Mol
14
Fin Mol 3 2
Tur Nor 3 0
Tur Ger 1 0
Nor Fin 1 0
Mol Ger 1 3
Tur Fin 1 3
Nor Mol 2 2
Nor Ger 0 3
Tur Mol 2 0
Ger Fin 2 0
Mol Fin 0 0
Ger Mol 6 1
Fin Tur 2 4
Mol Nor 0 0
0

Sample Output

1
2
3
4
5
6
7
8
9
10
Group #1
A 1-2
B 1-2
Group #2
Ger 1-3
Tur 1-3
Fin 1-4
Nor 1-5
Mol 4-5

Solution

一開始以為題目只給我 10 場資訊，結果一直想不到 P 的解法，只有 10 場就直接窮舉 10 場的結果紀錄即可。

額外閱讀 Matrix67 网络流和棒球赛淘汰问题

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 <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <map>
#include <vector>
using namespace std;
int g[32][32] = {}, score[32], n;
int brank[32], wrank[32];
vector< pair<int, int> > game;
void dfs(int idx) {
    if (idx == game.size()) {
        vector< pair<int, int> > board;
        int r;
        for (int i = 0; i < n; i++)
            board.push_back(make_pair(score[i], i));
        sort(board.begin(), board.end(), greater< pair<int, int> >());
        for (int i = 0; i < n; i++) {
            r = (int)(lower_bound(board.begin(), board.end(), make_pair(score[i], 0x3f3f3f3f), greater< pair<int, int> >()) 
                        - board.begin());
            brank[i] = min(brank[i], r);
            r = (int)(upper_bound(board.begin(), board.end(), make_pair(score[i], -1), greater< pair<int, int> >()) 
                        - board.begin());
            wrank[i] = max(wrank[i], r);
        }
        return ;
    }
    int x = game[idx].first, y = game[idx].second;
    score[x] += 3;
    dfs(idx+1);
    score[x] -= 3;
    
    score[y] += 3;
    dfs(idx+1);
    score[y] -= 3;
    
    score[x]++, score[y]++;
    dfs(idx+1);
    score[x]--, score[y]--;
}
int main() {
    char s[128];
    int cases = 0;
    int m, x, y, a, b;
    string name[128];
    while (scanf("%d", &n) == 1 && n) {
        map<string, int> R;
        memset(g, 0, sizeof(g));
        memset(score, 0, sizeof(score));
        for (int i = 0; i < n; i++) {
            scanf("%s", s);
            R[s] = i, name[i] = s;
        }
        scanf("%d", &m);
        for (int i = 0; i < m; i++) {
            scanf("%s", s);
            x = R[s];
            scanf("%s", s);
            y = R[s];
            g[x][y]++, g[y][x]++;
            scanf("%d %d", &a, &b);
            if (a < b)		score[y] += 3;
            else if (a > b)	score[x] += 3;
            else			score[x]++, score[y]++;
        }
        
        for (int i = 0; i < n; i++)
            brank[i] = 0x3f3f3f3f, wrank[i] = -1;
        game.clear();
        for (int i = 0; i < n; i++) {
            for (int j = i+1; j < n; j++) {
                for (int k = 0; k < 2 - g[i][j]; k++) {
                    game.push_back(make_pair(i, j));
                }
            }
        }
        dfs(0);
        printf("Group #%d\n", ++cases);
        for (int i = 0; i < n; i++) {
            printf("%s %d-%d\n", name[i].c_str(), brank[i] + 1, wrank[i]);
        }
        puts("");
    }
    return 0;
}