网络流最小割专题

以下题目的时空限制均为 1s/128M

最小割的直接应用

网络战争

给出一个带权无向图 (G=<V,E>)，每条边 (e) 有一个权 (w_e)。

求将点 (s) 和点 (t) 分开的一个边割集 (C)，使得该割集的平均边权最小，即最小化：

[frac{sumlimits_{ein C}w_e}{|C|} ]

注意： 边割集的定义与最小割中的割边的集合不同。在本题中，一个边割集是指：将这些边删去之后，(s) 与 (t) 不再连通。

输入格式

第一行包含四个整数 (n,m,s,t)，其中 (n,m) 分别表示无向图的点数、边数。

接下来 (m) 行，每行包含三个整数 (a,b,w)，表示点 (a) 和 (b) 之间存在一条无向边，边权为 (w)。

点的编号从 (1) 到 (n)。

输出格式

输出一个实数，表示将点 (s) 和点 (t) 分开的边割集的最小平均边权。

结果保留两位小数。

数据范围

(2≤n≤100, 1≤m≤400, 1≤w≤107,)
保证 (s) 和 (t) 之间连通。

输入样例：

6 8 1 6
1 2 3
1 3 3
2 4 2
2 5 2
3 4 2
3 5 2
5 6 3
4 6 3

输出样例：

2.00

解析

注意这里的边割集与网络流里的边割集不是一个东西。

所有形如 (frac{sum{W}}{|C|}) 的表达式让我们求最值的时候，都可能与 01分数规划 有关系。

先愉快推式子：

[假设frac{sumlimits{w}}{|C|} > lambda\ Rightarrow sum{w} > lambda|C|\ Rightarrow sum{w} - lambda|C| > 0\ Rightarrow sum{(w-lambda)} > 0\ 小于时仍然成立。 ]

于是我们要求的是 (sum{(w_e-lambda)}) 的最小值

我们可以转化一下，将原图 (G) 里面的边权值每个减去 (lambda) ，得到新图 (G^{prime}) 边权值为 (w_e^{prime})。

会出现如下几个问题

  1. (w_e^{prime} le 0) ， 此时(w_e^{prime}) 必选。否则不是最优解。

  2. 题中图为无向边，流网络都是有向边。

    假设我们已经把 (le 0) 的所有边都选上了。

    根据题中的定义，我们可以想到，除了位于割的两个点集之间的边以外，我们还可以选择两个点集内点互相的连边。

    但是显然这些边是不会选到的，因为题中要求最小。

    方向的问题，我们其实可以不用管。虽然我们建的是两条有向边，但是它只会被算一次。具体可以看割容量的定义。

所以，我们只需要把所有 (w_e^{prime} le 0) 的边都选上，然后再在所有 (w_e^{prime} ge 0) 的边构成的新图中跑最大流即可

#include<bits/stdc++.h>
using namespace std;

const int N=1e3+10,M=1e4+10,INF=1e8;
const double eps=0.00000001;

int n,m,S,T;
int head[N],ver[M],nxt[M],w[M],tot=0;
double cc[M];
void add(int x,int y,int c)
{
	ver[tot]=y; w[tot]=c; nxt[tot]=head[x]; head[x]=tot++;
	ver[tot]=x; w[tot]=c; nxt[tot]=head[y]; head[y]=tot++;
}
int q[N],d[N],cur[N];

bool bfs()
{
	int hh=0,tt=0;
	memset(d,-1,sizeof d);
	q[0]=S,d[S]=0,cur[S]=head[S];
	while(hh<=tt)
	{
		int x=q[hh++];
		for(int i=head[x];~i;i=nxt[i])
		{
			int y=ver[i];
			if(d[y]==-1 && cc[i]>eps)
			{
				d[y]=d[x]+1;
				cur[y]=head[y];
				if(y==T) return 1;
				q[++tt]=y;
			}
		}
	}
	return 0;
}

double find(int u,double lim)
{
	if(u==T) return lim;
	double flow=0;
	for(int i=cur[u];~i && flow<lim;i=nxt[i])
	{
		int y=ver[i];
		cur[u]=i;
		if(d[y]==d[u]+1 && cc[i]>eps)
		{
			double tmp=find(y,min(cc[i],(double)lim-flow));
			if(tmp<eps) d[y]=-1;
			cc[i]-=tmp; cc[i^1]+=tmp; flow+=tmp;
		}
	}
	return flow;
}

double solve(double mid)
{
	double res=0;
	for(int i=0;i<tot;i+=2)
	{
		if(w[i]<=mid)
		{
			res+=w[i]-mid;
			cc[i]=cc[i^1]=0;
		}
		else cc[i]=cc[i^1]=(double)w[i]-mid;
	}
	double rr=0,flow;
	while(bfs())
	{
		while(flow=find(S,INF)) rr+=flow;
	}
	return rr+res;
}

int main()
{
	scanf("%d%d%d%d",&n,&m,&S,&T);
	memset(head,-1,sizeof head);
	for(int i=1;i<=m;i++)
	{
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		add(a,b,c);
	}

	double l=0,r=1e7;
	while(r-l>eps)
	{
		double mid=(l+r)/2;
		if(solve(mid)<0) r=mid-eps;//λ过大
		else l=mid;
	}
	printf("%.2lf",r);
}

最优标号

给定一个无向图 (G=(V,E))，每个顶点都有一个标号，它是一个 $[0,2^{31}−1] 内的整数。

不同的顶点可能会有相同的标号。

对每条边 ((u,v))，我们定义其费用 (cost(u,v)) 为 (u) 的标号与 (v) 的标号的异或值。

现在我们知道一些顶点的标号。

你需要确定余下顶点的标号使得所有边的费用和尽可能小。

输入格式

第一行有两个整数 (N,M) ，(N) 是图的点数，(M) 是图的边数。

接下来有 (M) 行，每行有两个整数 (u,v)，代表一条连接 (u,v) 的边。

接下来有一个整数 (K)，代表已知标号的顶点个数。

接下来的 (K) 行每行有两个整数 (u,p_u)，代表点 (u) 的标号是 (p_u)。

假定这些 (u) 不会重复。

所有点编号从 (1) 到 (N)。

输出格式

输出一行一个整数，即最小的费用和。

数据范围

(1≤N≤500,\ 0≤M≤3000,\ 1≤K≤N)

输入样例：

3 2
1 2
2 3
2
1 5
3 100

输出样例：

97

解析

所有的位运算都有一个特点，两个数异或时不同的二进制位之间是完全独立，互不干扰的。

也就是说我们若是求边的最小值，我们可以最小化所有边在每一个二进制位上总的的值，然后加起来。

于是我们来看对于第 (k) 位怎么做。

二进制只有 (0,1) 两种取值，这意味着我们可以把点分成两个集合，取值为 (1) 的 ((A)) 和取值为 (0) 的 ((B)) 。
这一位上总的最小值就取决于在两个集合之间有多少边。

我们注意到这个问题的形态很像最小割，于是我们可以将问题网最小割上转化。

无向图转有向图不多说。

虚拟一个源点 (s) 在集合 (A) 内，以及一个汇点 (t) 在集合 (B) 内。

对于一开始就有编号的点，若编号当前二进制位是 (0) 则一定在 (s) 所在集合内，我们可以从 (s) 向这个点连一条容量为 (+infty) 的边。反之，若编号当前二进制位是 (1) 则一定在 (t) 所在集合内，我们可以从这个点向 (t) 连一条容量为 (+infty) 的边。

这样做的话我们在求最小割时一定不会将这条边放进去。

其他剩余的点我们把已有的边容量设为 (1) 然后就不必再进行其他操作了。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=5100,M=3e5+10,INF=1e8+10;

int head[N],ver[M],nxt[M],cc[M],tot=0;
void add(int x,int y,int c,int d)
{
	ver[tot]=y; cc[tot]=c; nxt[tot]=head[x]; head[x]=tot++;
	ver[tot]=x; cc[tot]=d; nxt[tot]=head[y]; head[y]=tot++;
}
int q[N],d[N],cur[N];
struct ED{int a,b;} edge[M];
int poi[N];//标号
int n,m,k,S,T;

bool bfs()
{
	int hh=0,tt=0;
	memset(d,-1,sizeof d);
	q[0]=S,d[S]=0,cur[S]=head[S];
	while(hh<=tt)
	{
		int x=q[hh++];
		for(int i=head[x];~i;i=nxt[i])
		{
			int y=ver[i];
			if(d[y]==-1 && cc[i])
			{
				d[y]=d[x]+1;
				cur[y]=head[y];
				if(y==T) return 1;
				q[++tt]=y;
			}
		}
	}
	return 0;
}

