学步园

题意：给定一个r*c的矩形格，对于矩形格中的每一列里面都会有两个格子的颜色是白色，其它的全是黑色。r<=c，问每一列选哪个白格子最终可以使得每一行都有被选的白格子。

题解：偶图吧，因为每一列都一定要选一个白格子，且行数小于等于列数。因此，拿行数去匹配，偶图中的边就是白格所对应的行列坐标。这样当得到最大匹配时，要想选定的白格子分布在所有行中，则最大匹配为行数。此时从第一列开始输出，若这一列选的白格是最大匹配中的一个，则输出与其匹配的行号，若不是，则输出任意一个白格的行号。如果最大匹配不等于行数，则说明选定的白格子不能覆盖所有的行，因此输出NO。

代码：

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;

const int MAX_ = 1010;

int vs[MAX_];
int link[MAX_];
bool mp[MAX_][MAX_], vis[MAX_];
int r, c;

int dfs(int k) {
    for(int i = 1; i <= c; i++) {
        if(!vis[i] && mp[k][i]) {
            vis[i] = 1;
            if(link[i] ==-1 || dfs(link[i])) {
                link[i] = k;
                vs[k] = i;
                return 1;
            }
        }
    }
    return 0;
}

void bfs() {
    int ans = 0;
    memset(link,-1,sizeof(link));
    memset(vs,0,sizeof(vs));
    for(int i = 1; i <= r; i++) {
        if(!vs[i]) {
            memset(vis,0,sizeof(vis));
            if(dfs(i))ans++;
        }
    }
    if(ans == r) {
        for(int j = 1; j <= c; j ++) {
            if(link[j] != -1) {
                printf("%d ",link[j]);
            } else {
                for(int i = 1; i <= r; i++) {
                    if(mp[i][j]) {
                        printf("%d ",i);
                        break;
                    }
                }
            }
        }
        putchar('\n');
        return ;
    }
    printf("NO\n");
    return ;
}

int main() {
    int Case, a, b;
    scanf("%d",&Case);
    while(Case--) {
        scanf("%d%d",&r,&c);
        memset(mp,0,sizeof(mp));
        for(int i = 1; i <= c; i ++) {
            scanf("%d%d",&a,&b);
            mp[a][i] = mp[b][i] = 1;
        }
        bfs();
    }
    return 0;
}