[UVA][隨機] 10982 - Troublemakers＠Morris' Blog

2013-07-22 20:08:19| 人氣881| 回應0 | 上一篇 | 下一篇

[UVA][隨機] 10982 - Troublemakers

推薦 0 收藏 0 轉貼0 訂閱站台

Problem A
Troublemakers
Time Limit: 1 second

[after seeing that the room is on fire; Ted has a needle
in his hand while holding the leg of a dead woman; Sara
has a bottle of champagne in her hand, and Juancho is smoking]
Man: Did they misbehave?

Robert Rodrigues, "The Misbehavers."

Every school class has its troublemakers - those kids who can make the teacher's life miserable. On his own, a troublemaker is manageable, but when you put certain pairs of troublemakers together in the same room, teaching a class becomes very hard. There are n kids in Mrs. Shaida's math class, and there are m pairs of troublemakers among them. The situation has gotten so bad that Mrs. Shaida has decided to split the class into two classes. Help her do it in such a way that the number of troublemaker pairs is reduced by at least a half.

Input
The first line of input gives the number of cases, N. N test cases follow. Each one starts with a line containing n (0<=n<=100) and m (0<m<5000). The next m lines will contain a pair of integers u and v meaning that when kids u and v are in the same room, they make a troublemaker pair. Kids are numbered from 1 to n.

Output
For each test case, output one line containing "Case #x:" followed by L - the number of kids who will be moved to a different class (in a different room). The next line should list those kids. The total number of troublemaker pairs in the two rooms must be at most m/2. If that is impossible, print "Impossible." instead of L and an empty line afterwards.

Sample Input	Sample Output
2 4 3 1 2 2 3 3 4 4 6 1 2 1 3 1 4 2 3 2 4 3 4	Case #1: 3 1 3 4 Case #2: 2 1 2

Problemsetter: Igor Naverniouk

題目描述：

搗蛋鬼的分班，搗蛋鬼兩兩存在會鬧事，分兩班使鬧事的情況減少一半。

題目解法：

目前是用隨機分班去做測試，不過這個做法不好，由於測資太弱了。可以說是假解吧

#include <stdio.h>
#include <stdlib.h>
int main() {
    int testcase, cases = 0;
    int u[5050], v[5050];
    int n, m, i, j, k;
    scanf("%d", &testcase);
    srand(514);
    while(testcase--) {
        scanf("%d %d", &n, &m);
        for(i = 0; i < m; i++)
            scanf("%d %d", &u[i], &v[i]);
        int Aclass[105] = {}, ret = 0;
        while(true) {
            for(i = 1; i <= n; i++)
                Aclass[i] = rand()%2;
            int trouble = 0;
            for(i = 0; i < m; i++) {
                if(Aclass[u[i]] != Aclass[v[i]])
                    trouble++;
            }
            if(trouble >= (m+1)/2)
                break;
        }
        for(i = 1; i <= n; i++)
            ret += Aclass[i];
        printf("Case #%d: %d\n", ++cases, ret);
        int st = 0;
        for(i = 1; i <= n; i++) {
            if(Aclass[i] == 1) {
                if(st) putchar(' ');
                st = 1;
                printf("%d", i);
            }
        }
        puts("");
    }
    return 0;
}

我要檢舉

#10982#Troublemakers#隨機#假解

台長： Morris

您可能對以下文章有興趣

[UVA][窮舉] 10001 - Garden of Eden

[UVA][spfa] 11338 - Minefield

[UVA] 471 - Magic Numbers

[UVA] 10488 - Swimming Gopher

人氣(881) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA] 11335 - Discrete Pursuit
此分類上一篇:[UVA][greedy] 11269 - Setting Problems

回應(0)