URAL 1156. Two Rounds

Author: 2015-10-09

ACM

, , ,

1. 题目

http://acm.timus.ru/problem.aspx?space=1&num=1156

1156. Two Rounds

Time limit: 2.0 second
Memory limit: 64 MB
There are two rounds in the Urals Championship. The competitors have to solve N problems on each round. The jury had been working hard and finally managed to prepare 2N problems for the championship. But it appeared that among those problems there were some, which have the analogous solutions. One shouldn’t assign such a problems for the same round. Please, help the jury form sets of tasks for each of the rounds.

Input

First line contains two numbers: N, the number of tasks for a round, and M, the number of pairs of tasks which should not be assigned for one round (1 ≤ N ≤ 50; 0 ≤ M ≤ 100). Then M lines follow, each of them contains two numbers of analogous tasks.

Output

Output two lines, containing numbers of tasks assigned for each round. If there is no solution, output the only word “IMPOSSIBLE”. If there are more than one solution you may assume anyone of them.

Sample

input output 
2 3
1 3
2 1
4 3

1 4
2 3
Problem Author: Eugene Bryzgalov
Problem Source: Ural Collegiate Programming Contest, April 2001, Perm, English Round

2. 思路

把N道题目平均分配到两轮比赛中，每轮N/2道题目。其中有一些类似的题目，不能同时出现在一轮比赛中，求如何分配题目。

对根据类似（冲突）关系，对题目进行BFS并分组，每一大组内包括相互冲突的两组题目，大组间没有冲突关系。然后要把这些题目划分为两组，使得每组刚好有N/2道题目，变成了背包问题。题目要求输出具体的分配方法，需要在DP过程中保留回溯信息。

3. 代码

#include <cstdio>

const int MAX_N = 51;
const int MAX_PROBLEM_NUM = 2 * MAX_N;

typedef bool Graph[MAX_PROBLEM_NUM][MAX_PROBLEM_NUM];

void solveE7f_TwoRounds();
int input(Graph graph, int n);

int main() {
    // freopen("test.txt", "r", stdin);
    solveE7f_TwoRounds();
}

Graph isSame;
int group[MAX_PROBLEM_NUM], queue[MAX_PROBLEM_NUM], numInGroup[MAX_PROBLEM_NUM], f[MAX_PROBLEM_NUM][MAX_PROBLEM_NUM], selectedGroupId[MAX_PROBLEM_NUM];;
bool used[MAX_PROBLEM_NUM];
void solveE7f_TwoRounds() {
    int n, m;
    scanf("%d %d", &n, &m);
    int problemNum = n * 2;
    int first = input(isSame, m);

    int front = 0, rear = 0, groupForRound1 = 1, groupForRound2 = 2, searchIdx = 1;
    queue[rear++] = first;
    group[first] = groupForRound1;

    while (front != rear) {
        int curr = queue[front++];
        for (int i = 1; i <= problemNum; ++i) {
            if (i != curr && isSame[curr][i]) {
                if (group[i] == 0) {
                    queue[rear++] = i;
                    group[i] = group[curr] == groupForRound1 ? groupForRound2 : groupForRound1;
                }
                else if (group[i] == group[curr]) {
                    printf("IMPOSSIBLE\n");
                    return;
                }
            }
        }

        if (front == rear) {
            for (; searchIdx <= problemNum; ++searchIdx) {
                if (group[searchIdx] == 0) {
                    groupForRound1 += 2;
                    groupForRound2 += 2;
                    queue[rear++] = searchIdx;
                    group[searchIdx] = groupForRound1;
                    break;
                }
            }
        }
    }

    for (int i = 1; i <= problemNum; ++i) {
        ++numInGroup[group[i]];
    }

    for (int i = 0; i <= problemNum; ++i) {
        for (int j = 0; j <= problemNum; ++j) {
            f[i][j] = -1;
        }
    }

    f[0][0] = 1;
    for (int i = 0; i<groupForRound2/2; ++i) {
        for (int j = 0; j <= n; ++j) {
            if (f[i][j] != -1) {
                f[i + 1][j + numInGroup[i * 2 + 1]] = i * 2 + 1;
                f[i + 1][j + numInGroup[i * 2 + 2]] = i * 2 + 2;
            }
        }
    }
    if (f[groupForRound2 / 2][n] == -1) {
        printf("IMPOSSIBLE\n");
        return;
    }

    int cnt = 0;
    for (int i = groupForRound2 / 2, neededNum = n; neededNum != 0; --i, ++cnt) {
        selectedGroupId[cnt] = f[i][neededNum];
        neededNum -= numInGroup[selectedGroupId[cnt]];
    }

    for (int i = 1; i <= problemNum; ++i) {
        for (int j = 0; j < cnt; ++j) {
            if (group[i] == selectedGroupId[j]) {
                printf("%d ", i);
                used[i] = true;
                break;
            }
        }
    }
    printf("\n");

    for (int i = 1; i <= problemNum; ++i) {
        if (!used[i])
            printf("%d ", i);
    }
    printf("\n");

}

int input(Graph graph, int n) {
    int first = -1;
    for (int i = 0; i < n; ++i) {
        int a, b;
        scanf("%d %d", &a, &b);
        graph[a][b] = true;
        graph[b][a] = true;
        first = (first == -1 ? a : first);
    }
    return first;
}