CUGB图论专场2：B - Asteroids 二分图：最小顶点覆盖=最大匹配数

3 4
1 1
1 3
2 2
3 2

2

题意：就是横纵坐标求出x或者y，即点覆盖边，即是求最小点覆盖。

例如：样例中的取x=1和y=2就可以灭掉所以的星星，就是二分图中左顶点集的1点和右顶点集的2点，就可以把二分图覆盖完了（横坐标x为左顶点集，纵坐标y为右顶点集。

最小点覆盖：假如选了一个点就相当于覆盖了以它为端点的所有边，你需要选择最少的点来覆盖图的所有的边。

这题看了学习资料，学习匈牙利算法就懂了。不过还要学习二分图最大匹配的K?nig定理：最小点覆盖数 = 最大匹配数。

所以求最小顶点覆盖等于求最大匹配数，而最大匹配数用匈牙利算法可以求出……

因为要用二分图求，所以得有左顶点集和右顶点集，而从样例中可以知道x和y是互斥的，所以可以设x为左顶点集，y为右顶点集。

邻接表：0ms可以AC。

#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <list>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <set>
#define PI acos(-1.0)
#define mem(a,b) memset(a,b,sizeof(a))
#define sca(a) scanf("%d",&a)
#define pri(a) printf("%d\n",a)
#define MM 10002
#define MN 505
#define INF 168430090
using namespace std;
typedef long long ll;
int n,k,m,pre[MN],vis[MN];//pre为y匹配点x，即匹配的前一结点
int cnt,head[MM]; //邻接表，邻接矩阵也可以，不过邻接表空点不用判断，省时
struct node
{
    int x,y,next;
} e[MM];
int dfs(int x)
{
    for(int y,i=head[x]; i!=-1; i=e[i].next)
    {
        y=e[i].y;
        if(!vis[y])
        {
            vis[y]=1;
            if(pre[y]==0||dfs(pre[y])) //dfs前向结点，如果为真说明找到增广路
            {
                pre[y]=x; //把匹配的变成未匹配，未匹配的变成匹配，故匹配数+1，因为未匹配数比匹配数大1
                return 1;
            }
        }
    }
    return 0;
}
void search()
{
    for(int x=1; x<=n; x++) //从左顶点集开始判断，匈牙利算法思想
    {
        mem(vis,0);
        m+=dfs(x);
    }
}
int main()
{
    cin>>n>>k;
    mem(head,-1);
    for(int x,y,i=0; i<k; i++)
    {
        scanf("%d%d",&x,&y);
        e[cnt].y=y; e[cnt].next=head[x];
        head[x]=cnt++;
    }
    search();
    cout<<m<<endl;
    return 0;
}

#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <list>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <set>
#define PI acos(-1.0)
#define mem(a,b) memset(a,b,sizeof(a))
#define sca(a) scanf("%d",&a)
#define pri(a) printf("%d\n",a)
#define MM 10002
#define MN 505
#define INF 168430090
using namespace std;
typedef long long ll;
int n,k,m,pre[MN],vis[MN],Map[MN][MN];
int dfs(int x)
{
    for(int y=1;y<=n;y++)
    {
        if(!vis[y]&&Map[x][y])
        {
            vis[y]=1;
            if(pre[y]==0||dfs(pre[y])) //dfs前向结点，如果为真说明找到增广路
            {
                pre[y]=x; //把匹配的变成未匹配，未匹配的变成匹配，故匹配数+1，因为未匹配数比匹配数大1
                return 1;
            }
        }
    }
    return 0;
}
void search()
{
    for(int x=1; x<=n; x++) //从左顶点集开始判断，匈牙利算法思想
    {
        mem(vis,0);
        m+=dfs(x);
    }
}
int main()
{
    cin>>n>>k;
    for(int x,y,i=0; i<k; i++)
    {
        scanf("%d%d",&x,&y);
        Map[x][y]=1;
    }
    search();
    cout<<m<<endl;
    return 0;
}

CUGB图论专场2：B - Asteroids 二分图：最小顶点覆盖=最大匹配数

原文：http://blog.csdn.net/u011466175/article/details/19237777