bzoj1565 植物大战僵尸
程序员文章站
2023-02-21 09:13:13
思路
如果想消灭掉一个植物,那么必须先消灭掉左右能保护这个植物的植物。这就成了最大权闭合子图的模板题了。
有两个需要注意的地方。 ......
思路
如果想消灭掉一个植物,那么必须先消灭掉左右能保护这个植物的植物。这就成了最大权闭合子图的模板题了。
有两个需要注意的地方。
第一个就是,能保护当前植物的植物还有当前植物右面的所有植物。
第二个就是,在环里的植物或者是被在环里的植物所保护的植物是无法消灭的。
所以先拓扑一下,找出所有可能被消灭的植物,然后按照最大权闭合子图的做法做就行了。
代码
#include<cstdio> #include<iostream> #include<cstdlib> #include<cmath> #include<ctime> #include<queue> #include<cstring> #include<vector> #include<bitset> using namespace std; typedef long long ll; #define num(x,y) y + (x - 1) * m const int n = 100000,m = 1000000,inf = 1e9; vector<int>e[n]; ll read() { ll x=0,f=1;char c=getchar(); while(c<'0'||c>'9') { if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c<='9') { x=x*10+c-'0'; c=getchar(); } return x*f; } struct node { int v,nxt,w; }e[m]; int head[n],ejs = 1; void add(int u,int v,int w) { e[++ejs].v = v;e[ejs].w = w;e[ejs].nxt = head[u];head[u] = ejs; e[++ejs].v = u;e[ejs].w = 0;e[ejs].nxt = head[v];head[v] = ejs; } int n,m,w[n],du[n]; queue<int>q; int dep[n]; int s,t; int bfs() { memset(dep,0,sizeof(dep)); while(!q.empty()) q.pop(); dep[s] = 1;q.push(s); while(!q.empty()) { int u = q.front();q.pop(); for(int i = head[u];i;i = e[i].nxt) { int v = e[i].v; if(!dep[v] && e[i].w) { q.push(v); dep[v] = dep[u] + 1; if(v == t) return 1; } } } return 0; } int cur[n]; int dfs(int u,int now) { if(u == t) return now; int ret = 0; for(int &i = cur[u];i;i = e[i].nxt) { int v = e[i].v; if(dep[v] == dep[u] + 1 && e[i].w) { int k = dfs(v,min(now - ret,e[i].w)); e[i].w -= k; e[i ^ 1].w += k; ret += k; if(now == ret) return ret; } } return ret; } int dinic() { int ans = 0; while(bfs()) { memcpy(cur,head,sizeof(cur)); ans += dfs(s,inf); } return ans; } int main() { n = read(),m = read(); s = n * m + 1,t = s + 1; for(int i = 1;i <= n;++i) { for(int j = 1;j <= m;++j) { w[num(i,j)] = read();int k = read(); for(int z = 1;z <= k;++z) { int x = read() + 1,y = read() + 1; e[num(i,j)].push_back(num(x,y)); du[num(x,y)]++; } } } for(int i = 1;i <= n;++i) { for(int j = 2;j <= m;++j) { e[num(i,j)].push_back(num(i,j - 1)); du[num(i,j-1)]++; } } for(int i = 1;i <= n * m;++i) if(!du[i]) q.push(i); while(!q.empty()) { int u = q.front();q.pop(); int k = e[u].size(); for(int i = 0; i < k;++i) { int v = e[u][i]; du[v]--; if(!du[v]) q.push(v); } } int ans = 0; for(int i = 1;i <= n * m;++i) { if(!du[i]) { if(w[i] >= 0) add(s,i,w[i]),ans += w[i]; else add(i,t,-w[i]); int k = e[i].size(); for(int j = 0;j < k;++j) { int v = e[i][j]; if(!du[v]) add(v,i,inf); } } } cout<<ans - dinic(); return 0; }
上一篇: ASP应用中心得回放
下一篇: Redis订阅与发布