解題區/解題區 - UVa

UVa 12052 - Cyber cafe

contents

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

Problem

給一張圖有 N 個節點、M 條邊，其中要放置 S 台新主機於其中 S 個節點，而沒放置的節點繼續使用舊主機，為了服務舊主機的網咖，每個舊節點旁邊最多只能有一個新主機網咖。

請問有多少種放置方法。

Sample Input

1
2
3
4
5
6
7
8
9
10
Dhaka
6 2 7
AB BC CD DE EF FA AD
Chittagong
4 3 4
AB AC AD BC
Sylhet
3 2 3
AB BC CA
TheEnd

Sample Output

1
2
3
4
5
6
7
Dhaka
9
Chittagong
1
Sylhet
0
TheEnd

Solution

對於每一個節點的連接方式用一個 32-bit 壓縮，接著窮舉所有可能放置方法 state，對於沒有放置的節點，直接壓縮結果與 state 做 AND 運算，算 bits 數是否都小於 2。

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
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int main() {
    char ss[1024];
    int n, s, p;
    while (scanf("%s", &ss) == 1) {
        printf("%s\n", ss);
        if (!strcmp(ss, "TheEnd"))
            break;
        scanf("%d %d %d", &n, &s, &p);
        int g[26][26] = {};
        for (int i = 0; i < p; i++) {
            scanf("%s", ss);
            int x = ss[0] - 'A', y = ss[1] - 'A';
            g[x][y] = g[y][x] = 1;
        }
        int mask[26] = {};
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                mask[i] |= g[i][j]<<j;
        int ret = 0;
        for (int i = (1<<n)-1; i >= 0; i--) {
            if (__builtin_popcount(i) == s) {
                int ok = 1;
                for (int j = 0; j < n && ok; j++) {
                    if ((i>>j)&1)	continue;
                    if (__builtin_popcount(mask[j]&i) >= 2)
                        ok = 0;
                }
                ret += ok;
            }
        }
        printf("%d\n", ret);
    }
    return 0;
}