[NOI2009]植物大战僵尸 [NOI2009]植物大战僵尸

嘟嘟嘟

这题看数据范围大概能猜出来是网络流，不过作为多年没写网络流的我，建图果然还是没想出来……

首先看到题目说，要想击溃某植物，就必须先击溃某植物，那可能会想到拓扑排序。但是拓扑排序和网络流并没有什么关系，还得换个方法。

然后我就想不到了。正解是我们反着建图，从被保护的植物向保护他的植物连边。于是我们就发现，如果这个点选了，那么他的出边到达的所有点都必须选。而要让选的权值最大，那不就是求最大权闭合子图嘛！

看起来完事了，但其实连样例都过不了，因为图中有环。
所以应该先拓扑排序，进过队列的点就是环外的点，然后只用这些点建的图跑出来才对。

怎么用网络流求最大权闭合子图我就不说了，贴个链接：网络流——最小割求最大权闭合子图

#include #include #include #include #include #include #include #include #include #include using namespace std; #define enter puts("") #define space putchar(' ') #define Mem(a, x) memset(a, x, sizeof(a)) #define In inline typedef long long ll; typedef double db; const int INF = 0x3f3f3f3f; const db eps = 1e-8; const int maxn = 25; const int maxm = 35; const int maxe = 5e6 + 5; inline ll read() { ll ans = 0; char ch = getchar(), last = ' '; while(!isdigit(ch)) last = ch, ch = getchar(); while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar(); if(last == '-') ans = -ans; return ans; } inline void write(ll x) { if(x < 0) x = -x, putchar('-'); if(x >= 10) write(x / 10); putchar(x % 10 + '0'); }int n, m, s, t; int val[maxn][maxm], G[maxn * maxm][maxn * maxm]; In int num(int x, int y) {return (x - 1) * m + y; }int du[maxn * maxm]; bool vis[maxn * maxn]; In void topoSort() { queue q; for(int i = 1; i <= n * m; ++i) if(!du[i]) vis[i] = 1, q.push(i); while(!q.empty()) { int now = q.front(); q.pop(); for(int i = 1; i <= n * m; ++i) if(G[now][i]) { if(!--du[i]) vis[i] = 1, q.push(i); } } }struct Edge { int nxt, from, to, cap, flow; }e[maxe]; int head[maxn * maxm], ecnt = -1; In void addEdge(int x, int y, int w) { e[++ecnt] = (Edge){head[x], x, y, w, 0}; head[x] = ecnt; e[++ecnt] = (Edge){head[y], y, x, 0, 0}; head[y] = ecnt; }int dis[maxn * maxm]; In bool bfs() { Mem(dis, 0); dis[s] = 1; queue q; q.push(s); while(!q.empty()) { int now = q.front(); q.pop(); for(int i = head[now], v; ~i; i = e[i].nxt) { if(!dis[v = e[i].to] && e[i].cap > e[i].flow) { dis[v] = dis[now] + 1; q.push(v); } } } return dis[t]; } int cur[maxn * maxm]; In int dfs(int now, int res) { if(now == t || res == 0) return res; int flow = 0, f; for(int& i = cur[now], v; ~i; i = e[i].nxt) { if(dis[v = e[i].to] == dis[now] + 1 && (f = dfs(v, min(res, e[i].cap - e[i].flow))) > 0) { e[i].flow += f; e[i ^ 1].flow -= f; flow += f; res -= f; if(res == 0) break; } } return flow; } In int minCut() { int flow = 0; while(bfs()) { memcpy(cur, head, sizeof(head)); flow += dfs(s, INF); } return flow; }int sum = 0; In void buildGraph() { for(int i = 1; i <= n; ++i) for(int j = 1, u; j <= m; ++j) if(vis[u = num(i, j)]) { if(val[i][j] > 0) addEdge(s, u, val[i][j]), sum += val[i][j]; else addEdge(u, t, -val[i][j]); for(int k = 1; k <= n * m; ++k) if(vis[k] && G[u][k]) addEdge(k, u, INF); } }int main() { Mem(head, -1); n = read(), m = read(); t = num(n, m) + 1; for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j) { val[i][j] = read(); int w = read(), u = num(i, j); for(int k = 1, v; k <= w; ++k) { int x = read() + 1, y = read() + 1; G[u][v = num(x, y)] = 1; ++du[v]; } } for(int i = 1; i <= n; ++i) for(int j = 2, x, y; j <= m; ++j) if(!G[x = num(i, j)][y = num(i, j - 1)]) G[x][y] = 1, ++du[y]; topoSort(); buildGraph(); write(sum - minCut()), enter; return 0; }

【[NOI2009]植物大战僵尸】转载于:https://www.cnblogs.com/mrclr/p/10485584.html