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;
}