joyoi1957 「Poetize5」Vani和Cl2捉迷藏

最小路径可重点覆盖。先传递闭包，然后拆点，\(n-\)最大匹配，看算法竞赛进阶指南。

#include <iostream>

#include <cstring>

#include <cstdio>

using namespace std;

int n, m, uu, vv, mat[205], ans;

bool w[205][205], vis[205];

bool hung(int x){

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

		if(w[x][i]){

			if(vis[i])	continue;

			vis[i] = true;

			if(!mat[i] || hung(mat[i])){

				mat[i] = x;

				return true;

			}

		}

	return false;

}

int main(){

	cin>>n>>m;

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

		scanf("%d %d", &uu, &vv);

		w[uu][vv] = true;

	}

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

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

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

				w[i][j] |= w[i][k] & w[k][j];

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

		memset(vis, 0, sizeof(vis));

		if(hung(i))	ans++;

	}

	cout<<n-ans<<endl;

	return 0;

}

巴特西

joyoi1957 「Poetize5」Vani和Cl2捉迷藏

最新文章

热门文章