[BZOJ1741][Usaco2005 nov]Asteroids 穿越小行星群 二分图最小点覆盖



给定网格图,一些格子里有陨石.每次能干掉一行或一列陨石,问最多几炮能清除所有陨石.
网格图问题往往与二分图有关,那么考虑将一个陨石想象成i行和j列之间的一条边,则要求的就是最少需要多少个点覆盖所有边.这是二分图最小点覆盖,它的大小等于最大匹配.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 1025
#define K 10233
#define rint register int
using namespace std;
const int inf=0x3f3f3f3f;
int n,k,s,t,head[N],to[K],nxt[K],f[K],tot=1;
inline void read(int &x)
{
    x=0;register char c=getchar();
    while(c>'9'||c<'0')c=getchar();
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
}
inline void add(int x,int y,int z)
{
    to[++tot]=y;f[tot]=z;nxt[tot]=head[x];head[x]=tot;
    to[++tot]=x;f[tot]=0;nxt[tot]=head[y];head[y]=tot;
}
int dis[N],q[N],l=1,r;
bool bfs()
{
    memset(dis,-1,sizeof dis);
    l=1,r=0;
    q[++r]=s;dis[s]=0;
    rint x,y,i;
    while(l<=r)
    {
        x=q[l++];
        for(i=head[x];i;i=nxt[i])if(dis[to[i]]==-1&&f[i])
        {
            dis[to[i]]=dis[x]+1;
            if(to[i]==t)return 1;
            q[++r]=to[i];
        }
    }
    return 0;
}
int dinic(int x,int flow)
{
    if(x==t)return flow;
    rint a,temp=flow;
    for(rint i=head[x];i;i=nxt[i])if(dis[to[i]]==dis[x]+1&&f[i])
    {
        a=dinic(to[i],min(f[i],temp));
        if(!a)dis[to[i]]=-1;
        temp-=a,f[i]-=a,f[i^1]+=a;
        if(!temp)return flow;
    }
    return flow-temp;
}
int maxflow()
{
    int re=0;
    while(bfs())re+=dinic(s,inf);
    return re;
}
int main()
{
    cin>>n>>k;
    s=0,t=n*2+1;
    for(rint x,y,i=1;i<=k;i++)
    {
        read(x),read(y);
        add(x,y+n,1);
    }
    for(rint i=1;i<=n;i++)add(s,i,1),add(i+n,t,1);
    cout<<maxflow();
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注