二分图匹配求DAG图上的最小路径覆盖
应用了拆点的思想,将DAG图上的每一个点拆成二分图的x集合与y集合,对于一条有向边u->v来说,我们在ux与vy之间连一条边,然后求二分图的最大匹配
DAG图上的最小路径覆盖数=DAG图上的顶点数-二分图最大匹配数.这是路径不能重合的情况,对于路径可以重合的来说,用传递闭包做
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
int init(){
int rv=0,fh=1;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-') fh=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
rv=(rv<<1)+(rv<<3)+c-'0';
c=getchar();
}
return rv*fh;
}
int T,m,n,g[150][150],match[150];
bool f[150];
bool hungarian(int u){
for(int i=1;i<=g[u][0];i++){
int v=g[u][i];
if(!f[v]){
f[v]=1;
if(!match[v]||hungarian(match[v])){
match[v]=u;
return 1;
}
}
}
return 0;
}
int main(){
T=init();
while(T--){
n=init();m=init();
memset(g,0,sizeof(g));
memset(match,0,sizeof(match));
for(int i=1;i<=m;i++){
int u=init(),v=init();
g[u][++g[u][0]]=v;
}
int ans=0;
for(int i=1;i<=n;i++){
memset(f,0,sizeof(f));
if(hungarian(i)) ans++;
}
cout<<n-ans<<endl;
}
return 0;
}