二分图最大独立集&最小路径点覆盖

最新推荐文章于 2020-04-22 21:42:14 发布

置顶

Modestr-E·X·L

最新推荐文章于 2020-04-22 21:42:14 发布

阅读量541

点赞数

本文链接：https://blog.csdn.net/Modestr/article/details/105115984

版权

本文介绍了二分图的最大独立集和最小路径点覆盖问题。最大独立集求解方法是通过最大匹配来计算，文章通过[LGOJ]P3355和[LGOJ]P5030题目详细讲解了应用实例。最小路径点覆盖则可以通过转换为最大流问题来解决，以[LGOJ]P2764为例展示了求解过程。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

一.二分图最大独立集

定义：

对于一张无向图 $G (V, E)$ ，选出一个 $V$ 的子集 $S$ ，使得 $S$ 中任意两点之间都没有边，且 $S$ 是最大这样的子集。

求解方法：

二分图的最大独立集的点的数量=总点数N-最大匹配

简单的证明：要使得独立集越大，那么删掉的点就要越少，同时话要保证删掉的点覆盖到所有边，所以删掉的因该是最小点覆盖。

例题：

Example1:[LGOJ]P3355 骑士共存问题:

总结：

能攻击的点，颜色都是不一样的，颜色一0样就意味着不冲突，一定可以放骑士。
这是一张“二分图”，如果我们把冲突的两个格子连边，相当于隔开。
每一个格子都是一个点，而每个格子只能放一个骑士，能选出来多少格子，最大独立集就是骑士的数量
所以答案为 $n * n - m -$ 最大匹配数

注意奇数建图&偶数建图的差距，奇数建图会TLE！！！

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1000005;
const int maxm=5005;
const int dx[8]={
   -1,-2,-2,-1,1,2,2,1};
const int dy[8]={
   -2,-1,1,2,2,1,-1,-2};
int n,m,tot,ans;
bool ban[maxm][maxm],vis[maxn];
int match[maxn],head[maxn];
vector<int> nd;
struct node
{
   
	int from,next,to;
}edge[maxn];
inline int read()
{
   
	int s=0,f=1;
	char c=getchar();
	while (c<'0'||c>'9')
	{
   
		if (c=='-')
		{
   
			f=-1;
		}
		c=getchar();
	}
	while (c>='0'&&c<='9')
	{
   
		s=s*10+c-48;
		c=getchar();
	}
	return s*f;
}
inline void add(int x,int y)
{
   
	edge[++tot].next=head[x];
	edge[tot].from=x;
	edge[tot].to=y;
	head[x]=tot;
}
inline bool dfs(int u)
{
   
	for (int i=head[u];i;i=edge[i].next)
	{
   
		int v=edge[i].to;
		if (!vis[v])
		{
   
			vis[v]=1;
			if (match[v]==-1||dfs(match[v]))
			{
   
				match[v]=u;
				return 1;
			}
		}
	}
	return 0;
}
int main()
{
   
	n=read(),m=read();
	int x,y;
	for (int i=1;i<=m;i++)
	{
   
		x=read(),y=read();
		ban[x][y]=1;
	}
	for (int i=1;i<=n;i++)
	{
   
		for (int j=1;j<=n;j++)
		{
   
			if (!ban[i][j]&&(i+j)%2)
			{
   
				nd.push_back(n*(i-1)+j);
				for (int k=0;k<8;k++)
				{
   
					int cur_x=i+dx[k],cur_y=j+dy[k];
					if (cur_x<1||cur_x>n||cur_y<1||cur_y>n)
					{
   
						continue;
					}
					if (!ban[cur_x][cur_y])

最低0.47元/天解锁文章