题目

在一个城市里有$n$个地点和$k$条道路，道路是无环的（也就是说一定可以二分染色——回路长度为偶数0），现在伞兵需要去n个地点视察，只能沿着路的方向走，问最少需要多少伞兵。

分析

这是什么问题？找出最少的边，访问所有的点——二分图的的最小路径覆盖。

那么对于一个最大匹配，它能覆盖（2最大匹配）个点，剩下的点都需要单独一条边覆盖，从而设匹配数为$k$，覆盖数为$p$，有$$n-2k+k=p$$，也就是$n-k=p$。

代码

#include <cstring>

#include <algorithm>

#include <vector>

#define MP make_pair

#define PB push_back

#define fi first

#define se second

#define ZERO(x) memset((x), 0, sizeof(x))

#define ALL(x) (x).begin(),(x).end()

#define rep(i, a, b) for (int i = (a); i <= (b); ++i)

#define per(i, a, b) for (int i = (a); i >= (b); --i)

#define QUICKIO                  \

    ios::sync_with_stdio(false); \

    cin.tie(0);                  \

    cout.tie(0);

#define MS(x,y) memset(x,y,sizeof(x))

using namespace std;

bool mat[125][125],vis[125];

int n,m;

int link[125];

bool dfs(int x)

{

	rep(i,1,n)

	{

		if(mat[x][i] && !vis[i])

		{

			vis[i]=true;

			if(link[i]==-1 || dfs(link[i]))

			{

				link[i]=x;

				return true;

			}

		}

	}

	return false;

}

int hungary()

{

	int ans=0;

	rep(i,1,n)

	{

		ZERO(vis);

		if(dfs(i)) ans++;

	}

	return ans;

}

int main()

{

	int T; scanf("%d",&T);

	while(T--)

	{

		scanf("%d%d",&n,&m);

		ZERO(mat);

		ZERO(vis);

		MS(link,-1);

		rep(i,1,m)

		{

			int a,b;

			scanf("%d%d", &a, &b);

			if(a && b) mat[a][b]=1;

		}

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

	}

	return 0;

}

巴特西

「专题训练」Air Raid（HDU-1151）

题目

分析

代码

最新文章

热门文章