網(wǎng)絡(luò)流與二分圖之最大獨(dú)立集問題

也許更好的閱讀體驗(yàn)

最大獨(dú)立集問題

在Ｎ個(gè)點(diǎn)的圖G中選出m個(gè)點(diǎn)，使這m個(gè)點(diǎn)兩兩之間沒有邊．求m最大值．（如果圖Ｇ滿足二分圖條件）可以用二分圖匹配來做,也可用網(wǎng)絡(luò)流解決．

答案等于總點(diǎn)數(shù)-最大匹配數(shù)

證明：
設(shè)M為總點(diǎn)集，S為最大獨(dú)立集,B為最大匹配中的點(diǎn)集
|X|為點(diǎn)集X的點(diǎn)數(shù)

有|S|>=|M|-|B|/2 　|B|/2為最大匹配數(shù)
證明：
如果是完美匹配就不用說了|S|=|M|-|B|/2
首先有 |S|>=|M|-|B|,|M|-|B|即為除去最大匹配點(diǎn)集后剩下的點(diǎn)集中的點(diǎn)數(shù)
這些點(diǎn)集都是沒有邊相連的（有就說明不是最大匹配）
接下來我們考慮在B中的點(diǎn)可不可以也放入現(xiàn)在的S中
設(shè)a點(diǎn)為B中的某個(gè)點(diǎn)
若a點(diǎn)與M-B中的某個(gè)點(diǎn)相連
設(shè)b為M-B中的與a相連點(diǎn)
有a的匹配點(diǎn)與b不相連（否則就不是二分圖）
然后a的匹配點(diǎn)也不與M-B中的點(diǎn)相連（否則就不是最大匹配）
所以可以將a的匹配點(diǎn)放入S
若a點(diǎn)不與任何M-B中的點(diǎn)相連
則可以將a放入S中
也就是一個(gè)匹配至少可以放入一個(gè)點(diǎn)進(jìn)去，所以可以放入|B|/2個(gè)點(diǎn)進(jìn)去
所以有|S|>=|M|-|B|+|B|/2
即|S|>=|M|-|B|/2
又有|S|＜=|M|-|B|/2
證明：
在B中的點(diǎn)都是兩兩相連的，所以|B|/2個(gè)點(diǎn)不能在S中
即|S|＜=|M|-|B|/2
所以|S|=|M|-|B|/2

來看一個(gè)經(jīng)（jian）典（dan）的問題

有一些n個(gè)男生和m個(gè)女生，他們中有k對(duì)互相對(duì)對(duì)方有好感，每個(gè)人可能和多個(gè)人有好感度，每一對(duì)有好感度的人就可以湊成一對(duì)情侶，現(xiàn)在你要邀請(qǐng)他們中的一些人一起來玩耍，但是作為單身狗的你是不想見到情侶在一起的，你想知道你最多可以和多少人一起玩耍。
輸入格式
一行三個(gè)整數(shù)n，m，k
接下來k行每行2個(gè)整數(shù)a，b，表示a號(hào)男生與b號(hào)女生相互有好感
輸出格式
一行表示答案

首先男生和男生之間是不會(huì)有好感的，那么男生和女生就形成一個(gè)二分圖
我們自己畫一個(gè)圖，將男生和女生分為兩部，左部是男生，右部是女生

1號(hào)男生同時(shí)和2,4號(hào)女生有好感，2號(hào)男生只和4號(hào)女生有好感，3號(hào)男生和1,3號(hào)女生互相有好感， 4號(hào)男生只和3號(hào)女生互相有好感。
那么最多可以邀請(qǐng)4個(gè)人一起玩
（一）四個(gè)男生或者四個(gè)女生
（二）1,2號(hào)男生，1,3號(hào)女生
（三）3,4號(hào)男生，2,4號(hào)女生。

相信你也看出來了，題目的要求就是最多可以有多少個(gè)互相沒有邊的點(diǎn)，即最大獨(dú)立集
所以把這個(gè)二分圖的最大匹配求出來后用總點(diǎn)數(shù)減去即可

互相攻擊類型

這一類的題目大多數(shù)是給一個(gè)棋盤，上面的點(diǎn)有攻擊范圍，問最多可以放多少個(gè)棋子使其不會(huì)互相攻擊
如騎士共存問題,長脖子鹿放置,攻擊裝置.
這一類的題目通常的解法
先找相互之間絕對(duì)不會(huì)有聯(lián)系的點(diǎn)（如上面例題中的男生全部放在左邊）
需要的話考慮加邊順序會(huì)帶來的影響，如怎樣會(huì)使找增廣路次數(shù)最少，一般就是左部的選擇。
建邊，不能放置的點(diǎn)就不要連邊了。
注，盡管匈牙利算法打起來簡單一些，但是對(duì)于某些題目，網(wǎng)絡(luò)流速度會(huì)快一些
下面以長脖子鹿放置作為例題講一下。
我們發(fā)現(xiàn)，奇數(shù)行的點(diǎn)只打偶數(shù)行的點(diǎn)，偶數(shù)行的點(diǎn)只打奇數(shù)行的點(diǎn)，那么把奇數(shù)行的點(diǎn)看做左部，偶數(shù)行的點(diǎn)看做右部即可。
由于出題人卡了數(shù)據(jù)，所以匈牙利是過不去的。
代碼

/******************************* Author:Morning_Glory LANG:C++ Created Time:2019年03月23日 星期六 15時(shí)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;
}