解題區/解題區 - Zerojudge

a576. No Cheating

contents

  1. 1. 題目
    1. 1.1. 內容：
    2. 1.2. 輸入說明：
    3. 1.3. 輸出說明：
    4. 1.4. 範例輸入：
    5. 1.5. 範例輸出：
  2. 2. 解法

題目

內容：

有個學校想辦一場考試，提供了 T 間教室。每間教室的座位都是 M×N 的矩陣(不同教室的 M, N 可以不一樣)，而有的座位壞掉了不能坐。此外，為了避免學生作弊，如下圖，對任何一個學生而言，他的左方、左前方、右方、右前方都不可以有人坐。請問每間教室所能容納的學生數最多為何？

輸入說明：

第一行有一個數字 T，代表學校有 T 間教室。接下來會有每個教室的資料，每筆資料會有在同一行兩個正整數 M, N，代表座位的配置是 M×N。接下來的 M 行，每行有 N 個字元，’.’代表那個座位是好的，而’x’則代表那個座位壞了。

輸出說明：

對於每間教室，輸出”Case #X: Y”, 其中 X 代表這是第幾間教室，而 Y 則代表這間教室能容納的學生數最大值。

範例輸入：

4
2 3
...
...
2 3
x.x
xxx
2 3
x.x
x.x
10 10
....x.....
..........
..........
..x.......
..........
x...x.x...
.........x
...x......
........x.
.x...x....

範例輸出：

Case #1: 4
Case #2: 1
Case #3: 2
Case #4: 46

解法

  • 作法：
    按列黑白染色，會發現不能連的位置恰好可以化成二分圖，求最大獨立集即可。
    最大獨立集 = 點個數 - 最大匹配數
a576.cpp
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
/**********************************************************************************/
/*  Problem: a576 "No Cheating" from GCJ 2008 Round 3 C                           */
/*  Language: CPP (3826 Bytes)                                                    */
/*  Result: AC(0.1s, 1.2MB) judge by this@ZeroJudge                               */
/*  Author: morris1028 at 2014-04-18 18:09:46                                     */
/**********************************************************************************/
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
using namespace std;
struct Node {
    int x, y, v;// x->y, v
    int next;
} edge[65536];
int e, head[6500], prev[6500], record[6500];
int level[6500], visited[6500];
void addEdge(int x, int y, int v) {
    edge[e].x = x, edge[e].y = y, edge[e].v = v;
    edge[e].next = head[x], head[x] = e++;
    edge[e].x = y, edge[e].y = x, edge[e].v = 0;
    edge[e].next = head[y], head[y] = e++;
}
bool buildLevelGraph(int s, int t) {
    memset(level, 0, sizeof(level));
    queue<int> Q;
    Q.push(s), level[s] = 1;
    while(!Q.empty()) {
        int tn = Q.front();
        Q.pop();
        for(int i = head[tn]; i != -1; i = edge[i].next) {
            int y = edge[i].y;
            if(edge[i].v > 0 && level[y] == 0) {
                level[y] = level[tn] + 1;
                Q.push(y);
            }
        }
    }
    return level[t] > 0;
}
int constructBlockingFlow(int s, int t) {
    int ret = 0;
    stack<int> stk;
    memset(visited, 0, sizeof(visited));
    stk.push(s);
    while(!stk.empty()) {
        int now = stk.top();
        if(now != t) {
            for(int i = head[now]; i != -1; i = edge[i].next) {
                int y = edge[i].y;
                if(visited[y] || level[y] != level[now] + 1)
                    continue;
                if(edge[i].v > 0) {
                    stk.push(y), prev[y] = now, record[y] = i;
                    break;
                }
            }
            if(stk.top() == now)
                stk.pop(), visited[now] = 1;
        } else {
            int flow = 1e+9, bottleneck;
            for(int i = t; i != s; i = prev[i]) {
                int ri = record[i];
                flow = min(flow, edge[ri].v);
            }
            for(int i = t; i != s; i = prev[i]) {
                int ri = record[i];
                edge[ri].v -= flow;
                edge[ri^1].v += flow;
                if(edge[ri].v == 0)
                    bottleneck = prev[i];
            }
            while(!stk.empty() && stk.top() != bottleneck)
                stk.pop();
            ret += flow;
        }
    }
    return ret;
}
int maxflowDinic(int s, int t) {
    int flow = 0;
    while(buildLevelGraph(s, t))
        flow += constructBlockingFlow(s, t);
    return flow;
}
int main() {
    int n, m;
    int testcase, cases = 0;
    int i, j, k, x, y;
    char g[128][128];
    int id[128][128];
    scanf("%d", &testcase);
    while(testcase--) {
        e = 0;
        memset(head, -1, sizeof(head));
        scanf("%d %d", &n, &m);
        for(int i = 0; i < n; i++)
            scanf("%s", g[i]);
        int ST[2] = {0, 0};
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(g[i][j] == '.') {
                    id[i][j] = ST[j&1]++;
                } else {
                    id[i][j] = -1;
                }
            }
        } 
        int source = ST[0] + ST[1];
        int sink = source + 1;
        for(int i = 0; i < ST[0]; i++)
            addEdge(source, i, 1);
        for(int i = 0; i < ST[1]; i++)
            addEdge(i + ST[0], sink, 1);
        int dx[] = {-1, -1, 0, 0, 1, 1};
        int dy[] = {-1, 1, -1, 1, 1, -1};
        int tx, ty, u, v;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j += 2) {
                if(id[i][j] == -1)  
                    continue;
                v = id[i][j];
                for(int k = 0; k < 6; k++) {
                    tx = i + dx[k];
                    ty = j + dy[k];
                    if(tx < 0 || ty < 0 || tx >= n || ty >= m)
                        continue;
                    u = id[tx][ty];
                    if(u == -1)
                        continue;
                    addEdge(v, u + ST[0], 1);
                }
            }
        }
        int ret = maxflowDinic(source, sink);
        printf("Case #%d: %d\n", ++cases, ST[0] + ST[1] - ret);
    }
    return 0;
}