int find(int u,int lim)
{
	if(u==T) return lim;
	int flow=0;
	for(int i=cur[u];~i&&flow<lim;i=nxt[i])
	{
		int y=ver[i];
		cur[u]=i;
		if(d[y]==d[u]+1 && cc[i])
		{
			int tmp=find(y,min(cc[i],lim-flow));
			if(!tmp) d[y]=-1;
			cc[i]-=tmp;cc[i^1]+=tmp; flow+=tmp;
		}
	}
	return flow;
}

ll dinic(int k)
{
	memset(head,-1,sizeof head);
	tot=0;
	for(int i=1;i<=m;i++)
		add(edge[i].a,edge[i].b,1,1);
	for(int i=1;i<=n;i++)
	{
		if(poi[i]<0) continue;
		if((poi[i]>>k)&1) add(i,T,INF,0);
		else add(S,i,INF,0);
	}

	int res=0,flow;
	while(bfs()) while(flow=find(S,INF)) res+=flow;
	return res;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin>>n>>m;
	S=0,T=N-2;
	for(int i=1;i<=m;i++)
		cin>>edge[i].a>>edge[i].b;
	memset(poi,-1,sizeof poi);
	cin>>k;
	for(int i=1;i<=k;i++)
	{
		int u,x;
		cin>>u>>x;
		poi[u]=x;
	}
	ll res=0;
	for(int i=0;i<31;i++) res+=dinic(i)<<i;
	cout<<res;
}

最大权闭合图

闭合图：对于一个带点权有向图 (G<V,E>) ，我们选出一个点集 (V^{prime}) 使得对于任意 (uin V^{prime} , exists(u,v)in E) 使得 (v otin V^{prime}) 。这个点集以及点集内点互相之间的连边组成集合就是 (G) 的一个闭合子图，(V^{prime}) 是闭合点集。

最大权闭合子图指的是最大点权和闭合子图。很显然的是，当一个图中的所有点权都是正数时，最大权闭合子图是它本身。

那么给你一张带点权有向图图 (G<V,E>) 如何求其最大点权闭合图？

我们首先把它改造成一张流网络 (N<V_N,E_N>) 。

首先建立源点汇点。

源点向所有的正权点连一条边，所有的负权点向汇点连一条边，容量为点权的绝对值。原图内的边仍然存在，容量为 (+infty)。

构造完毕。

下面证明对应性。

我们定义一种特殊的割：

定义简单割 (<A,B>,(A,Bin V)) 满足对于 (forall (u,v)in{(u,v)|uin A and vin B}) 都有 (u=s or v=t) ，即所有割边都与源点或汇点相连的割。

在这个题中，易得最大流一定是一个有限值，故由最大流最小割定理，最小割也是一个有限值。所以这里最小割一定是一个简单割。

试证明原图任意一个闭合子图 (G_c<V^{prime},E^{prime}>) 都能对应新网络 (N<V_N,E_N>) 中的一个简单割。

  • 先构造一个割 (<S,T>) ，(S=V^{prime}+{s} , T=V_N-S) 。

    我们可以知道，(V^{prime}) 是一个闭合点集，除与源汇点相连的边外其他的边都在 (V^{prime}) 的内部连接。所以割 (<S,T>) 一定是一个简单割。

接着证明新网络的任何一个简单割 (<S,T>) 对应原网络的一个闭合子图

  • 构造点集 (V^{prime}=S-{s})

    由于 (<S,T>) 是一个简单割，所以 (S,T) 之间没有原图的边。也就是说从 (V^{prime}) 中的任何一个点出发，都无法通过原图就有的边走到一个点 (v otin V^{prime}) 。所以 (V^{prime}) 是一个闭合点集，由于闭合点集与闭合子图一一对应。故新网络任意一个简单割对应原图的一个闭合子图。

综上，原图的闭合子图与新网络的简单割一一对应。

现在我们来考察一下本题条件下简单割的容量计算方法。

对于一个简单割 (<S,T>,(S=V_1+{s},T=V_2+{t}))

[{ egin{aligned} C(S,T) &=C(V_1,{t})+C({s},V_2) \ &=sumlimits_{vin V_2}w_v + sumlimits_{vin V_1}(-w_v) \ end{aligned} } ]

令 (V_1) 的权值和 (w(V_1))，用 (V_1^{+}) 表示 (V_1) 中的正权点,(V_1^{-}) 表示负权点

[{ egin{aligned} w(V_1) &=sumlimits_{vin V_1^+}w_v-sumlimits_{vin V_1^-}(-w_v) \ end{aligned}\ egin{aligned} w(V_1)+C(S,T) &=sumlimits_{vin V_1^+}w_v-sumlimits_{vin V_1^-}(-w_v)+sumlimits_{vin V_2}w_v + sumlimits_{vin V_1}(-w_v) \ &=sumlimits_{vin V^+}w_v \ end{aligned}\ 即：w(V_1)+C(S,T)=w(V^+) } ]

也就是说我们若是想要最大化 (w(V_1)) 我们最小化 (C(S,T)) 就可以了。

具体的说，最大权闭合子图的点权和 (=) 原图正点权和 (-) 新网络最小割容量。

[NOI2006]最大获利

(link)

题目背景

新的技术正冲击着手机通讯市场，对于各大运营商来说，这既是机遇，更是挑战。

THU 集团旗下的 CS&T 通讯公司在新一代通讯技术血战的前夜，需要做太多的准备工作，仅就站址选择一项，就需要完成前期市场研究、站址勘测、最优化等项目。

在前期市场调查和站址勘测之后，公司得到了一共 (N) 个可以作为通讯信号中转站的地址，而由于这些地址的地理位置差异，在不同的地方建造通讯中转站需 要投入的成本也是不一样的，所幸在前期调查之后这些都是已知数据：

建立第 (i) 个通讯中转站需要的成本为 (P_i)（(1≤i≤N)） 。

另外公司调查得出了所有期望中的用户群，一共 (M) 个。

关于第 (i) 个用户群的信息概括为 (A_i,B_i) 和 (C_i)：这些用户会使用中转站 (A_i) 和中转站 (B_i) 进行通讯，公司可以获益 (C_i)。（(1≤i≤M,1≤Ai,Bi≤N)）
THU 集团的 CS&T 公司可以有选择的建立一些中转站（投入成本），为一些用户提供服务并获得收益（获益之和）。

那么如何选择最终建立的中转站才能让公司的净获利最大呢？（净获利 (=) 获益之和 (–) 投入成本之和）

输入格式

第一行有两个正整数 (N) 和 (M) 。

第二行中有 (N) 个整数描述每一个通讯中转站的建立成本，依次为 (P_1,P_2,…,P_N) 。

以下 (M) 行，第((i + 2))行的三个数 (A_i,B_i) 和 (C_i) 描述第 (i) 个用户群的信息。

所有变量的含义可以参见题目描述。

输出格式

输出一个整数，表示公司可以得到的最大净获利。

数据范围

(N≤5000,\ M≤50000,\ 0≤Ci,Pi≤100)

输入样例：

5 5
1 2 3 4 5
1 2 3
2 3 4
1 3 3
1 4 2
4 5 3

输出样例：

4

样例解释

选择建立 (1、2、3) 号中转站，则需要投入成本 (6)，获利为 (10)，因此得到最大收益 (4)。

解析(最大权闭合图做法)

我们把中转站和用户群看做两种点，中转站点权为负，用户群点权为正。

若一个用户群需要数个中转站那么我们从用户群向这些中转站连边。

于是我们发现，这是一个最大权闭合图问题。我们若是要选择一个用户群，那么我们就要满足他们的需求，相连接的中转站也会被连接进来。换句话说，我们选择的点构成的子图要没有出边，也就是闭合子图。同时我们要是逆向思考，每一个闭合子图都对应数个人群被完全满足不留遗憾，是一个满足条件的解。故原问题的任意一组解可以对应我们建立的有向图中的一个闭合子图。

而我们要获得最大收益，就是要求最大权闭合图的点权和。

#include <bits/stdc++.h>
using namespace std;

const int N=2e5+10,M=5e5+10,INF=1e8;
int head[N],ver[M],nxt[M],cc[M],tot=0;
void add(int x,int y,int c)
{
	ver[tot]=y; cc[tot]=c; nxt[tot]=head[x]; head[x]=tot++;
	ver[tot]=x; cc[tot]=0; nxt[tot]=head[y]; head[y]=tot++;
}
int q[N],d[N],cur[N];
int n,m,S,T;

bool bfs()
{
	int hh=0,tt=0;
	memset(d,-1,sizeof d);
	q[0]=S; d[S]=0; cur[S]=head[S];
	while(hh<=tt)
	{
		int x=q[hh++];
		for(int i=head[x];~i;i=nxt[i])
		{
			int y=ver[i];
			if(d[y]==-1 && cc[i])
			{
				d[y]=d[x]+1;
				cur[y]=head[y];
				if(y==T) return 1;
				q[++tt]=y;
			}
		}
	}
	return 0;
}

