题目描述
在一张图上,用最少的不相交边覆盖所有的点。
样例
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;
}