题目描述

在一张图上，用最少的不相交边覆盖所有的点。

样例

2
4
3
3 4
1 3
2 3
3
3
1 3
1 2
2 3

2
1

算法1

(二分图匹配) $O(nm)$

最小路径点覆盖模版。

我们把原图重建，$x,y$变为$x,y+n$，所以变成了$1~n$和$n+1~n+n$的拆点二分图。

最小路径即为$n-$新二分图最大匹配。

lyd的进阶指南上有详细证明。

C++ 代码

#include <iostream>
#include <cstdio>
using namespace std;
struct edge{
    int to,nxt;
}s[150*150];
int ls=1,head[250];
void link(int a,int b){
    s[ls].to=b;
    s[ls].nxt=head[a];
    head[a]=ls++;
}
int match[250];
int vis[250];
int xyl(int u){
    for(int i=head[u],y;i;i=s[i].nxt)
        if(!vis[y=s[i].to]){
            vis[y]=1;
            if(!match[y]||xyl(match[y])){
                match[y]=u;
                return 1;
            }
        }
    return 0;
}
int T,n,m,a,b;
int main(){
    cin>>T;
    while(T--){
        for(int i=0;i<=n*2;i++) head[i]=match[i]=0;
        ls=1;
        scanf("%d%d",&n,&m);
        for(int i=0;i<m;i++){
            scanf("%d%d",&a,&b);
            link(a,b+n);//建为拆点二分图
        }
        int ans=0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n*2;j++) vis[j]=0;
            ans+=xyl(i);//匹配
        }
        printf("%d\n",n-ans);
    }
    return 0;
}