UVa 10615 - Rooks

#图论 #二分图完美匹配
Published on 2015-12-24

题目地址

描述

给出一个 n×n(n≤100)n\times n(n \le 100) 的矩阵，有一些格子上放了车子，用 * 表示，你要用尽量少的颜色为他们染色，使得同一行以及同一列两辆车颜色均不相同，并输出方案。

样例输入

2
2
*.
**
4
*.*.
*.*.
***.
..**

样例输出

2
2 0
1 2
4
1 0 2 0
3 0 1 0
2 1 3 0
0 0 4 1

分析

简单分析可以知道，由于每行每列的车子的颜色都不能相同，所以需要的最少颜色数 ansans 一定是车子最多的行/列的的车子数量。问题关键在于如何构造解。
我们利用二分图完美匹配解决，左侧 XX 集为行，右侧 YY 集为列，对于车子坐标 (i,j)(i,j)，我们连接左侧标号为 ii 与右侧标号为 jj 的节点，于是我们把车子抽象为边，目标是给这些边染色。
可以观察到，由于同行列车子颜色不能相同，如果我们求出了一个完美匹配，那么匹配边（代表着某个车子）之间一定是没有冲突的。每一次的匹配边都可以染成相同的颜色，之后将其删去。每一次匹配所有的点度 - 1，故 ansans 次完美匹配就行了。
比较关键的一点是补边的操作，每一次最大匹配若不是完美匹配，最大匹配会造成下一次匹配不一定是最大， ansans 次二分匹配后，可能会有边未被染色，所以要补边。细节见代码。

代码

//  Created by Sengxian on 12/24/15.
//  Copyright (c) 2015年 Sengxian. All rights reserved.
//  Uva 10615 完美匹配+补边
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
using namespace std;
const int maxn = 100 + 3;
bool real[maxn][maxn], s[maxn], t[maxn];
int n, inrow[maxn], incow[maxn], match[maxn], col[maxn][maxn], w[maxn][maxn];

bool dfs(int u) {
    s[u] = true;
    for(int v = 0; v < n; ++v)
        if(w[u][v] > 0 && !t[v]) {
            t[v] = true;
            if(match[v] == -1 || dfs(match[v])) {
                match[v] = u;
                return true;
            }
        }
    return false;
}

int bipartite() {
    int cnt = 0;
    fill(match, match + n, -1);
    for(int i = 0; i < n; ++i) {
        fill(s, s + n, false);
        fill(t, t + n, false);
        cnt += dfs(i);
    }
    return cnt;
}

inline void relax(int &a, int b) {
    if(b > a) a = b;
}

inline int ReadInt() {
    int n = 0, ch = getchar();
    while(ch < '0' || ch > '9') ch = getchar();
    do {
        n = n * 10 + ch - '0';
        ch = getchar();
    }while(ch >= '0' && ch <= '9');
    return n;
}

int main() {
    int caseNum = ReadInt();
    while(caseNum--) {
        n = ReadInt();
        fill(inrow, inrow + n, 0);
        fill(incow, incow + n, 0);
        for(int i = 0; i < n; ++i) {
            for(int j = 0; j < n; ++j) {
                w[i][j] = real[i][j] = getchar() == '*';
                if(real[i][j]) inrow[i]++, incow[j]++;
            }
            while(getchar() == ' ');
        }
        int ans = 0;
        for(int i = 0; i < n; ++i) relax(ans, max(inrow[i], incow[i]));
        for(int i = 0; i < n; ++i)
            if(inrow[i] < ans)
                for(int j = 0; j < n; ++j) {
                    //需用while，防止补不满，能补则补
                    while(inrow[i] < ans && incow[j] < ans) {
                        inrow[i]++; incow[j]++;
                        w[i][j]++; //w[i][j] 表示 i -> j 一共有几条边
                    }
                }
        for(int i = 1; i <= ans; ++i) {
            bipartite();
            for(int j = 0; j < n; ++j) {
                if(match[j] == -1) continue;
                if(real[match[j]][j]) col[match[j]][j] = i;
                w[match[j]][j]--;
            }
        }
        printf("%d\n", ans);
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < n; ++j)
                printf("%d%c", real[i][j] ? col[i][j] : 0, j + 1 == n ? '\n' : ' ');
    }
    return 0;
}
UVa 1459 - Flowers Placement