【BZOJ1565】【NOI2009】植物大战僵尸

好久没写博客了

题目

题目在这里

思路&做法

没什么好说的

应该很容易看出是 最大闭合子图 吧？

不过要注意一下的是，这题 可能有植物是不可能被击溃的 ， 所以要先跑一遍 拓扑排序 把这些点排除掉

代码

#include <iostream>

#include <cstdlib>

#include <cstdio>

#include <cmath>

#include <cstring>

#include <vector>

#include <queue>

#include <algorithm>

using namespace std;

const int N = 810, M = 500010;

const int INF = 0x7F7F7F7F;

int n, m;

int val[40][40];

vector< pair<int, int> > vec[40][40];

bool vis[N]; //vis为0的点就是不可能击溃的点

struct edge

{	int from, to, flow, cap;

	edge() { }

	edge(int _1, int _2, int _3, int _4) : from(_1), to(_2), flow(_3), cap(_4) { }

};

struct Dinic

{	edge edges[M];

	int head[N], nxt[M], tot;

	int L, R;

	inline void init()

	{	memset(head, -1, sizeof(head));

		tot = 0;

	}

	void add_edge(int x, int y, int z)

	{	edges[tot] = edge(x, y, 0, z);

		nxt[tot] = head[x];

		head[x] = tot++;

		edges[tot] = edge(y, x, 0, 0);

		nxt[tot] = head[y];

		head[y] = tot++;

	}

	int s, t;

	int d[N];

	bool bfs()

	{	memset(d, -1, sizeof(d));

		queue<int> q;

		q.push(s);

		d[s] = 0;

		while (!q.empty())

		{	int x = q.front(); q.pop();

			for (int i = head[x]; ~i; i = nxt[i])

			{	edge & e = edges[i];

				if (vis[e.to] && e.cap > e.flow && d[e.to] == -1)

				{	d[e.to] = d[x] + 1;

					q.push(e.to);

				}

			}

		}

		return d[t] != -1;

	}

	int cur[N];

	int dfs(int x, int a)

	{	if (x == t || a == 0) return a;

		int flow = 0, f;

		for (int & i = cur[x]; ~i; i = nxt[i])

		{	edge & e = edges[i];

			if (vis[e.to] && d[e.to] == d[x] + 1 && (f = dfs(e.to, min(a, e.cap-e.flow))) > 0)

			{	e.flow += f;

				edges[i^1].flow -= f;

				a -= f;

				flow += f;

				if (!a) break;

			}

		}

		return flow;

	}

	int maxflow(int _s, int _t)

	{	s = _s, t = _t;

		int flow = 0;

		while (bfs())

		{	for (int i = L; i <= R; i++)

				cur[i] = head[i];

			flow += dfs(s, INF);

		}

		return flow;

	}

} dinic;

int S, T;

int in[N];

int num[N];

inline int id(int x, int y) { return (x-1)*m + y; }

void topo()

{	queue<int> q;

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

		if (!in[i]) q.push(i);

	while (!q.empty())

	{	int x = q.front(); q.pop();

		vis[x] = 1;

		for (int i = dinic.head[x]; ~i; i = dinic.nxt[i])

		{	edge & e = dinic.edges[i];

			if (e.to == S || e.to == T || in[e.to] == 0 || e.cap > e.flow)

				continue;

			if ((--in[e.to]) == 0)

				q.push(e.to);

		}

	}

}

void build()

{	S = n * m + 1, T = n * m + 2;

	dinic.init();

	dinic.L = 0, dinic.R = n * m + 2;

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

	{	for (int j = 1; j <= m; j++)

		{	if (val[i][j] > 0)

				dinic.add_edge(S, id(i, j), val[i][j]);

			if (val[i][j] < 0)

				dinic.add_edge(id(i, j), T, -val[i][j]);

			for (int k = 0; k < vec[i][j].size(); k++)

			{	dinic.add_edge(id(vec[i][j][k].first, vec[i][j][k].second), id(i, j), INF);

				in[id(vec[i][j][k].first, vec[i][j][k].second)]++;

			}

			if (j > 1)

				dinic.add_edge(id(i, j-1), id(i, j), INF),

				in[id(i, j-1)]++;

		}

	}

}

int main()

{	scanf("%d %d", &n, &m);

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

		for (int j = 1; j <= m; j++)

		{	int l;

			scanf("%d %d", &val[i][j], &l);

			num[id(i, j)] = val[i][j];

			for (int k = 1; k <= l; k++)

			{	int x, y;

				scanf("%d %d", &x, &y);

				x++, y++;

				vec[i][j].push_back(make_pair(x, y));

			}

		}

	build();

	topo();

	int ans = 0;

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

		if (vis[i] && num[i] > 0)

			ans += num[i];

	vis[S] = vis[T] = 1;

	ans -= dinic.maxflow(S, T);

	printf("%d\n", ans);

	return 0;

}