解題區/解題區 - UVa

UVa 12831 - Bob the Builder

contents

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

Problem

一台機器，每一次能產出其 X 的子孫、子孫的子孫 … 類推。

不會產生重複的子孫，把所有可能性產生，請問使用機器的最少次數為何？

Sample Input

1
2
3
4
5
2
1 36
20
2 40
8 20

Sample Output

1
2
Case 1: 2
Case 2: 3

Solution

一開始誤解題目，以為一次可以將數個的子孫都產出來，實際上只能拿一個 X 進去，並且將其單一後代產出。

也就是說，會看到一個 DAG 圖中，用最少路徑覆蓋所有的節點。這題同時也需要非常快速的二分匹配，舊的模板大概沒辦法通過這一題，至於需不需要貪心預流？根據之前測試點數非常多的圖，貪心預流效果在這個二分匹配下沒有很好的反應？

  • 题意：
    有向无环图中，需要多少条简单路可以覆盖整个图。

  • 建模：
    构造二分图。把原图的每个顶点i拆分成二分图X，Y集合中的两个顶点Xi和Yi。对于原图的边(i, i)，连接(Xi, Yj)，值为1，然后把二分图最大匹配模型转化为网络留模型，求最大流。

  • 分析：

    对于一个路径覆盖，有如下性质：

    1、每个顶点属于且只属于一个路径。
    2、路径上除终点外，从每个顶点出发只有一条边指向路径上的另一顶点。

    所以我们可以把每个顶点理解成两个顶点，一个是出发，一个是目标，建立二分图模型。该二分图的任何一个匹配方案，都对应了一个路径覆盖方案。如果匹 配数为0，那么显然路径数=顶点数。每增加一条匹配边，那么路径覆盖数就减少一个，所以路径数=顶点数 - 匹配数。要想使路径数最少，则应最大化匹配数，所以要求二分图的最大匹配。

    注意，此建模方法求最小路径覆盖仅适用于有向无环图，如果有环或是无向图，那么有可能求出的一些环覆盖，而不是路径覆盖。

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <queue>
#include <stack>
#include <assert.h>
#include <set>
#include <map>
using namespace std;
const int MAXV = 20010;
const int MAXE = MAXV * 300 * 2;
const int INF = 1<<29;
typedef struct Edge {
    int v, cap, flow;
    Edge *next, *re;
} Edge;
class MaxFlow {
    public:
    Edge edge[MAXE], *adj[MAXV], *pre[MAXV], *arc[MAXV];
    int e, n, level[MAXV], lvCnt[MAXV], Q[MAXV];
    void Init(int x) {
        n = x, e = 0;
        for (int i = 0; i < n; ++i) adj[i] = NULL;
    }
    void Addedge(int x, int y, int flow){
        edge[e].v = y, edge[e].cap = flow, edge[e].next = adj[x];
        edge[e].re = &edge[e+1], adj[x] = &edge[e++];
        edge[e].v = x, edge[e].cap = 0, edge[e].next = adj[y];
        edge[e].re = &edge[e-1], adj[y] = &edge[e++];
        assert(x < MAXV && y < MAXV);
        assert(e < MAXE);
    }
    void Bfs(int v){
        int front = 0, rear = 0, r = 0, dis = 0;
        for (int i = 0; i < n; ++i) level[i] = n, lvCnt[i] = 0;
        level[v] = 0, ++lvCnt[0];
        Q[rear++] = v;
        while (front != rear){
            if (front == r) ++dis, r = rear;
            v = Q[front++];
            for (Edge *i = adj[v]; i != NULL; i = i->next) {
                int t = i->v;
                if (level[t] == n) level[t] = dis, Q[rear++] = t, ++lvCnt[dis];
            }
        }
    }
    int Maxflow(int s, int t){
        int ret = 0, i, j;
        Bfs(t);
        for (i = 0; i < n; ++i) pre[i] = NULL, arc[i] = adj[i];
        for (i = 0; i < e; ++i) edge[i].flow = edge[i].cap;
        i = s;
        while (level[s] < n){
            while (arc[i] && (level[i] != level[arc[i]->v]+1 || !arc[i]->flow)) 
                arc[i] = arc[i]->next;
            if (arc[i]){
                j = arc[i]->v;
                pre[j] = arc[i];
                i = j;
                if (i == t){
                    int update = INF;
                    for (Edge *p = pre[t]; p != NULL; p = pre[p->re->v])
                        if (update > p->flow) update = p->flow;
                    ret += update;
                    for (Edge *p = pre[t]; p != NULL; p = pre[p->re->v])
                        p->flow -= update, p->re->flow += update;
                    i = s;
                }
            }
            else{
                int depth = n-1;
                for (Edge *p = adj[i]; p != NULL; p = p->next)
                    if (p->flow && depth > level[p->v]) depth = level[p->v];
                if (--lvCnt[level[i]] == 0) return ret;
                level[i] = depth+1;
                ++lvCnt[level[i]];
                arc[i] = adj[i];
                if (i != s) i = pre[i]->re->v;
            }
        }
        return ret;
    }
} g;
int visited[32767], N, L;
vector<int> D;
void dfs(int u) {
    if (visited[u])	return ;
    visited[u] = 1, D.push_back(u);
    for (int i = 0; (1<<i) <= u; i++)	 {
        if ((u>>i)&1) {
            int v = u + (1<<i);
            if (v <= L) {
                dfs(v);
                g.Addedge(u, v + L, 1);
            }
        }
    }
}
int main() {
    int testcase, cases = 0;
    int x, y, u, v;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &N, &L);
        assert(N > 0 && N <= 36);
        memset(visited, 0, sizeof(visited));
        D.clear();
        int A[10000 + 5];
        int source = 0, sink = 2 * L + 1;
        g.Init(2 * L + 5);
        for (int i = 0; i < N; i++) {
            scanf("%d", &A[i]);
            dfs(A[i]);
        }
        for (int i = 0; i < D.size(); i++) {
            g.Addedge(source, D[i], 1);
            g.Addedge(D[i] + L, sink, 1);
        }
        int ret = D.size() - g.Maxflow(source, sink);
        printf("Case %d: %d\n", ++cases, ret);
    }
    return 0;
} 
/*
99999
1 36
20
2 40
8 20
1 2
2
1 10
6
*/