DAG图上可相交最小路径覆盖

先求给定DAG的传递闭包,将任意相连的两点加入二分图中,然后就是经典的不相交最小路径覆盖

所谓传递闭包就是将DAG图中任意点间的连通关系处理出来,用Floyd即可

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cstdlib>

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 fh*rv;

}

int n,m,dis[505][505],g[505][505],match[505];

bool f[505];

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(){

	while(1){

		n=init();m=init();

		if(!n&&!m) break;

		memset(dis,0,sizeof(dis));

		memset(g,0,sizeof(g));

		memset(match,0,sizeof(match));

		for(int i=1;i<=m;i++){

			int u=init(),v=init();

			dis[u][v]=1;

		}

		for(int k=1;k<=n;k++){

			for(int j=1;j<=n;j++){

				for(int i=1;i<=n;i++){

					dis[i][j]=dis[i][j]||(dis[i][k]&&dis[k][j]);

				}

			}

		}

		for(int i=1;i<=n;i++){

			for(int j=1;j<=n;j++){

				if(dis[i][j]) g[i][++g[i][0]]=j;

			}

		}

		int ans=0;

		for(int i=1;i<=n;i++){

			memset(f,0,sizeof(f));

			if(hungarian(i)) ans++;

		}

		printf("%d\n",n-ans);

	}

}