int find(int u,int lim)
{
	if(u==T) return lim;
	int flow=0;
	for(int i=cur[u];~i && flow<lim;i=nxt[i])
	{
		int y=ver[i];
		cur[u]=i;
		if(d[y]==d[u]+1 && cc[i])
		{
			int tmp=find(y,min(cc[i],lim-flow));
			if(!tmp) d[y]=-1;
			cc[i]-=tmp; cc[i^1]+=tmp; flow+=tmp;
		}
	}
	return flow;
}

int dinic()
{
	int res=0,flow;
	while(bfs()) while(flow=find(S,INF)) res+=flow;
	return res;
}

int main()
{
	memset(head,-1,sizeof head);
	scanf("%d%d",&n,&m);
	S=0,T=n+m+10;
	for(int i=1;i<=n;i++)
	{
		int p;
		scanf("%d",&p);
		add(m+i,T,p);
	}
	int sum=0;
	for(int i=1;i<=m;i++)
	{
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		add(i,m+a,INF);
		add(i,m+b,INF);
		add(S,i,c);
		sum+=c;
	}
	printf("%d",sum-dinic());
	return 0;
}

最大密度子图

给出一张图 (G<V,E>) 我们选出一个子图 (G^{prime}<V^{prime},E^{prime}>) 使得其 (frac{|E^{prime}|}{|V^{prime}|}) 最大，这个图就是最大密度子图。

借01分数规划的逻辑，我们试着二分 (frac{|E^{prime}|}{|V^{prime}|})

假设 (frac{|E^{prime}|}{|V^{prime}|}le g)

整理得 (|E^{prime}|-g|V^{prime}|le 0)

我们设一个函数 (h(g)=max{|E^{prime}|-g|V^{prime}|})

我们简记 (|V^{prime}|=n,|E^{prime}|=m)

可以得到

[egin{cases} h(g)=0 Leftrightarrow g=最优解\ h(g)<0 Leftrightarrow g>最优解\ h(g)>0 Leftrightarrow g<最优解\ end{cases} ]

于是我们需要对 (g) 二分查找，并对每一个得到的猜测值求解 (h(g))。

密度不超过 (m) 且 不小于 (frac{1}{n}) ，于是使他们作为二分的上下界。

然后是确定二分精度。

这里有一个推论：任意两个密度不同的子图 (G_1,G_2) 其密度差绝对值不小于 (frac{1}{n^2})

[egin{matrix} 证明：& 不妨设 G_1 的密度大于 G_2 的密度，则：\ & frac{m_1}{n_1}-frac{m_2}{n_2}=frac{m_1n_2-m_2n_1}{n_1n_2}ge frac{1}{n_1n_2}ge frac{1}{n^2}\ end{matrix} ]

现在问题在于，已知 (g) 如何求解 (h(g))。

回顾题意，我们可以知道在选出的新图 (G^{prime}) 中，边 ((u,v)in E^{prime}) 的必要条件是 (u,vin V^{prime}) ，这与上文最大权闭合图的限制条件形式差不多。

那么我们把本问题中的边看做点，点权为 (1) ，本问题中的点带上点权 (-g) ，问题就转化为了最大权闭合图的模型。

我们发现在跑最大流时建边很多，并且上述问题在转化过程中将问题一般化了，复杂度会提高，所以我们思考能否利用这个图以及问题的特殊性质做这个问题。

回顾题意，我们可以发现，当我们的点集确定时，点集的诱导子图一定是最优解。

诱导子图：从原图 (G<V,E>) 中选出来一个子图 (G^{prime}<V^{prime},E^{prime}>) ,对于所有的 (u,vin V^{prime}) 都有 ((u,v)in E^{prime}) 。即把点集内部点之间的连边全部都选上。

假设我们选出了一个点集 (V^{prime}) 现在我们要弄出它的诱导子图 (G^{prime}<V^{prime},E^{prime}>)，正向的思维便是把点集内的边一个一个找出来。

但我们使用逆向思维思考：根据补集思想，可以将所有与 (V^{prime}) 中的点关联，同时又不在 (E^{prime}) 中的点选出(下图中的红边)，然后用与 (V^{prime}) 关联的所有边的集合减去，就是我们要求的边集了。

画图继续探索：

于是我们发现，所有我们要选出的边是连接 (V^{prime}) 和 (V-V^{prime}) 的所有边。这与割的定义形式相近。我们可以考虑转化利用最小割来做。

首先我们在上面得出了要最大化 (|E^{prime}|-g|V^{prime}|) 的结论。只需要乘上 (-1) 就可以转化为最小化。

也就是我们要最小化 (g|V^{prime}|-|E^{prime}|)

根据上面的推论推一下式子：
其中 (d_v) 代表 (v) 点的度。

[egin{aligned} Minimizequad g|V^{prime}|-|E^{prime}| &=sum_{vin V^{prime}}g-sum_{ein E^{prime}}1\ &=sum_{vin V^{prime}}g-(frac{sum_{vin V^{prime}}d_v-C(V^{prime},V-V^{prime})}{2})\ &=sum_{vin V^{prime}}(g-frac{d_v}{2})+frac{C(V^{prime},V-V^{prime})}{2}\ &我们希望割的系数能够到整个式子的前面去，所以我们暴力提一个 frac{1}{2}\ 原式&=frac{1}{2}cdot [sum_{vin V^{prime}}(2g-d_v)+C(V^{prime},V-V^{prime})] end{aligned} ]

这个式子相当于在提示我们每个点多了个 (2g-d_v) 的点权。

我们怎么把它结合到最小割里呢？

只需要每个点向汇点连一条边，容量是 (2g-d_v)。

原图内部的所有边不做改变，容量为 (1)。

由于最小割只能接受容量非负的边权，所以我们给上面的边容量加上一个大数 (U) 保证非负。

建立源点，源点向每个点都连一条容量为 (U) 的边

解法正确性待会证明。

现在思考怎么算答案。

这时我们来看求出的最小割 (C(S,T))

定义 (V^{prime}=S-{s} \ overline{V^{prime}}=V-V^{prime})

那么

[egin{aligned} C(S,T) &=sum_{vin overline{V^{prime}}}U + sum_{uin V^{prime}}(U+2g-d_u)+sum_{uin {V^{prime}}}sum_{vin overline{V^{prime}}} C_{u,v}\ &=sum_{vin overline{V^{prime}}}U + sum_{uin V^{prime}}[(U+2g-d_u)+sum_{vin overline{V^{prime}}} C_{u,v}]\ &=sum_{vin overline{V^{prime}}}U + sum_{uin V^{prime}}[U+2g-(d_u-sum_{vin overline{V^{prime}}} C_{u,v})] end{aligned} ]

接下来我们关注一下括号里面 ((d_u-sumlimits_{vin overline{V^{prime}}} C_{u,v})) 的含义

这个式子描述的是，从 (u) 出发的所有边减去到所有到集合外部的边，也就是在集合内部的边。

所以 ((d_u-sumlimits_{vin overline{V^{prime}}} C_{u,v})=sumlimits_{vin V^{prime}} C_{u,v})

所以：

[egin{aligned} 原式 &=sum_{vin overline{V^{prime}}}U+ sum_{uin V^{prime}}[U+2g-sum_{vin V^{prime}} C_{u,v}]\ &=sum_{vin V}U+ sum_{uin V^{prime}}2g-sum_{uin V^{prime}}sum_{vin V^{prime}} C_{u,v}\ &=Ucdot n + 2g|V^{prime}|-2|E^{prime}| end{aligned} ]

于是我们发现，割和密度子图是由一一对应且单调的关系的。

我们可以整理一下答案：(g|V^{prime}|-|E^{prime}|=frac{Ucdot n-C(S,T)}{2})。

Hard Life

约翰是一家公司的 CEO。

公司的股东决定让他的儿子斯科特成为公司的经理。

约翰十分担心，儿子会因为在经理岗位上表现优异而威胁到他 CEO 的位置。

因此，他决定精心挑选儿子要管理的团队人员，让儿子知道社会的险恶。

已知公司中一共有 (n) 名员工，员工之间共有 (m) 对两两矛盾关系。

如果将一对有矛盾的员工安排在同一个团队，那么团队的管理难度就会增大。

一个团队的管理难度系数等于团队中的矛盾关系对数除以团队总人数。

团队的管理难度系数越大，团队就越难管理。

约翰希望给儿子安排的团队的管理难度系数尽可能大。

请帮帮他。

以上图为例，管理难度系数最大的团队由 (1,2,4,5) 号员工组成，他们 (4) 人中共有 (5) 对矛盾关系，所以管理难度系数为 (54)。

如果我们将 (3) 号员工也加入到团队之中，那么管理难度系数就会降至 (65)。

输入格式

第一行包含两个整数 (n) 和 (m)。

