首页 > 代码库 > 【bzoj1565】[NOI2009]植物大战僵尸 拓扑排序+最大权闭合图
【bzoj1565】[NOI2009]植物大战僵尸 拓扑排序+最大权闭合图
原文地址:http://www.cnblogs.com/GXZlegend/p/6808268.html
题目描述
输入
输出
仅包含一个整数,表示可以获得的最大能源收入。注意,你也可以选择不进行任何攻击,这样能源收入为0。
样例输入
3 2
10 0
20 0
-10 0
-5 1 0 0
100 1 2 1
100 0
样例输出
25
题解
拓扑排序+最大权闭合图
一个坑点卡了半年。。
由题目描述易知如果某些植物保护关系成了环,那它们都不能吃掉。所以若A能保护B,则A向B连边,再用拓扑排序判环(Tarjan也可以)。
注意如果A在B的前边,那么也应看作A保护B。
然后所有被无敌植物保护的植物都不能吃掉,应用dfs判掉。
最后跑最大权闭合图即可。
坑点有点多,实际没啥太难的。
#include <cstdio> #include <cstring> #include <queue> #define inf 0x3f3f3f3f using namespace std; queue<int> q; int n , m , map[610][610] , w[610] , rd[610] , flag[610]; int head[610] , to[400000] , val[400000] , next[400000] , cnt = 1 , s , t , dis[610]; void init() { int i , j; for(i = 1 ; i <= n * m ; i ++ ) for(j = 1 ; j <= n * m ; j ++ ) if(map[i][j]) rd[j] ++ ; for(i = 1 ; i <= n * m ; i ++ ) if(!rd[i]) q.push(i); while(!q.empty()) { i = q.front() , q.pop() , flag[i] = 1; for(j = 1 ; j <= n * m ; j ++ ) { if(map[i][j]) { rd[j] -- ; if(!rd[j]) q.push(j); } } } } void add(int x , int y , int z) { to[++cnt] = y , val[cnt] = z , next[cnt] = head[x] , head[x] = cnt; to[++cnt] = x , val[cnt] = 0 , next[cnt] = head[y] , head[y] = cnt; } bool bfs() { int x , i; while(!q.empty()) q.pop(); memset(dis , 0 , sizeof(dis)); dis[s] = 1 , q.push(s); while(!q.empty()) { x = q.front() , q.pop(); for(i = head[x] ; i ; i = next[i]) { if(val[i] && !dis[to[i]]) { dis[to[i]] = dis[x] + 1; if(to[i] == t) return 1; q.push(to[i]); } } } return 0; } int dinic(int x , int low) { if(x == t) return low; int temp = low , i , k; for(i = head[x] ; i ; i = next[i]) { if(val[i] && dis[to[i]] == dis[x] + 1) { k = dinic(to[i] , min(temp , val[i])); if(!k) dis[to[i]] = 0; val[i] -= k , val[i ^ 1] += k; if(!(temp -= k)) break; } } return low - temp; } void dfs(int x) { int i; for(i = 1 ; i <= n * m ; i ++ ) if(map[x][i] && flag[i]) flag[i] = 0 , dfs(i); } int main() { int i , j , k , x , y , ans = 0; scanf("%d%d" , &n , &m); s = 0 , t = n * m + 1; for(i = 1 ; i <= n ; i ++ ) { for(j = 1 ; j <= m ; j ++ ) { scanf("%d%d" , &w[(i - 1) * m + j] , &k); if(j > 1) map[(i - 1) * m + j][(i - 1) * m + j - 1] = 1; while(k -- ) scanf("%d%d" , &x , &y) , map[(i - 1) * m + j][x * m + y + 1] = 1; } } init(); for(i = 1 ; i <= n * m ; i ++ ) if(!flag[i]) dfs(i); for(i = 1 ; i <= n * m ; i ++ ) { if(flag[i]) { if(w[i] >= 0) add(s , i , w[i]) , ans += w[i]; else add(i , t , -w[i]); for(j = 1 ; j <= n * m ; j ++ ) if(map[j][i] && flag[j]) add(i , j , inf); } } while(bfs()) ans -= dinic(s , inf); printf("%d\n" , ans); return 0; }
【bzoj1565】[NOI2009]植物大战僵尸 拓扑排序+最大权闭合图
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。