解題區/解題區 - UVa

UVa 10615 - Rooks

contents

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

Problem

給一個 n x n 個棋盤，放置 * 於棋盤上，著色所有的 * 使得同行同列的 * 都是不同顏色。

使用最小顏色總數，給出一種可行解。

Input

1
2
3
4
5
6
7
8
9
10
11
2
2
*.
**
4
*.*.
*.*.
***.
..**

Output

1
2
3
4
5
6
7
8
2
2 0
1 2
4
1 0 2 0
3 0 1 0
2 1 3 0
0 0 4 1

Solution

最小著色數為同行同列的最多 * 總數
為了輸出可行解，進行二分匹配。對於著色座標 (row, column) = (i, j) 拉一條 i->j 的邊，匹配一條邊，相當於著色一個點。

假設最少著色數是 c，則進行補邊，使得二分圖的 X-Y 集合中的每一個點都是 degree = c。

進行 c 次的二分匹配，每一次匹配都是完美匹配，因符合性質｀degree = c。這一次的所有匹配邊 (i, j) 表示相同顏色。
每一次完美匹配，會將所有的 degree - 1，因此便能將所有邊使用完畢。這裏有 Hall’s marriage theorem 的意味在，來保證完美匹配的存在。

如果不補邊，每一次最大匹配若不是完美匹配，最大匹配會造成下一次匹配不一定是最大，c 次二分匹配後，會有殘留的邊！也就是造成點未著色。

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
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
// Hall's marriage theorem, bipartite graph matching, maxflow
// for all subset X sat. |X| <= |Neighborhood(X)| = |Y|
// 
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <queue>
#include <stack>
#include <assert.h>
#include <set>
using namespace std;
const int MAXV = 40010;
const int MAXE = MAXV * 200 * 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++];
    }
    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 main() {
    int testcase;
    int n, x, y;
    char s[128][128];
    
    scanf("%d", &testcase);
    while (testcase--) {
        
        scanf("%d", &n);
        for (int i = 0; i < n; i++)
            scanf("%s", s[i]);
            
        vector<int> bigraph[128];
        int row_deg[128] = {}, col_deg[128] = {};
        int place_color[128][128];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (s[i][j] == '*') {
                    row_deg[i]++, col_deg[j]++;
                    bigraph[i].push_back(j);
                }					
            }
        }
        
        int mx_colors = 0;
        for (int i = 0; i < n; i++) {
            mx_colors = max(mx_colors, row_deg[i]);
            mx_colors = max(mx_colors, col_deg[i]);
        }
        
        // increase edge, make perfect matching
        for (int i = 0; i < n; i++) {
            if (row_deg[i] < mx_colors) {
                for (int j = 0; j < n; j++) {
                    while (row_deg[i] < mx_colors && col_deg[j] < mx_colors) {
                        row_deg[i]++, col_deg[j]++;
                        bigraph[i].push_back(j);
                    }
                }
            }
        }
        
        // bipartite graph matching
        for (int color = 0; color < mx_colors; color++) {
            g.Init(2 * n + 2);
            int source = 2 * n, sink = 2 * n + 1;
            for (int i = 0; i < n; i++) {
                g.Addedge(source, i, 1), g.Addedge(i + n, sink, 1);
                for (int j = 0; j < bigraph[i].size(); j++)
                    g.Addedge(i, bigraph[i][j] + n, 1);
            }
            
            int matching = g.Maxflow(source, sink);
            assert(matching == n); // perfect matching
            // make sure, matching pair won't collision.
            for (int i = 0; i < n; i++) {
                for (Edge *p = g.adj[i]; p != NULL; p = p->next) {
                    int x = i, y = p->v, flow = p->flow;
                    if (flow == 0 && y - n >= 0 && y - n < n) {
                        // match x - (y - n) in bipartite graph
                        int r = x, c = y - n;
                        if (s[r][c] == '*')
                            place_color[r][c] = color;
                        // remove edge
                        bigraph[r].erase(find(bigraph[r].begin(), bigraph[r].end(), c));
                    }
                }
            }
        }
        
        for (int i = 0; i < n; i++)
            assert(bigraph[i].size() == 0);
        
        printf("%d\n", mx_colors);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (s[i][j] == '*')	printf("%d", place_color[i][j] + 1);
                else				printf("%d", 0);
                printf("%c", j == n-1 ? '\n' : ' ');
            }
        }
    }
    return 0;
}
/*
9999
4
****
****
****
****
4
***.
.***
.**.
....
4
****
.*.*
..**
...*
4
*...
.*..
..*.
...*
4
*...
.*..
..*.
..*.
2
*.
**
4
*.*.
*.*.
***.
..**
*/