POJ3041

Bessie 驾驶着他的太空飞船呆呆2号在太空旅行，途径一段危险地带，他希望自己能安全通过这段区域，于是他将这片区域的地图扫描进入了太空飞船，地图是一个N x N的网络 (1 <= N <= 500)，其中有K颗小行星 (1 <= K <= 10,000)。

还好Bessie有一个强力的武器能够一发光束将一整行或者一整列的小行星轰成灰烬。 这种光束的价格高昂，材料稀有，所以他希望更少的使用这个光束。现在把地图给你，你能帮Bessie计算一下，摧毁掉这些小行星至少需要几发光束。

Input

  • Line 1: 两个整数N和K，中间用空格隔开。
  • Lines 2…K+1: 每一行有两个整数R和C (1 <= R, C <= N) ，代表行和列，即小行星i的位置是(Ri,Ci)。

Output

  • Line 1: 输出一个整数表示最少需要几发光束。

Sample Input

3 4
1 1
1 3
2 2
3 2

Sample Output

2

分析：

建图用行和列 行->列 即每个坐标对应一个边 然后找最大匹配即为所求

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
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int mmap[555][555];//存图
int vis[555];
int match[555];//匹配过
int n;//总点数
bool dfs(int u)
{
    for (int v = 1; v <= n; v++)
    {
        if (mmap[u][v] && !vis[v])
        {
            vis[v] = true;
            if (match[v] == -1 || dfs(match[v]))
            {
                match[v] = u;
                return true;
            }
        }
    }
    return false;
}
int main()
{
    memset(mmap, 0, sizeof(mmap));
    int k;//边数
    scanf("%d%d", &n, &k);//n个点k个边
    int i, a, b;
    for (i = 0; i<k; i++)
    {
        scanf("%d%d", &a, &b);
        mmap[a][b] = 1;//连边a->b 要单向边
    }
    int sum = 0;//匹配数
    memset(match, -1, sizeof(match));//初始化为-1
    for (int i = 1; i <= n; i++)
    {
        memset(vis, 0, sizeof(vis));
        if (dfs(i))//是否有增广路，有的话匹配数+1
            sum++;
    }
    printf("%d\n", sum);
}