bzoj1741 [Usaco2005 nov]Asteroids 穿越小行星群 最小点覆盖

链接

https://www.lydsy.com/JudgeOnline/problem.php?id=1741

思路

消除所有的小行星
每个点(x,y)只有选择x或者y才能被覆盖
二分图最小点覆盖=最大流

首先，最小顶点覆盖一定>=最大匹配，因为假设最大匹配为n，那么我们就得到了n条互不相邻的边，光覆盖这些边就要用到n个点。剩下的点就不用去管他，要不然m就!=最大匹配
不明白就去这里
左边横边，右边竖边
然后开心的跑最大流就可以

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
const int N=5e5+7,inf=0x3f3f3f3f;
using namespace std;
int read() {
    int x=0,f=1;char s=getchar();
    for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;
    for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';
    return x*f;
}
int n,m,S,T;
struct node {
    int v,nxt,cap;
}e[N<<1];
int head[N<<1],cnt=1;
void add_edge(int u,int v,int cap) {
    e[++cnt].v=v;
    e[cnt].cap=cap;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}
void Add(int u,int v,int cap) {
    add_edge(u,v,cap);
    add_edge(v,u,0);
}
int dis[N];
bool bfs() {
    queue<int> q;
    memset(dis,-1,sizeof(dis));
    q.push(S);
    dis[S]=0;
    while(!q.empty()) {
        int u=q.front();
        q.pop();
        for(int i=head[u];i;i=e[i].nxt) {
            int v=e[i].v;
            if(dis[v]==-1&&e[i].cap) {
                dis[v]=dis[u]+1;
                q.push(v);
            }
        }
    }
    return dis[T]!=-1;
}
int dfs(int u,int f) {
    if(u==T) return f;
    int rest=f;
    for(int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v;
        if(e[i].cap&&dis[v]==dis[u]+1&&rest) {
            int t=dfs(v,min(e[i].cap,rest));
            if(!t) dis[v]=0;
            e[i].cap-=t;
            e[i^1].cap+=t;
            rest-=t;
        }
    }
    return f-rest;
}
int dinic() {
    int ans=0;
    while(bfs())
        ans+=dfs(S,inf);
    return ans; 
}
int main() {
//  freopen("a.in","r",stdin);
    n=read(),m=read();
    S=1001,T=1002;
    for(int i=1;i<=n;++i) Add(S,i,1),Add(i+n,T,1);
    for(int i=1;i<=m;++i) {
        int x=read(),y=read();
        Add(x,y+n,1);
    }
    int ans=dinic();
    printf("%d\n",ans);
}