BZOJ 1565 / P2805 [NOI2009]植物大战僵尸 (最大权闭合子图 最小割)

时间：2021-06-04 01:57:05

题意

自己看吧 BZOJ传送门

分析

BZOJ 1565 / P2805 [NOI2009]植物大战僵尸 (最大权闭合子图 最小割)

…

这道题其实就是一些点,存在一些二元限制条件,即如果要选uuu则必须选vvv.求得到的权值最大是多少.

建一个图,如果选uuu必须选vvv,则uuu向vvv连边.那么一个点如果要选肯定所有儿子都要选(也就是整棵子数都要选).这就是一个最大权闭合子图的模型.

可以发现,如果一个点数大于1的强连通分量每个点都不可选.那么去挑这些点,同时也可以去掉这些点的祖先.然后就是一个有向无环图.我们选点只要保证选了uuu必须选所有直接相连的儿子就行了.那么就可以用最小割建模来解决.

取到的数的价值之和=所有正数的和-(要舍弃掉的正数的和+要选的负数的和)

我们最小割的任务就是让后面括号中的最小.连边方式为:

  • SSS向每个正数连容量为数值的边
  • 每个负数向TTT连容量为绝对值的边
  • 在我们之前建的关系图中,父亲向每一个儿子连边,容量为∞\infty∞

这样的话:

  • 对于正数,分在SSS一边表示选择了,(也就是保留了它连向SSS的那条边),否则割掉这条边表示不选
  • 对于负数,分在SSS一边同样表示选择了,(也就是割掉了它连向TTT的那条边),否则保留这条边表示不选
  • 因为父亲向儿子连了∞\infty∞的边,那么这条边一定不会被割掉.那么一旦父亲要选,也就是父亲被分在了SSS一边,则儿子一定也会被分在SSS一边,也就是被选择了.因为如果儿子分在TTT那一边,就存在了从S→S\toS→父亲→\to→儿子→T\to T→T的一条增广路,而最小割是不允许这样的情况出现的.

注意细节,这题不是特别难

CODE

#include <vector>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

template<typename T>inline void read(T &num) {

    char ch; int flg=1;

    while((ch=getchar())<'0'||ch>'9')if(ch=='-')flg=-flg;

    for(num=0;ch>='0'&&ch<='9';num=num*10+ch-'0',ch=getchar());

    num*=flg;

}

const int MAXN = 605;

const int MAXM = 500005;

const int inf = 1e9;

struct edge { int to, nxt, c, w, C; }e[MAXM];

int n, m, S, T, cnt, fir[MAXN], info[MAXN];

inline void add(int u, int v, int cc) {

    e[cnt] = (edge){ v, fir[u], cc }, fir[u] = cnt++;

    e[cnt] = (edge){ u, fir[v], 0 }, fir[v] = cnt++;

}

namespace SAP { //最大流

	int h[MAXN], gap[MAXN], sz;

	int aug(int u, int Max) {

		if(u == T) return Max;

		int flow = 0, delta, v;

		for(int i = info[u]; ~i; i = e[i].nxt)

			if(e[i].c && h[v=e[i].to]+1 == h[u]) {

				delta = aug(v, min(Max-flow, e[i].c));

				e[i].c -= delta, e[i^1].c += delta; info[u] = i;

				if((flow+=delta) == Max || h[S] == sz) return flow;

			}

		if(!(--gap[h[u]])) h[S] = sz;

		++gap[++h[u]]; info[u] = fir[u];

		return flow;

	}

	inline int sap() {

		memcpy(info, fir, sizeof fir);

		int flow = 0; sz = T;

		while(h[S] < sz)

			flow += aug(S, inf);

		return flow;

	}

}

int A[MAXN], id[MAXN], sum;

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

vector<int>g[MAXN];

int dfn[MAXN], low[MAXN], scc[MAXN], num[MAXN], stk[MAXN], indx, tmr, tot;

void tarjan(int u) {

	dfn[u] = low[u] = ++tmr; stk[++indx] = u;

	for(int i = 0, siz = g[u].size(), v; i < siz; ++i)

		if(!dfn[v=g[u][i]]) tarjan(v), low[u] = min(low[u], low[v]);

		else if(!scc[v]) low[u] = min(low[u], dfn[v]);

	if(dfn[u] == low[u]) {

		++tot; do{ ++num[tot], scc[stk[indx]] = tot; }while(stk[indx--] != u);

	}

}

int vis[MAXN];

int dfs(int u) { //搜索判断子树是否合法

	if(vis[u]) return vis[u];

	if(num[scc[u]] > 1) return vis[u]=-1;

	for(int i = 0, siz = g[u].size(); i < siz; ++i)

		if(dfs(g[u][i]) == -1) return vis[u]=-1;

	return vis[u]=1;

}

int main () {

    memset(fir, -1, sizeof fir);

    read(n), read(m);

	for(int i = 1, x, y, z; i <= n*m; ++i) { //我是从1~n,1~m标号

		read(A[i]), read(z);

		while(z--) read(x), read(y), g[enc(x+1, y+1)].push_back(i);

		if(i % m) g[i].push_back(i+1); //要先打(x,y+1)的才能打到(x,y)

	}

	for(int i = 1; i <= n*m; ++i)

		if(!dfn[i]) tarjan(i);

	tot = 0;

	for(int i = 1; i <= n*m; ++i)

		if(dfs(i) == 1) id[i] = ++tot; //满足条件就给标号

	S = 0, T = tot+1;

	for(int i = 1; i <= n*m; ++i) if(id[i]) {

		for(int j = 0, siz = g[i].size(); j < siz; ++j)

			add(id[i], id[g[i][j]], inf); //父亲如果满足条件,儿子一定也满足

		if(A[i] > 0) add(S, id[i], A[i]), sum += A[i];

		else if(A[i] < 0) add(id[i], T, -A[i]);

	}

	printf("%d\n", sum-SAP::sap());

}

相关文章