理解了。。以sample为例，把行的点看做left集，列的点看做right集，我们可以画出如下图：
空格用*代替了。。怕没法填充。。

1————————1
*\
**\
2—-\——2
****\/
****/\
***/**\
**/****\
*/******\
3********3 
太佩服我了- -。。

其中每条边都代表一个障碍。。那么目的是要用最少的点消灭障碍，即图中的边，就是

最小覆盖： 最小覆盖要求用最少的点（左右两边的点）让每条边都至少和其中一个点关联。可以证明：最少的点（即覆盖数）＝最大匹配数，最大匹配用匈牙利算法，匈牙利不懂见这里：

http://imlazy.ycool.com/post.1603708.html

我的AC如下：

#include <stdio.h>
#include <string.h>
#define N 501
char map[N][N], used[N];
int match[N];

int find(int k, int n)
{
    int i;
    for (i = 1; i <= n; i++)
        if (map[k][i] && !used[i])
        {
            used[i] = 1;
            if (match[i] == -1 || find(match[i], n))
            {
                match[i] = k;
                return 1;
            }
        }
    return 0;
}

int hungary(int n)
{
    int i, res;
    memset(match, -1, sizeof(match));
    res = 0;
    for (i = 1; i <= n; i++)
    {
        memset(used, 0, sizeof(used));
        if (find(i, n)) res++;
    }
    return res;
}

int main(void)
{
    int n, k, i, r, c, res;
    scanf("%d%d", &n, &k);
    for (i = 0; i < k; i++)
    {
        scanf("%d%d", &r, &c);
        map[r][c] = 1;
    }
    printf("%d", hungary(n));
    return 0;
}

• Re:膜拜大牛！！ (0) ZJNU09220229 2010-09-25 21:32:46