UVA

題目大意：給出一個N＊N的棋盤，上面放了一些車。現在要用盡量少的顏色對這些車進行染色，使得同一行同一列的任意兩個車的顏色不同

解題思路：首先，先統計一下需要染多少種顏色。
需要染多少種顏色，是由一行或者一列的車的最大數量決定的。
接著枚舉一下每種顏色（假設顏色為k種），再決定哪些地方需要染哪些顏色，決定哪些地方染哪些顏色，這就由二分圖匹配來決定了

首先，先建立這個二分圖。如何建立這個二分圖呢，將所有車的位置(i,j)，i和j連線
但是所有的車的位置(i,j)都連線了，在k次的枚舉下，並不能每次都能二分圖完美匹配，因為每次都完美匹配都需要n條匹配邊，而所提供的連線並不能保證有
所以我們得提供一下一些多余的線，使得每次都能完美匹配
那麼如何提供多余的線呢，首先我們可以記錄一下每行每列在車的連線上已經有多少個了
因為要有k次完美匹配，所以每行每列被連的次數必須等於k，所以現在的任務就是將這些未滿k的行和列進行連邊就可以了，這樣就可以保證每次都是完美匹配了
然後在完美匹配的情況下，再考慮所匹配的這個點是不是車就可以了

#include 
#include 
#include 
using namespace std;
#define N 110

int n, MaxColor;
int color[N][N], link[N], inRow[N], inCol[N];
char map[N][N];
bool vis[N];
vector G[N];

void init() {
    memset(inRow, 0, sizeof(inRow));
    memset(inCol, 0, sizeof(inCol));
    MaxColor = 0;

    scanf(%d, &n);
    for (int i = 0; i < n; i++) {
        G[i].clear();
        scanf(%s, map[i]);
        for (int j = 0; j < n; j++) {
            if (map[i][j] == '*') {
                inRow[i]++, inCol[j]++;
                G[i].push_back(j);
            }
        }
    }
    for (int i = 0; i < n; i++)
        MaxColor = max(MaxColor, max(inRow[i], inCol[i]));

    for (int i = 0; i < n; i++) if (inRow[i] < MaxColor) 
        for (int j = 0; j < n && inRow[i] < MaxColor; j++) {
            while (inRow[i] < MaxColor && inCol[j] < MaxColor) {
                inRow[i]++;
                inCol[j]++;
                G[i].push_back(j);
            }
        }
}

bool dfs(int u) {
    for (int i = 0; i < G[u].size(); i++) {
        int v = G[u][i];
        if (!vis[v]) {
            vis[v] = true;
            if (!(~link[v]) || dfs(link[v])) {
                link[v] = u;
                return true;
            }
        }
    }
    return false;
}

void hungary() {
    memset(link, -1, sizeof(link));
    for (int i = 0; i < n; i++) {
        memset(vis, 0, sizeof(vis));
        dfs(i);
    }
}

void solve() {
    memset(color, 0, sizeof(color));
    int cnt = 0;
    while (cnt < MaxColor) {
        ++cnt;
        hungary();
        for (int i = 0; i < n; i++) {
            int row = link[i];
            if (map[row][i] == '*') color[row][i] = cnt;
            for (int j = 0; j < G[row].size(); j++) 
                if (G[row][j] == i) {
                    G[row].erase(G[row].begin() + j);
                    break;
                }
        }
    }

    printf(%d
, MaxColor);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (j)
                printf( );
            printf(%d, color[i][j]);
        }
        printf(
);
    }

}

int main() {
    int test;
    scanf(%d, &test);
    while (test--) {
        init();
        solve();
    }
    return 0;
}