接下来 (m) 行，每行包含两个整数 (a_i) 和 (b_i)，表示员工 (a_i) 和 (b_i) 之间存在矛盾。

所有员工编号从 (1) 到 (n)。

每个矛盾对最多在输入中出现一次，且介绍矛盾对时，员工介绍顺序是随意的。

输出格式

首先输出一个整数 (k)，表示安排给斯科特的团队人员数量。

接下来 (k) 行，以升序输出团队每个成员的编号，每行一个。

如果答案不唯一，则输出任意一种即可。

注意：至少要选择一名员工。

数据范围

(1≤n≤100, 0≤m≤1000, 1≤k≤n)

输入样例1：

5 6
1 5
5 4
4 2
2 5
1 2
3 1

输出样例1：

4
1
2
4
5

输入样例2：

4 0

输出样例2：

1
1

提示

注意样例 (2) 中，任意团队的管理困难系数都是 (0)，这种情况输出任意非空方案即可。

解析

这个题就是让我们求最大密度子图。但是我们还需要输出方案。

我们可以使用在证明最大流最小割定理时用到的一个方法：我们从源点出发，沿着容量大于 (0) 的边走，所有能走到的边就是 (S) 集合，将 (S) 集合中的源点删去，就得到了 (V^{prime})。

code

#include <bits/stdc++.h>
using namespace std;

const int N=1e5+10,M=1e6+10,INF=1e8+10,U=1200;

int head[N],ver[M],nxt[M],tot=0;
double cc[N];
void add(int x,int y,double c,double d)
{
	ver[tot]=y; cc[tot]=c; nxt[tot]=head[x]; head[x]=tot++;
	ver[tot]=x; cc[tot]=d; nxt[tot]=head[y]; head[y]=tot++;
}
int q[N],d[N],cur[N];
int n,m,S,T;
int dg[N];//每个点的度数
struct node
{
	int u,v;
} edge[M];//把所有的关系预先存好，方便每次二分重新建图

void build(double g)
{
	memset(head,-1,sizeof head);
	tot=0;
	for(int i=1;i<=m;i++) add(edge[i].u,edge[i].v,1,1);
	for(int i=1;i<=n;i++)
	{
		add(i,T,U+2*g-dg[i],0);
		add(S,i,U,0);
	}
}

bool bfs()
{
	int hh=0,tt=0;
	memset(d,-1,sizeof d);
	q[0]=S; d[S]=0; cur[S]=head[S];
	while(hh<=tt)
	{
//		cout<<hh<<" "<<tt<<"
";
		int x=q[hh++];
		for(int i=head[x];~i;i=nxt[i])
		{
			int y=ver[i];
			if(d[y]==-1 && cc[i]>0)
			{
				d[y]=d[x]+1;
				cur[y]=head[y];
				if(y==T) return 1;
				q[++tt]=y;
			}
		}
	}
	return 0;
}

double find(int u,double lim)
{
	if(u==T) return lim;
	double flow=0;
	for(int i=cur[u];~i && flow<lim;i=nxt[i])
	{
		int y=ver[i];
		cur[u]=i;
		if(d[y]==d[u]+1 && cc[i]>0)
		{
			double tmp=find(y,min(cc[i],lim-flow));
			if(tmp<=0) d[y]=-1;
			cc[i]-=tmp; cc[i^1]+=tmp; flow+=tmp;
		}
	}
	return flow;
}

double dinic(double g)
{
	build(g);
	double res=0,flow=0;
	while(bfs()) while(flow=find(S,(double)INF)) res+=flow;
	return res;
}

bool vis[N];
int ans=0;
void dfs(int x)
{
	vis[x]=1;
	if(x!=S) ans++;
	for(int i=head[x];~i;i=nxt[i])
	{
		int y=ver[i];
		if(!vis[y] && cc[i]>0) dfs(y);
	}
	return ;
}

