Problem UVA1609-Foul Play

Accept: 101  Submit: 514

Time Limit: 3000 mSec

Problem Description

 

 

Input

For each test case, the input is as follows:

• One line containing the number of teams n, where n is a power of two and 2 ≤ n ≤ 1024. Teams are numbered from 1 to n, where team 1 is your favourite team.

• n lines, each containing a string of n binary digits. The k-th digit on the j-th line is ‘1’ if team j would certainly win from team k, otherwise it is ‘0’. A team cannot play against itself, therefore the j-th digit on the j-th line is ‘0’. If j ̸= k, the k-th digit on the j-th line is different from the j-th digit on the k-th line.

 

 Output

For each test case, print n−1 lines of output, specifying a tournament schedule that ensures victory for team 1. The first n/2 lines describe the first round of the tournament. The next n/4 lines describe the second round, if any, etc. The last line describes the final match. Each line contains two integers x and y, indicating that team x plays a match against team y. If there are multiple tournament schedules where team 1 wins, any one of those tournament schedules will be accepted as a correct answer.

 

 Sample Input

4

0110

0011

0000

1010

8

00111010

10101111

00010010

01000101

00110010

10101011

00010000

10101010

 

 Sample Output

1 3

2 4

1 2

1 5

3 7

4 8

2 6

1 3

4 2

1 4

 

题解：这个题的构造比较难，我是想不到，构造出来之后的递归就相对比较简单了。构造的方式分为四个阶段：

1、把满足条件的队伍A和B配对，其中1打不过A，1能打过B，并且B能打过A.

2、把1和剩下的它能打过的队伍配对.

3、把1打不过的队伍相互配对.

4、把剩下的队伍配对.

能够证明按照这样的策略打过一轮之后，剩下的队伍还满足初始条件，因此可以递归求解。（构造太巧妙orz）

 

1 #include 
       
         2  3 using namespace std; 4  5 const int maxn = 1050; 6  7 int n; 8 char gra[maxn][maxn]; 9 bool vis[maxn], have_failed[maxn];10 11 void dfs(int m) {12     if (m == 1) return;13 14     memset(vis, false, sizeof(vis));15     16     for (int i = 2; i <= n; i++) {17         if (have_failed[i] || vis[i]) continue;18         if (gra[1][i] == '0') {19             for (int j = 2; j <= n; j++) {20                 if (have_failed[j] || vis[j]) continue;21                 if (gra[1][j] == '1' && gra[j][i] == '1') {22                     vis[j] = vis[i] = true;23                     have_failed[i] = true;24                     printf("%d %d\n", i, j);25                     break;26                 }27             }28         }29     }30     31     for (int i = 2; i <= n; i++) {32         if (have_failed[i] || vis[i]) continue;33         if (gra[1][i] == '1') {34             vis[i] = true;35             have_failed[i] = true;36             printf("%d %d\n", 1, i);37             break;38         }39     }40     41     int flag = 0, pre = 0;42     for (int i = 2; i <= n; i++) {43         if (have_failed[i] || vis[i]) continue;44         if (gra[1][i] == '0') {45             if (!flag) {46                 flag = 1;47                 pre = i;48             }49             else {50                 flag = 0;51                 vis[i] = vis[pre] = true;52                 printf("%d %d\n", pre, i);53                 if (gra[pre][i] == '0') have_failed[pre] = true;54                 else have_failed[i] = true;55             }56         }57     }58     59     flag = 0;60     for (int i = 2; i <= n; i++) {61         if (have_failed[i] || vis[i]) continue;62         if (!flag) {63             flag = 1;64             pre = i;65         }66         else {67             flag = 0;68             vis[i] = vis[pre] = true;69             printf("%d %d\n", pre, i);70             if (gra[pre][i] == '0') have_failed[pre] = true;71             else have_failed[i] = true;72         }73     }74 75     dfs(m >> 1);76 }77 78 int main()79 {80     //freopen("input.txt", "r", stdin);81     //freopen("output.txt", "w", stdout);82     while (~scanf("%d", &n)) {83         memset(have_failed, false, sizeof(have_failed));84         for (int i = 1; i <= n; i++) {85             scanf("%s", gra[i] + 1);86         }87 88         dfs(n);89     }90     return 0;91 }