POJ 1719 二分图最大匹配（记录路径）

Shooting Contest

Time Limit: 1000MS		Memory Limit: 10000K
Total Submissions: 4097		Accepted: 1499		Special Judge

Description

Welcome to the Annual Byteland Shooting Contest. Each competitor will shoot to a target which is a rectangular grid. The target consists of r*c squares located in r rows and c columns. The squares are coloured white or black. There are exactly two white squares and r-2 black squares in each column. Rows are consecutively labelled 1,..,r from top to bottom and columns are labelled 1,..,c from left to right. The shooter has c shots. 

A volley of c shots is correct if exactly one white square is hit in each column and there is no row without white square being hit. Help the shooter to find a correct volley of hits if such a volley exists. 
Example 
Consider the following target: 

Volley of hits at white squares in rows 2, 3, 1, 4 in consecutive columns 1, 2, 3, 4 is correct. 
Write a program that: verifies whether any correct volley of hits exists and if so, finds one of them.

Input

The first line of the input contains the number of data blocks x, 1 <= x <= 5. The following lines constitute x blocks. The first block starts in the second line of the input file; each next block starts directly after the previous one. 

The first line of each block contains two integers r and c separated by a single space, 2 <= r <= c <= 1000. These are the numbers of rows and columns, respectively. Each of the next c lines in the block contains two integers separated by a single space. The integers in the input line i + 1 in the block, 1 <= i <= c, are labels of rows with white squares in the i-th column. 

Output

For the i-th block, 1 <= i <= x, your program should write to the i-th line of the standard output either a sequence of c row labels (separated by single spaces) forming a correct volley of hits at white squares in consecutive columns 1, 2, ..., c, or one word NO if such a volley does not exists.

Sample Input

2
4 4
2 4
3 4
1 3
1 4
5 5
1 5
2 4
3 4
2 4
2 3

Sample Output

2 3 1 4
NO

Source

CEOI 1997

 

题目意思：

有n*m的格子，每个格子要么是白色要么是黑色。题目给定每列有2个白色的格子，其他的格子为黑色。每列选出一个白色的格子，使得每一行至少有一个白色格子被选出，若能满足条件则输出每列选出白色格子的行数，否则输出NO。

 

思路：

列标号放在左边，行标号放在右边，若该列a可选择第b行和第c行，则a-b连边，a-c连边。

在增广过程中记录to[i]和from[j]即第i列选择的行的标号和第j行被选择的列的标号。

init：to 0;from -1

1、若n>m，一定不可满足条件

2、若增广结束后存在from[i]=-1，则第i行一定不能被选择，输出NO

3、若增广结束后存在to[i]=0，那么第i列选择a和b其中一个即可。

 

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <set>
using namespace std;

#define N 1005
#define inf 999999999

int max(int x,int y){return x>y?x:y;}
int min(int x,int y){return x<y?x:y;}
int abs(int x,int y){return x<0?-x:x;}

int from[N];
int to[N];
bool visited[N];
int n, m;
vector<int>ve[N];

int march(int u){
    int i, v;
    for(i=0;i<ve[u].size();i++){
        v=ve[u][i];
        if(!visited[v]){
            visited[v]=true;
            if(from[v]==-1||march(from[v])){
                from[v]=u;
                to[u]=v;
                return 1;
            }
        }
    }
    return 0;
}

main()
{
    int t, i, j, k, u, v;
    cin>>t;
    while(t--){
        scanf("%d %d",&n,&m);
        for(i=0;i<=m;i++) ve[i].clear();
        for(i=1;i<=m;i++){
            scanf("%d %d",&u,&v);
            ve[i].push_back(u);
            ve[i].push_back(v);
        }
        if(n>m) {
            printf("NO
");continue;
        }
        memset(from,-1,sizeof(from));
        int num=0;
        for(i=1;i<=m;i++){
            memset(visited,false,sizeof(visited));
            march(i);
        }
        int f=1;
        for(i=1;i<=n;i++){
            if(from[i]==-1){
                f=0;break;
            }
        }
        if(!f){
            printf("NO
");continue;
        }
        for(i=1;i<=m;i++){
            if(!to[i]){
                to[i]=ve[i][0];
            }
        }
        printf("%d",to[1]);
        for(i=2;i<=m;i++) printf(" %d",to[i]);
        cout<<endl;
    }
}