int main()
{
	scanf("%d%d",&n,&m);
	S=0,T=n+1;
	for(int i=1;i<=m;i++)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		++dg[a]; ++dg[b];
		edge[i]={a,b};
	}

	double l=1/n,r=m,eps=1.0/(double)(n*n);
	while(r-l>eps)
	{
		double mid=(l+r)/2;
		double tmp=dinic(mid);
		if(U*n-tmp>0) l=mid;
		else r=mid;
	}

	dinic(l);
	dfs(S);
	if(ans==0)
	{
		printf("1
1");
		return 0;
	}
	printf("%d
",ans);
	for(int i=1;i<=n;i++)
		if(vis[i]) printf("%d
",i);
	return 0;
}

带边权的最大密度子图

首先我们重新定义一下问题：给出一个带边权无向图 (G<V,E>) 其中每条边都有一个边权 (w_ege 0) 。定义带边权无向图的密度 (D=frac{sumlimits_{ein E}w_e}{|V|}) 。求最大密度子图。

主要的思想是改造上面的做法。

我们现在的新目标就是选出一个子图 (G^{prime}<V^{prime},E^{prime}>) 且最大化 (h(g)=max{sumlimits_{ein E^{prime}}w_e-g|V^{prime}|})

对比上面的式子，只有边权项不同。

我们重定义一个点 (u) 的“度” (d_u=sumlimits_{(u,v)in E}w_e)。再在建立流网络的时候将边权为 (1) 改为边权为 (w_e)。

于是我们发现，朴素最大密度子图有关的引理推论都成立。

即仍然有 (h(g)=frac{Ucdot n-C(S,T)}{2}) 成立，(C(S,T)) 是最小割。

然而此时由于度的重定义，关于二分精度的推论不再适用，所以要人为规定精度，我自己习惯 (10^{-8})。

暂时没有找到例题。

带点权边权的最大密度子图

仍然先重定义一下问题。

给出一个带点权边权的无向图 (G<V,E>) 每个点 (vin V) 有一个点权 (p_ige 0)，每条边 (ein E) 有一个边权 (w_ege 0) 。定义密度 (D=frac{sumlimits_{vin V}p_v+sumlimits_{ein E}w_e}{|V|})。求解最大密度子图。

主体思路仍然是改造上面的方法。

我们转化一下分数规划的式子，得到我们新的 (h(g)) 函数。

[h(g)=max{sum_{ein E^{prime}}w_e+sum_{vin V^{prime}}p_v-sum_{vin V^{prime}}g}=max{sum_{ein E^{prime}}w_e-sum_{vin V^{prime}}(g-p_v)} ]

观察式子后，我们重定义节点 (u) 的“度” (d_u) 为 (d_u=sumlimits_{(u,v)in E}w_e) 然后替换网络中对应容量为 (1) 的边的容量为 (w_e) 。与带边权最密子图比较，我们的点权改变了，不再是单纯的 (g)，而是 (g-p_u) 所以我们在流网络向汇点连边时边容量应为 (U+2(g-p_u)-d_u)

我们把重定义的量拿来计算，由于各个量均非负，仍然能够得到

[h(g)=frac{Ucdot n-C(S,T)}{2} ]

当然，二分需要人为规定精度。

最大获利

题目同上

解析

我们将用户群看做边，中转站看做点。题目要求我们拿出一些边使其“满足”，得到收益 (sum w_e) ，建立中转站花去费用 (sum p_v)

我们设所有选出来的中转站 (v) 组成的集合为 (V^{prime}) ，所有选出的用户群集合为 (E^{prime}) 得到一张新图 (G^{prime}<V^{prime},E^{prime}>)，题目要求我们最大化

[sum_{ein E} w_e-sum_{vin V}p_v ]

由题意我们可以知道，(forall (u,v)in E) 都有 (u,vin V) 这不仅满足最大权闭合图模型的形式，还符合最大密度子图的限制条件。于是我们可以试图转化问题到带点权边权最大密度子图上。

我们看一下上面优化的对象：

[h(g)=max{sum_{ein E^{prime}}w_e+sum_{vin V^{prime}}p_v-sum_{vin V^{prime}}g}=max{sum_{ein E^{prime}}w_e-sum_{vin V^{prime}}(g-p_v)} ]

我们若是令上式中的 ((g-p_v)) 为本题中的 (p_v) ，那么两个式子就一模一样，字母都不带改的那种。

也就是说，我们只要令 (g=0) ,然后赋点权时赋负值就可以了。

#include <bits/stdc++.h>
using namespace std;

const int N=5e4+10, M=5e5+10, INF=1e8;

int head[N],ver[M],nxt[M],cc[M],tot=0;
void add(int x,int y,int c1,int c2)
{
	ver[tot]=y; cc[tot]=c1; nxt[tot]=head[x]; head[x]=tot++;
	ver[tot]=x; cc[tot]=c2; nxt[tot]=head[y]; head[y]=tot++;
}
int q[N],d[N],cur[N];
int poi[N],dg[N];
int n,m,S,T;

bool bfs()
{
	int hh=0,tt=0;
	memset(d,-1,sizeof d);
	q[0]=S, d[S]=0, cur[S]=head[S];
	while(hh<=tt)
	{
		int x=q[hh++];
		for(int i=head[x];~i;i=nxt[i])
		{
			int y=ver[i];
			if(d[y]==-1 && cc[i])
			{
				d[y]=d[x]+1;
				cur[y]=head[y];
				if(y==T) return 1;
				q[++tt]=y;
			}
		}
	}
	return 0;
}

int find(int u,int lim)
{
	if(u==T) return lim;
	int flow=0;
	for(int i=cur[u];~i && flow<lim;i=nxt[i])
	{
		int y=ver[i];
		cur[u]=i;
		if(d[y]==d[u]+1 && cc[i])
		{
			int tmp=find(y,min(cc[i],lim-flow));
			if(!tmp) d[y]=-1;
			cc[i]-=tmp; cc[i^1]+=tmp; flow+=tmp;
		}
	}
	return flow;
}

int dinic()
{
	int res=0,flow;
	while(bfs()) while(flow=find(S,INF)) res+=flow;
	return res;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin>>n>>m;
	memset(head,-1,sizeof head);
	S=0,T=n+1;
	for(int i=1;i<=n;i++)
	{
		cin>>poi[i];
		poi[i]*=-1;
	}
	memset(dg,0,sizeof dg);
	for(int i=1;i<=m;i++)
	{
		int x,y,z;
		cin>>x>>y>>z;
		add(x,y,z,z);
		dg[x]+=z; dg[y]+=z;//注意度数的重定义
	}
	int U=0;
	for(int i=1;i<=n;i++) U=max(U,2*poi[i]+dg[i]);//极大值U要保证≥pv+dv
	for(int i=1;i<=n;i++)
	{
		add(S,i,U,0);
		add(i,T,U-2*poi[i]-dg[i],0);
	}
	cout<<(U*n-dinic())/2;
	return 0;
}

最小权点覆盖

点覆盖集(点覆盖)：给我们一个无向图 (G<V,E>) ，我们需要选出一些点组成 (V^{prime}) 使得每一条边 ((u,v)in E) 有 (uin V^{prime}) 或 (vin V^{prime})。(V^{prime}) 就是一个点覆盖集。

最小权点覆盖中，我们要求每个点有一个非负权值 (p)，选出点权和。

在一般图中，这个问题被证明无法在多项式时间内解出。所以我们关注二分图下的最小权点覆盖。

借鉴二分图匹配最大流解法，我们可以试着如下建图：

首先建立源汇点 (s,t)，(s) 向左部的每个点连一条边。右部的每个点向 (t) 连一条边。我们若是把二分图中的边看做有向的，那么任意一条 (s-t) 路径一定有 (s-u-v-t) 的形式。若我们人为地使 ((u,v)) 边不会到最小割里面去，那么 ((s,u),(v,t)) 至少有一条边是在最小割中。

这样的条件刚好和最小权点覆盖的条件一样。若我们令 (c(s,u)=p_u，c(v,t)=p_v) ，那么此时最小割的优化目标也与最小权点覆盖相同。

综上我们可以如下建图：

建立源汇点 (s,t) (s) 向每一个左部点 (uin A) 连一条容量为 (p_u) 的边，每一个右部点 (vin B) 向 (t) 连一条容量为 (p_v) 的边。二分图原有的边 ((u,v)) 改为容量为 (+infty) 的单向边 ((u,v)) 。

再形式化一点，对于原二分图 (G<V,E>)，建立流网络 (N<V_N,E_N>):

[{ V_N=Vcup {s,t}\ E_N=Ecup {(s,u)|uin A}cup {(v,t)|vin B}\ egin{cases} c(u,v)=+infty & (u,v)in E\ c(s,u)=p_u & uin A\ c(v,t)=p_v & vin B end{cases} } ]

若规定：极小点覆盖是指任意删去一个点都不能成为点覆盖的点覆盖。极小点覆盖下每条边有且仅有一个端点被选入点覆盖。

我们可以知道，最小权点覆盖一定是极小点覆盖。

这里沿用上面简单割的概念。由于上面已经证明最小割一定是简单割，我们只需要证明极小点覆盖与简单割 (<S,T>) 对应。

  1. 简单割 (Rightarrow) 点覆盖

    由于这个割是简单割，我们就把每条割边的非源汇端点加入一个集合 (Q) 。假设此时存在一条边 ((u,v)) 其两个端点都不在 (Q) 中，则会出现 (s,t) 同时在 (T) 中，不符题意。反之假设此时存在一条边 ((u,v)) 其两个端点都在 (Q) 中，则会出现 (s,t) 同时在 (S) 中，不符题意。所以每条边有且只有一个端点在 (Q) 中。(Q) 即为简单割对应的极小点覆盖选出的点集。

  2. 点覆盖 (Rightarrow) 简单割

    极小点覆盖选出的的点集 (V^{prime})，我们可以在图中将这些点对应的与源汇点的连边标记，组成边集 (E^{prime}) 。从源点出发搜索我们发现，由于原图每一条边都有一个端点被选入 (V^{prime}) ，所以每一条 (s-t) 的路径都经过一条边 (ein E^{prime})。换句话说，若是将边集 (E^{prime}) 中的所有边作为割边的话就能构成一个合法的 (<S,T>) 割，并且是一个简单割。割的容量就是 (E^{prime}) 容量和。

综上，由于上文给出的一一对应关系，并且由于最小割和最小权点覆盖的优化方向一致，所以可以用最小割解决。

有向图破坏

爱丽丝和鲍勃正在玩以下游戏。

首先，爱丽丝绘制一个 (N) 个点 (M) 条边的有向图。

然后，鲍勃试图毁掉它。

在每一步操作中，鲍勃都可以选取一个点，并将所有射入该点的边移除或者将所有从该点射出的边移除。

已知，对于第 (i) 个点，将所有射入该点的边移除所需的花费为 (W^+_i)，将所有从该点射出的边移除所需的花费为 (W^−_i)。

鲍勃需要将图中的所有边移除，并且还要使花费尽可能少。

请帮助鲍勃计算最少花费。

输入格式

第一行包含 (N) 和 (M)。

第二行包含 (N) 个正整数，第 (i) 个为 (W^+_i)。

第三行包含 (N) 个正整数，第 (i) 个为 (W^−_i)。

接下来 (M) 行，每行包含两个整数 (a,b)，表示从点 (a) 到点 (b) 存在一条有向边。

所有点编号从 (1) 到 (N)。

图中可能由重边或自环。

输出格式

第一行输出整数 (W)，表示鲍勃所需的最少花费。

第二行输出整数 (K)，表示鲍勃需要进行的操作步数。

接下来 (K) 行，每行输出一个鲍勃的具体操作。

如果操作为将所有射入点 (i) 的边移除，则输出格式为 i +。

如果操作为将所有从点 (i) 射出的边移除，则输出格式为 i -。

如果答案不唯一，则输出任意一种即可。

数据范围

(1≤N≤100, 1≤M≤5000, 1≤W^+_i,W^−_i≤10^6)

输入样例：

3 6
1 2 3
4 2 1
1 2
1 1
3 2
1 2
3 1
2 3

输出样例：

5
3
1 +
2 -
2 +

解析

我们发现这是有向图，模型给的是无向图，不能直接套模型。

那我们稍微分析一下：

对于一个边 ((u,v)) ，我们要删掉它只能由 (W^-_u) 或 (W^+_v)的方式删掉它，并且两个方式至少选择一个 (废话)。这里很像我们最小权点覆盖中的逻辑。那我们继续分析。

每个点都有两种身份：(W^+) 和 (W^-) ，我们可以联想到拆点，而且我们发现拆完点后图也变成二分图了。

设原图 (G<V,E>)

把每个点拆成两个，左部是 (W^+) 的点，对于点 (u) 记为 (u^+)；右部是 (W^-) 的点，对于点 (u) 记为 (u^-)。若存在 ((u,v)in E) 就从 (v^+) 向 (u^-) 连一条边，边权设为 (+infty)，源点向所有左部点 (u) 连边，边权设为 (W^+_u) ，所有右部点 (v) 向汇点连边，边权为 (W^-_v)。原问题的限制是我们至少选择一种方式删边，对应到这个二分图中就是两个点至少选一个，这个问题就变成了最小权点覆盖问题。

同时其优化方向也与最小权点覆盖问题相同。

但是这个题还要我们求点覆盖集方案。

在证明最大流最小割时我们如何构造的割？

从 (s) 出发在残留网络中沿着剩余容量 (>0) 的边走，所有遍历到的点构成集合 (S) 。当时我们也证明了这是一个最小割。

现在要干的是转换最小割到点覆盖。我们找出所有割边即可，注意这里的割边只能在原网络里找。

#include <bits/stdc++.h>
using namespace std;

const int N=1e4+10,M=2e5+10,INF=5e8+10;

int n,m,S,T;
int head[N],ver[M],nxt[M],cc[M],tot=0;
void add(int x,int y,int c)
{
	ver[tot]=y; cc[tot]=c; nxt[tot]=head[x]; head[x]=tot++;
	ver[tot]=x; cc[tot]=0; nxt[tot]=head[y]; head[y]=tot++;
}
int q[N],d[N],cur[N];
int poi[N],poin[N],dg[N];
bool vis[N];

bool bfs()
{
	int hh=0,tt=0;
	memset(d,-1,sizeof d);
	q[0]=S,d[S]=0; cur[S]=head[S];
	while(hh<=tt)
	{
		int x=q[hh++];
		for(int i=head[x];~i;i=nxt[i])
		{
			int y=ver[i];
			if(d[y]==-1 && cc[i])
			{
				d[y]=d[x]+1;
				cur[y]=head[y];
				if(y==T) return 1;
				q[++tt]=y;
			}
		}
	}
	return 0;
}

int find(int u,int lim)
{
	if(u==T) return lim;
	int flow=0;
	for(int i=cur[u];~i && flow<lim;i=nxt[i])
	{
		cur[u]=i;
		int y=ver[i];
		if(d[y]==d[u]+1 && cc[i])
		{
			int tmp=find(y,min(cc[i],lim-flow));
			if(!tmp) d[y]=-1;
			cc[i]-=tmp; cc[i^1]+=tmp; flow+=tmp;
		}
	}
	return flow;
}

int dinic()
{
	int res=0,flow;
	while(bfs()) while(flow=find(S,INF)) res+=flow;
	return res;
}

void dfs(int x)
{
	vis[x]=1;
	for(int i=head[x];~i;i=nxt[i])
	{
		int y=ver[i];
		if(cc[i] && (!vis[y])) dfs(y);
	}
	return ;
}

int main()
{
	scanf("%d%d",&n,&m);
	memset(head,-1,sizeof head);
	S=0,T=N-10;
	for(int i=1;i<=n*2;i++)
		scanf("%d",poi+i);
	for(int i=1;i<=m;i++)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		add(b,n+a,INF);
	}
	for(int i=1;i<=n;i++)
	{
		add(S,i,poi[i]);
		add(n+i,T,poi[n+i]);
	}

	printf("%d
",dinic());
	dfs(S);
	int cnt=0;
	for(int i=0;i<tot;i+=2)//先寻找方案数
	{
		int a=ver[i^1],b=ver[i];
		if(vis[a]&&!vis[b]) ++cnt;
	}
	printf("%d
",cnt);
	for(int i=0;i<tot;i+=2)//寻找方案
	{
		int a=ver[i^1],b=ver[i];
		if(vis[a]&&!vis[b])
		{
			if(a==S) printf("%d +
",b);
			if(b==T) printf("%d -
",a-n);
		}
	}
	return 0;
}

最大点权独立集

定义一个无向图 (G<V,E>) 的点独立集 (V^{prime}) 为：对于 (forall (u,v)in E) 满足 (uin V^{prime} , vin V^{prime}) 不同时成立。

转化为布尔代数形式 ，由德摩根律

[lnot (uin V^{prime}land vin V^{prime})\ Leftrightarrow lnot uin V^{prime}lorlnot vin V^{prime}\ Leftrightarrow uin overline{V^{prime}}lor vin overline{V^{prime}} ]

我们发现，得到的条件与点覆盖集相似。

实际上有这样一个定理：若 (overline{V^{prime}}) 是不含孤立点的图 (G<V,E>) 的一个点覆盖集，则当且仅当(V^{prime}) 是一个点独立集。

证明：

  1. 充分性：

    假设 (V^{prime}) 不是独立集，即 (exists u,vin V^{prime}) 使得 ((u,v)in E)，那么 ((u,v)) 就被 (overline{V^{prime}}) 遗漏了。这与 (overline{V^{prime}}) 是一个点覆盖集矛盾。

    故当 (overline{V^{prime}}) 是点覆盖集时 (V^{prime}) 是点独立集。

  2. 必要性：

    假设 (overline{V^{prime}}) 不是覆盖集，即 (exists (u,v)in E) 使得 (u,v otin overline{V^{prime}})。此时 (u,vin V^{prime}) ，但由于 ((u,v)in E) 所以与 (V^{prime}) 是独立集矛盾。

    故当 (V^{prime}) 是点独立集时 (overline{V^{prime}}) 是点覆盖集。

    综上，定理成立。

根据这个定理，我们可以得出一个推论：若 (V^{prime}) 是不含孤立点的图 (G<V,E>) 的最大点权独立集，那么 (overline{V^{prime}}) 是最小点权覆盖集。

  • 证明：

    由上面定理我们可以得到：(V=V^{prime}+overline{V^{prime}})

    [sumlimits_{vin V}w_v=sumlimits_{vin V^{prime}}w_v+sumlimits_{vin overline{V^{prime}}}w_v ]

    (ecause sumlimits_{vin V}w_v) 是一个定值，所以最小化 (sumlimits_{vin overline{V^{prime}}}w_v) 就是最大化 (sumlimits_{vin V^{prime}}w_v)。

所以，我们只需要对原图求一次最小点权覆盖，然后补集就可以了。

王者之剑

给出一个 (n×m) 网格，每个格子上有一个价值 (v_{i,j}) 的宝石。

(Amber) 可以自己决定起点，开始时刻为第 (0) 秒。

以下操作，在每秒内按顺序执行。

  1. 若第 (i) 秒开始时，(Amber) 在 ((x,y))，则 (Amber) 可以拿走 ((x,y)) 上的宝石。

  2. 在偶数秒时（(i) 为偶数），则 (Amber) 周围 (4) 格的宝石将会消失。

  3. 若第 (i) 秒开始时，(Amber) 在 ((x,y))，则在第 ((i+1)) 秒开始前，(Amber) 可以马上移动到相邻的格子 ((x+1,y),(x−1,y),(x,y+1),(x,y−1)) 或原地不动 ((x,y))。
    求 Amber 最多能得到多大总价值的宝石。

上图给出了一个 (2×2) 的网格的例子。

在第 (0) 秒，首先选择 (B2) 进入，取走宝石 (3)；由于是偶数秒，周围的格子 (A2,B1) 的宝石 (1,2) 消失；向 (A2) 走去。

在第 (1) 秒，由于 (A2) 的宝石已消失，无宝石可取；向 (A1) 走去。

在第 (2) 秒，取走 (A1) 的宝石 (4)。

全程共取得 (2) 块宝石：宝石 (3) 和宝石 (4)。

输入格式

第一行包含两个整数 (n,m)。

接下来 (n) 行，每行包含 (m) 个整数，用来描述宝石价值矩阵。其中第 (i) 行第 (j) 列的整数表示 (v_{i,j}) 。

输出格式

输出可拿走的宝石最大总价值。

数据范围

(1≤n,m≤100 , 1≤vi,j≤1000)

输入样例：

2 2
1 2
2 1

输出样例：

4

分析

我们观察一下这个问题的某些 显然的 特殊性质

首先，我们只能在偶数秒拿到宝石。奇数秒走到的格子已经被上一个偶数秒清空了。

而且我们不能同时拿到相邻格子上的两个宝石。原因同上。

这个时候已经有点独立集那味了。我们若是把相邻的格子黑白染色并连上边，那么最优方案选出来的点就组成一个独立集，还是二分图的最大点权独立集。其实我们可以看出，每种合法方案都可以转化这个二分图的一个独立集。

但是每个独立集都是一个合法方案吗？这可不一定。我们需要证明出来。

怎么去考虑？最好的方法是对任意独立集直接构造一个合法方案出来。

我们先把每一行看做一个阶段，用 “S” 形路线试着挨个遍历每个阶段。以下图一个 (6 imes 6) 的矩阵举例

标灰色的点是独立集中的点，也就是我们要取到的点。

进入 (A2) 时一定是偶数秒，进入(A3) 是奇数秒，进入 (A4) 是偶数秒，如果我们要保证能拿到 (A5) 那我们就要在 (A3) 停顿一秒，但是我们一停顿就会将我们接下来要取的 (B3) 给炸了。并且在其他任何地方停顿都无法保证任意一个的灰点都能够被取到。所以这种构造方式不可行。

但是我们不一定要遍历所有的格子。我们若是每两行为一个阶段，在遍历第一行时连着第二行的一起取完。然后不遍历第二行就可以防止影响下个阶段。可按照如下方式构造：

  1. 按遍历方向顺序，依次取宝石。 (废话)
  2. 第一行的宝石在偶数秒时直接进入格子获取。
  3. 第二行的宝石我们要在奇数秒时进入其在第一行的对应格子，然后在偶数秒进入格子取宝石，之后立即返回第一行对应格子，奇偶性没有改变。

来实际操作一下：

我们可以看到，当到达 (A3) 时，我们直接上去拿到 (B3) ，用时两秒，时间奇偶性没变。(A5) 要求在偶数秒进入，那我们就在 (A3) 停顿一秒。由于 (B3) 已经拿了，所以没有影响。同样的，我们应在奇数秒进入 (C6) ，以便取到 (D6) ，取完 (D6) 回到 (C6) 时还是奇数秒，可以顺利取到 (C5)。

试着证它能否取到所有独立集的点。

首先，阶段之间是没有冲突的。我们只有在第二行有灰点时才去第二行，由独立集的性质能知道下一阶段第一行对应位置是没有灰点的。

其次我们需证，对于阶段内的点，必定有一个操作序列能够取到所有的点。

我们将每个格子的要求序列化。对于阶段的第一行，将灰点所在位置设为 (0) ，代表这个点必须偶数秒进入；将第二行有对应灰点的位置设为 (1) ，代表必须在奇数时进入这个点；其他的点都设为 (?) ，假装我们不知道。

就举上面 (Phase 1) 的例子。

构造出来一个序列 (?,0,1,?,0,?)

根据“不能同时拿到相邻格子上的两个宝石”的推论，该序列不应该存在连续的两个 (0) 或 (1) 必然是 (01) 相间的形式。

由于对于一段连续的 (?) 我们很容易构造序列使其只有单个 (?)，所以问题集中于非 (?) 和 (?) 的衔接上。

我们直接开始分类讨论。

  1. (0,?,0) 或 (1,?,1) 我们只需要令 (?) 为 (1) 或 (0) 即可。

  2. (1,?,0) ，此时我们需要在这一格停留一下，得到序列 (1,(0)1,0)

  3. (0,?,1) ，仍然是用停留解决问题，得到序列 (0,(1)0,1) 。

综上，对于任意一个独立集，我们都可以构造出一个合法方案取到独立集内所有点。

你已经证明了每一个方案与独立集一一对应，只需要放心大胆跑网络流就可以了，快去试一试吧

code

#include <bits/stdc++.h>
using namespace std;

const int N=1e5+10, M=2e6+10,INF=1e8;

int n,m,S,T;
int head[N],ver[M],cc[M],nxt[M],tot=0;
void add(int x,int y,int c)
{
	ver[tot]=y; cc[tot]=c; nxt[tot]=head[x]; head[x]=tot++;
	ver[tot]=x; cc[tot]=0; nxt[tot]=head[y]; head[y]=tot++;
}
int q[N],d[N],cur[N];
int dx[5]={0,1,0,-1};
int dy[5]={-1,0,1,0};

inline int index_(int i,int j)	{return (i-1)*m+j;}

bool bfs()
{
	int hh=0,tt=0;
	memset(d,-1,sizeof d);
	q[0]=S, d[S]=0, cur[S]=head[S];
	while(hh<=tt)
	{
		int x=q[hh++];
		for(int i=head[x];~i;i=nxt[i])
		{
			int y=ver[i];
			if(d[y]==-1 && cc[i])
			{
				d[y]=d[x]+1;
				cur[y]=head[y];
				if(y==T) return 1;
				q[++tt]=y;
			}
		}
	}
	return 0;
}

int find(int u,int lim)
{
	if(u==T) return lim;
	int flow=0;
	for(int i=cur[u];~i && flow<lim;i=nxt[i])
	{
		int y=ver[i];
		cur[u]=i;
		if(d[y]==d[u]+1 && cc[i])
		{
			int tmp=find(y,min(lim-flow,cc[i]));
			if(!tmp) d[y]=-1;
			cc[i]-=tmp; cc[i^1]+=tmp; flow+=tmp;
		}
	}
	return flow;
}

int dinic()
{
	int res=0,flow;
	while(bfs()) while(flow=find(S,INF)) res+=flow;
	return res;
}

int main()
{
	scanf("%d%d",&n,&m);
	S=0,T=N-10;
	memset(head,-1,sizeof head);
	int sum=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			int x;
			scanf("%d",&x);
			sum+=x;
			if((i+j)&1)
			{
				add(S,index_(i,j),x);
				for(int k=0;k<4;k++)
				{
					int xx=i+dx[k],yy=j+dy[k];
					if(xx>=1&&xx<=n&&yy>=1&&yy<=m)
						add(index_(i,j),index_(xx,yy),INF);
				}
			}
			else {
				add(index_(i,j),T,x);
			}
		}
	}
	printf("%d",sum-dinic());
	return 0;
}

建图实战

有线电视网络

给定一张 (n) 个点 (m) 条边的无向图，求最少去掉多少个点，可以使图不连通。

如果不管去掉多少个点，都无法使原图不连通，则直接返回 (n)。

输入格式

输入包含多组测试数据。

每组数据占一行，首先包含两个整数 (n) 和 (m)，接下来包含 (m) 对形如 ((x,y)) 的数对，形容点 (x) 与点 (y) 之间有一条边。

数对 ((x,y)) 中间不会包含空格，其余地方用一个空格隔开。

输出格式

每组数据输出一个结果，每个结果占一行。

数据范围

(0≤n≤50)

输入样例：

0 0
1 0
3 3 (0,1) (0,2) (1,2)
2 0
5 7 (0,1) (0,2) (1,3) (1,2) (1,4) (2,3) (3,4)

输出样例：

0
1
3
0
2

解析

我们要通过删点的方式划出两个点集使得这两个点集不连通，很有最小割的感觉。

但是这个题让我们删点而不是删边。最小割容量定义的重点放在边上，所以我们要想个办法化点为边。拆点的解法就呼之欲出了。

由于我们图中没有规定哪两个点集必须互异，所以我们首先要枚举源汇点，保证考虑所有的方案。

确定好源汇点后再来看一下建图。我们不希望原图的边成为割边，所以我们在连原图的边时将容量设为 (+infty) 。我们要求的是总点数，所以入点到出点的连边容量为 (1)。

然后求最小割就可以了。

定义对于上文构建的网络 (N<V_N,E_N>) 的简单割为一个合法割当它所有的割边是入点和出点内部的边。

现在我们需证任意一个简单割与原问题方案一一对应。

  1. 简单割 (Rightarrow) 删点方案

    我们找出所有的割边，将割边删去。假设此时有一条路径 ((u,v)) 从 (s ightarrow t) ，那么就与这是一个简单割矛盾。故删去割边之后图不连通。我们可以得到一个删点方案 (V^{prime}={v|vin V land v ext{内部的边是割边}}) 。

  2. 删点方案 (Rightarrow) 简单割

    一个极小删点方案 (V^{prime}) 当且仅当 (V^{prime}-{v}) 不是合法删点方案对 (forall vin V^{prime}) 成立。

    为了简便，我们只证明极小删点方案对应简单割。任意一个非极小删点方案都可以优化为一个极小删点方案。

    我们找出极小删点方案内的所有的点 (v) ，删去其内部的边 ((v_{in},v_{out})) 。我们就能得到两个不连通的点集 (V_0 , overline{V_0}) ，当我们指定源点汇点分别于 (V_0,overline{V_0}) 时，我们就可以构造出一个简单割。割边是我们删去的边。

综上，我们可以知道简单割和删点方案可以一一对应。并且最小割对应确定 (s,t) 下的最小删点方案。

所以我们只需要按以上方式建图，然后求最小割就可以了。

code

#include <bits/stdc++.h>
using namespace std;

const int N=1e3+10, M=5e5+10, INF=1e8;

int head[N],ver[M],nxt[M],cc[M],tot=0;
void add(int x,int y,int c)
{
	ver[tot]=y; cc[tot]=c; nxt[tot]=head[x]; head[x]=tot++;
	ver[tot]=x; cc[tot]=0; nxt[tot]=head[y]; head[y]=tot++;
}
int q[N],d[N],cur[N];
int n,m,S,T;

bool bfs()
{
	int hh=0,tt=0;
	memset(d,-1,sizeof d);
	q[0]=S; d[S]=0; cur[S]=head[S];
	while(hh<=tt)
	{
		int x=q[hh++];
		for(int i=head[x];~i;i=nxt[i])
		{
			int y=ver[i];
			if(d[y]==-1 && cc[i])
			{
				d[y]=d[x]+1;
				cur[y]=head[y];
				if(y==T) return 1;
				q[++tt]=y;
			}
		}
	}
	return 0;
}

int find(int u,int lim)
{
	if(u==T) return lim;
	int flow=0;
	for(int i=cur[u];~i && flow<lim; i=nxt[i])
	{
		int y=ver[i];
		cur[u]=i;
		if(d[y]==d[u]+1 && cc[i])
		{
			int tmp=find(y,min(cc[i],lim-flow));
			if(!tmp) d[y]=-1;
			cc[i]-=tmp; cc[i^1]+=tmp; flow+=tmp;
		}
	}
	return flow;
}

int dinic()
{
	int res=0,flow;
	while(bfs()) while(flow=find(S,INF)) res+=flow;
	return res;
}

int main()
{
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		memset(head,-1,sizeof head);
		tot=0;
		for(int i=0;i<n;i++) add(i,n+i,1);
		for(int i=0;i<m;i++)
		{
			int a,b;
			scanf(" (%d,%d)",&a,&b);
			add(n+a,b,INF);
			add(n+b,a,INF);
		}
		int ans=n;
		for(int i=0;i<n;i++)
		{
			for(int j=0l;j<i;j++)
			{
				S=n+i,T=j;
				ans=min(ans,dinic());
				for(int k=0;k<tot;k+=2)
				{
					cc[k]+=cc[k^1];
					cc[k^1]=0;
				}
			}
		}
		printf("%d
",ans);
	}
	return 0;
}

太空飞行计划问题

我们转述一下题意：有 (m) 个实验 (n) 个仪器。做第 (i) 个试验需要集合 (R_jin I) 里的所有仪器。假设所有仪器编号 (1sim k) ，编号为 (k) 的仪器花费 (c_k)。如果做了实验 (i) 就会获得 (p_i) 的收益。求最大收益。

如果我们将实验和仪器抽象为两种点，如果实验依赖一种仪器我们从实验向仪器连一条边，那么我们可能连出如下一张图。

我们要是选择一个实验，那么就要将与其相连的所有实验都选上。也就是说，我们选中的子图里面，不应该有向外的边。

这就是闭合图的概念。其实这个题和 [NOI2006]最大获利 是差不多的。但是这里的实验可能会依靠多个或只依靠一个仪器，所以本题不能使用最大密度子图，只能由最大权闭合图来做。

总之，我们只需要给表示实验的点附上正权，给表示仪器的点赋上负权，用最大权闭合图做就可以了。

最大利润就是正点权和减最小割。

输出方案的话我们求得最小割 (<S,T>) 后，在残留网络中从源点沿着容量 (>0) 的边 DFS，所有能够遍历到的点就是 (S) 集合内的点。也就是我们要选的点。

code

#include <bits/stdc++.h>
using namespace std;

const int N=500,M=1e5+10,INF=1e8+10;

int m,n,S,T;
int head[N],ver[M],nxt[M],cc[M],tot=0;
void add(int x,int y,int c)
{
	ver[tot]=y; cc[tot]=c; nxt[tot]=head[x]; head[x]=tot++;
	ver[tot]=x; cc[tot]=0; nxt[tot]=head[y]; head[y]=tot++;
}
int q[N],d[N],cur[N];

bool bfs()
{
	int hh,tt;
	hh=tt=0;
	memset(d,-1,sizeof d);
	q[0]=S,d[S]=0,cur[S]=head[S];
	while(hh<=tt)
	{
		int x=q[hh++];
		for(int i=head[x];~i;i=nxt[i])
		{
			int y=ver[i];
			if(d[y]==-1 &&cc[i])
			{
				d[y]=d[x]+1;
				cur[y]=head[y];//记录当前路
				if(y==T) return 1;
				q[++tt]=y;
			}
		}
	}
	return 0;
}

int find(int u,int lim)//从源点流向u点的最大流量是lim的话
{
	if(u==T) return lim;
	int flow=0;
	for(int i=cur[u];~i && flow<lim;i=nxt[i])
	{
		cur[u]=i;//记录当前路
		int y=ver[i];
		if(d[y]==d[u]+1 &&cc[i])
		{
			int tmp=find(y,min(cc[i],lim-flow));
			if(!tmp) d[y]=-1;
			cc[i]-=tmp;cc[i^1]+=tmp;flow+=tmp;
		}
	}
	return flow;
}

int dinic()
{
	int res=0,flow;
	while(bfs())
	{
		while(flow=find(S,INF)) res+=flow;
	}
	return res;
}
bool vis[N];

void dfs(int x)
{
	vis[x]=1;
	for(int i=head[x];~i;i=nxt[i])
	{
		int y=ver[i];
		if(!vis[y] && cc[i]) dfs(y);
	}
	return ;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin>>m>>n;
	memset(head,-1,sizeof head);
	S=0,T=n+m+5;
	int sum=0;
	string str;
	getline(cin,str);
	for(int i=1;i<=m;i++)
	{
		int w,x;
		getline(cin,str);
		stringstream ssin(str);
		ssin>>w;
		sum+=w;
		add(S,i,w);
		while(ssin>>x) add(i,m+x,INF);
	}
	for(int i=1;i<=n;i++)
	{
		int p;
		cin>>p;
		add(m+i,T,p);
	}

	int res=dinic();
	dfs(S);
	for(int i=1;i<=m;i++)
	{
		if(vis[i]) cout<<i<<' ';
	}
	cout<<'
';
	for(int i=1;i<=n;i++)
	{
		if(vis[m+i]) cout<<i<<' ';
	}
	cout<<'
'<<sum-res;
	return 0;
}

骑士共存问题

观察题目，我们可以得到：

当一个棋子在 ((x,y)) 放下后，((x+2,y+1),(x+2,y-1),(x+1,y+2),(x+1,y-2),(x-1,y+2),(x-1,y-2),(x-2,y-1),(x-2,y+1)) 都不能放棋子。 日常废话

同时我们发现当一个棋子在一个点上的时候，其阻挡的点都在奇偶性相反的点。

我们把点按奇偶性染色，得到两个点集 (A)，(B) 分别为奇点偶点。我们再按照上面给出的阻挡关系连边，就可以发现这是一个二分图最大点独立集的问题。

里面有障碍物又怎么处理呢？简单，不连到障碍物的边就是了。

本题对应关系非常直观所以就不严谨证明了(逃

code:

#include<bits/stdc++.h>
using namespace std;

const int N=1e5+10,M=4e6+10,INF=1e9;

int head[N],ver[M],nxt[M],cc[M],tot=0;
void add(int x,int y,int c)
{
	ver[tot]=y; cc[tot]=c; nxt[tot]=head[x]; head[x]=tot++;
	ver[tot]=x; cc[tot]=0; nxt[tot]=head[y]; head[y]=tot++;
}
int q[N],d[N],cur[N];
bool mp[210][210];
int n,m,S,T;

int get(int i,int j)
{
	return (i-1)*n+j;
}

bool bfs()
{
	int hh=0,tt=0;
	memset(d,-1,sizeof d);
	q[0]=S; d[S]=0; cur[S]=head[S];
	while(hh<=tt)
	{
		int x=q[hh++];
		for(int i=head[x];~i;i=nxt[i])
		{
			int y=ver[i];
			if(d[y]==-1 && cc[i])
			{
				d[y]=d[x]+1;
				cur[y]=head[y];
				if(y==T) return 1;
				q[++tt]=y;
			}
		}
	}
	return 0;
}

int find(int u,int lim)
{
	if(u==T) return lim;
	int flow=0;
	for(int i=cur[u];~i && flow<lim;i=nxt[i])
	{
		int y=ver[i];
		cur[u]=i;
		if(d[y]==d[u]+1 && cc[i])
		{
			int tmp=find(y,min(cc[i],lim-flow));
			if(!tmp) d[y]=-1;
			cc[i]-=tmp; cc[i^1]+=tmp; flow+=tmp;
		}
	}
	return flow;
}

int dinic()
{
	int res=0,flow;
	while(bfs())
	{
		while(flow=find(S,INF)) res+=flow;
	}
	return res;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin>>n>>m;
	memset(head,-1,sizeof head);
	for(int i=1;i<=m;i++)
	{
		int x,y;
		cin>>x>>y;
		mp[x][y]=1;
	}
	S=0,T=N-2;

	int dx[]={-2,-1,1,2,2,1,-1,-2};
	int dy[]={1,2,2,1,-1,-2,-2,-1};
	int sum=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(mp[i][j]) continue;
			++sum;
			if((i+j)&1)
			{
				add(S,get(i,j),1);
				for(int k=0;k<8;k++)
				{
					int xx=i+dx[k],yy=j+dy[k];
					if(xx>=1 && xx<=n && yy>=1 && yy<=n && !mp[i][j])
					{
						add(get(i,j),get(xx,yy),INF);
					}
				}
			}
			else
				add(get(i,j),T,1);

		}
	}
	cout<<sum-dinic();
}

本文的讲解内容就到这里，这些网络瘤问题的建模方式最主要还是一个经验问题。积少成多，聚沙成塔。

参考文献

胡伯涛-《最小割模型在信息学奥赛中的应用》

本文严谨证明过程基本借鉴 照抄 了里面的思路。这篇论文讲的非常清晰严谨，值得细研。

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/IzayoiMiku/p/14423288.html