网络流与二分图之最大独立集问题

也许更好的阅读体验

最大独立集问题

在Ｎ个点的图G中选出m个点，使这m个点两两之间没有边．求m最大值．（如果图Ｇ满足二分图条件）可以用二分图匹配来做,也可用网络流解决．

答案等于总点数-最大匹配数

证明：
设M为总点集，S为最大独立集,B为最大匹配中的点集
|X|为点集X的点数

有|S|>=|M|-|B|/2 　|B|/2为最大匹配数
证明：
如果是完美匹配就不用说了|S|=|M|-|B|/2
首先有 |S|>=|M|-|B|,|M|-|B|即为除去最大匹配点集后剩下的点集中的点数
这些点集都是没有边相连的（有就说明不是最大匹配）
接下来我们考虑在B中的点可不可以也放入现在的S中
设a点为B中的某个点
若a点与M-B中的某个点相连
设b为M-B中的与a相连点
有a的匹配点与b不相连（否则就不是二分图）
然后a的匹配点也不与M-B中的点相连（否则就不是最大匹配）
所以可以将a的匹配点放入S
若a点不与任何M-B中的点相连
则可以将a放入S中
也就是一个匹配至少可以放入一个点进去，所以可以放入|B|/2个点进去
所以有|S|>=|M|-|B|+|B|/2
即|S|>=|M|-|B|/2
又有|S|＜=|M|-|B|/2
证明：
在B中的点都是两两相连的，所以|B|/2个点不能在S中
即|S|＜=|M|-|B|/2
所以|S|=|M|-|B|/2

来看一个经（jian）典（dan）的问题

有一些n个男生和m个女生，他们中有k对互相对对方有好感，每个人可能和多个人有好感度，每一对有好感度的人就可以凑成一对情侣，现在你要邀请他们中的一些人一起来玩耍，但是作为单身狗的你是不想见到情侣在一起的，你想知道你最多可以和多少人一起玩耍。
输入格式
一行三个整数n，m，k
接下来k行每行2个整数a，b，表示a号男生与b号女生相互有好感
输出格式
一行表示答案

首先男生和男生之间是不会有好感的，那么男生和女生就形成一个二分图
我们自己画一个图，将男生和女生分为两部，左部是男生，右部是女生

1号男生同时和2,4号女生有好感，2号男生只和4号女生有好感，3号男生和1,3号女生互相有好感， 4号男生只和3号女生互相有好感。
那么最多可以邀请4个人一起玩
（一）四个男生或者四个女生
（二）1,2号男生，1,3号女生
（三）3,4号男生，2,4号女生。

相信你也看出来了，题目的要求就是最多可以有多少个互相没有边的点，即最大独立集
所以把这个二分图的最大匹配求出来后用总点数减去即可

互相攻击类型

这一类的题目大多数是给一个棋盘，上面的点有攻击范围，问最多可以放多少个棋子使其不会互相攻击
如骑士共存问题,长脖子鹿放置,攻击装置.
这一类的题目通常的解法
先找相互之间绝对不会有联系的点（如上面例题中的男生全部放在左边）
需要的话考虑加边顺序会带来的影响，如怎样会使找增广路次数最少，一般就是左部的选择。
建边，不能放置的点就不要连边了。
注，尽管匈牙利算法打起来简单一些，但是对于某些题目，网络流速度会快一些
下面以长脖子鹿放置作为例题讲一下。
我们发现，奇数行的点只打偶数行的点，偶数行的点只打奇数行的点，那么把奇数行的点看做左部，偶数行的点看做右部即可。
由于出题人卡了数据，所以匈牙利是过不去的。
代码

/******************************* Author:Morning_Glory LANG:C++ Created Time:2019年03月23日 星期六 15时47分47秒 *******************************/
#include <cstdio>
#include <fstream>
#include <cstring>
#include <queue>
#include <algorithm>
#define inf 123456789
using namespace std;
const int maxn = 1000006;
const int maxm = 305;
const int dirx [] = {-1,-3,-3,-1,1,3,3,1};
const int diry [] = {3,1,-1,-3,-3,-1,1,3};
struct IO{
	template<typename T>
	IO & operator>>(T&res){
		res=0;
		bool flag=false;
		char ch;
		while((ch=getchar())>'9'||ch<'0')	flag|=ch=='-';
		while(ch>='0'&&ch<='9') res=(res<<1)+(res<<3)+(ch^'0'),ch=getchar();
		if (flag)	 res=~res+1;
		return *this;
	}
}cin;
int n,m,x,y,k,cnt=-1,ans,s,t;
int head[maxn],cur[maxn],nxt[maxn],to[maxn],w[maxn],dep[maxn];
bool prv[maxm][maxm];
inline int loc (int x,int y)
{
	return (x-1)*n+y;
}
inline void add (int u,int v,int val)
{
	nxt[++cnt]=head[u],head[u]=cnt,to[cnt]=v,w[cnt]=val;
}
inline bool bfs ()
{
	queue<int> q;
	for (int i=0;i<=t;++i)	dep[i]=0,cur[i]=head[i];
	q.push(s);
	dep[s]=1;
	while (!q.empty()){
		int x=q.front();
		q.pop();
		for (int e=head[x];~e;e=nxt[e])
			if (!dep[to[e]]&&w[e]>0){
				dep[to[e]]=dep[x]+1;
				if (to[e]==t)	return true;
				q.push(to[e]);
			}
	}
	return false;
}
int dfs (int x,int dist)
{
	if (x==t)	return dist;
	for (int &e=cur[x];~e;e=nxt[e]){
		if (dep[to[e]]==dep[x]+1&&w[e]>0){
			int di=dfs(to[e],min(dist,w[e]));
			if (di){
				w[e]-=di;
				w[e^1]+=di;
				return di;
			}
		}
	}
	return 0;
}
inline int Dinic ()
{
	int ans=0;
	while (bfs())
		while (int d=dfs(s,inf))	ans+=d;
	return ans;
}
//以上为正常Dinic
int main()
{
	memset(head,-1,sizeof(head));
	cin>>n>>m>>k;
	ans=n*m-k;
	t=loc(n,m)+1;
	for (int i=1;i<=k;++i){
		cin>>x>>y;
		prv[x][y]=true;
	}
	for (int i=1;i<=n;++i)
		for (int j=1;j<=m;++j)
			if (!prv[i][j]){
				if (i&1)	add(s,loc(i,j),1),add(loc(i,j),s,0);
				else		add(loc(i,j),t,1),add(t,loc(i,j),0);
			}
	for (int i=1;i<=n;++i)
		for (int j=1;j<=m;++j){
			if (prv[i][j]||!(i&1))	continue;
			for (int k=0;k<=7;++k){
				x=i+dirx[k],y=j+diry[k];
				if (x<1||x>n||y<1||y>m||prv[x][y])	continue;
				add(loc(i,j),loc(x,y),inf),add(loc(x,y),loc(i,j),0);
			}
		}
	printf("%d\n",ans-Dinic());
	return 0;
}