解題區/解題區 - UVa

UVa 953 - The Incredible Pile Machine

contents

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

Problem

現在有 N 堆，總共有 N 種物品，希望移動最少次，使得每一堆只具有單一種物品。

輸出最小的組合方案。按照第 i 種物品放置在第 j 堆的字典順序最小。

Sample Input

1
2
3
4
5
6
7
4
3 2 3 4 0 0 2 1 3 1
3 66 66 0 66 66 0 66 66 66
6 476 357 874 50 594 394 320 803 817 348 252 940 453 500 647 299
94 143 800 947 561 885 389 172 301 276 612 130 540 731 774 306 96
239 227 907
2 99 1 1 99

Sample Output

1
2
3
4
021 9
012 264
251340 12741
01 2

Solution

很明顯地答案會是在某一堆 X 指派給 A 物品，那麼可以減少的移動次數是 X 原本具有 A 的數量。因此答案會是物品述兩總和扣除最大權匹配。

但是答案特別要求輸出字典順序要最小，所以用 KM 算法、最少費用流會稍微麻煩一點，也許多做 $O(N^2)$ 次的窮舉也可以完成。這裡使用 bitmask 的方式去找到最順序最小的最大權匹配。

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 10;
int dp[MAXN][1<<MAXN], used[MAXN][1<<MAXN];
int main() {
    int testcase, N;
    int type[20][20];
    scanf("%d", &testcase);
    while (testcase--) {
    	scanf("%d", &N);
    	
    	int sum = 0;
    	for (int i = 0; i < N; i++) {
    		for (int j = 0; j < N; j++)
    			scanf("%d", &type[i][j]), sum += type[i][j];
    	}
    	    	
    	memset(dp, 0, sizeof(dp));
    	memset(used, 0, sizeof(used));
    	for (int i = 0; i < N; i++)
    		dp[0][1<<i] = type[0][i];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < (1<<N); j++) {
                for (int k = 0; k < N; k++) {
                    if ((j>>k)&1)	continue;
                    dp[i+1][j|(1<<k)] = max(dp[i+1][j|(1<<k)], dp[i][j] + type[i+1][k]);
                }
            }
        }
        
        used[N-1][(1<<N) - 1] = 1;
        for (int i = N-2; i >= 0; i--) {
            for (int j = 0; j < (1<<N); j++) {
                for (int k = 0; k < N; k++) {
                    if ((j>>k)&1)	continue;
                    if (used[i+1][j|(1<<k)] && dp[i+1][j|(1<<k)] == dp[i][j] + type[i+1][k])
                        used[i][j] = 1;
                }
            }
        }
        int ret = dp[N-1][(1<<N)-1];
        for (int i = 0, p, q = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if ((q>>j)&1)
                    continue;
                if (used[i][q|(1<<j)]) {
                    p = j, q |= 1<<j;
                    break;
                }
            }
            printf("%d", p);
        }
        printf(" %d\n", sum - ret);
    }
    return 0;
}