题目描述
输入格式
输出格式
仅包含一个整数,表示可以获得的最大能源收入。注意,你也可以选择不进行任何攻击,这样能源收入为0。
样例输入
3 2 10 0 20 0 -10 0 -5 1 0 0 100 1 2 1 100 0
样例输出
25
数据范围及提示
在样例中, 植物P1,1可以攻击位置(0,0), P2, 0可以攻击位置(2,1)。
一个方案为,首先进攻P1,1, P0,1,此时可以攻击P0,0 。共得到能源收益为(-5)+20+10 = 25。注意, 位置(2,1)被植物P2,0保护,所以无法攻击第2行中的任何植物。
【大致数据规模】
约20%的数据满足1 ≤ N, M ≤ 5; 约40%的数据满足1 ≤ N, M ≤ 10; 约100%的数据满足1 ≤ N ≤ 20,1 ≤ M ≤ 30,-10000 ≤ Score ≤ 10000 。
题解
首先注意到,由于僵尸是从右侧开始走的,所以同一行内右侧植物可以认为是保护左侧一个植物的,在保护关系加边的时候可以加上这类边。
很好想,我们注意到如果把植物间的保护关系建出图,那么就可以发现,其实就是个最大权闭合子图(相当于最小割)的问题,不过形成环的植物们都是无敌的,所以可以用tarjan或者topsort求出环,然后把环上的点全部删掉,剩下的跑最大权闭合子图就行了。
网络流建图方式:
把剩下的点分为两类: score大于零的:从源点S向此点连边,流量为score
score小于零的:从此点向汇点T连边,流量为-score
然后每个点向自己保护的点连一条反向边,流量为INF
最大权闭合子图的求法:跟最小割一样,把剩下的点里面正的score全加起来,减去跑的dinic返回的值(最小割),就是答案。当然此处要和0取较大值。
代码
#include <iostream> #include <cstring> #include <cstdlib> #include <cstdio> #include <cmath> #include <algorithm> #include <queue> #include <stack> using namespace std; int get_num(){ int num = 0; char c; bool flag = false; while((c = getchar()) == ' ' || c == '\r' || c == '\n'); if(c == '-') flag = true; else num = c - '0'; while(isdigit(c = getchar())) num = num * 10 + c - '0'; return (flag ? -1 : 1) * num; } const int maxn = 605; const int INF = 2147483647; int n,m,c,b,ans = 0,ans2 = 0; int S,T; queue<int>q; struct plant{ int x,y,sc,w; }a[maxn]; struct edge1{ int fr,to,next; }e[maxn*maxn]; int h[maxn],cnt = 0; void add1(int u,int v){ e[cnt].fr = u;e[cnt].to = v;e[cnt].next = h[u];h[u] = cnt++; } struct edge2{ int fr,to,cap,next; }edges[maxn*maxn]; int g[maxn],sum = 0; void add2(int u,int v,int c){ edges[sum].fr = u;edges[sum].to = v;edges[sum].cap = c;edges[sum].next = g[u];g[u] = sum++; edges[sum].fr = v;edges[sum].to = u;edges[sum].cap = 0;edges[sum].next = g[v];g[v] = sum++; } stack<int>s; int dfst = 0; int dfn[maxn],low[maxn],ins[maxn],vis[maxn],scc_cnt,tot = 0,cur[maxn],d[maxn]; void dfs(int x){ dfn[x] = low[x] = ++dfst; s.push(x); ins[x] = 1; for(int i = h[x];i != -1;i = e[i].next){ if(!dfn[e[i].to]){ dfs(e[i].to); low[x] = min(low[x],low[e[i].to]); } else if(ins[e[i].to])low[x] = min(low[x],dfn[e[i].to]); } if(dfn[x] == low[x]){ scc_cnt++; tot = 0; while(true){ int p = s.top(); s.pop(); ins[p] = 0; tot++; vis[x] = 1; if(p == x){ if(tot == 1)vis[x] = 0; break; } } } return; } void tarjan(){ for(int i = 1;i <= n*m;++i){ if(!dfn[i])dfs(i); } return; } void dfs2(int now){ for(int i = h[now];i != -1;i = e[i].next){ if(vis[e[i].to])continue; vis[e[i].to] = 1; dfs2(e[i].to); } } void init(){ memset(h,-1,sizeof(h)); memset(g,-1,sizeof(g)); n = get_num(); m = get_num(); for(int i = 1;i <= n*m;++i){ a[i].x = (i-1) / m; a[i].y = (i-1) % m; a[i].sc = get_num(); a[i].w = get_num(); for(int j = 1;j <= a[i].w;++j){ b = get_num(); c = get_num(); int id = b * m + c + 1; add1(i,id); } if(a[i].y != 0)add1(i,i-1); } tarjan(); for(int i = 1;i <= n*m;++i){ if(vis[i])dfs2(i); } return; } bool bfs(){ memset(d,-1,sizeof(d)); d[S] = 0; q.push(S); while(!q.empty()){ int x = q.front(); q.pop(); for(int i = g[x];i != -1;i = edges[i].next){ int v = edges[i].to; if(d[v] == -1 && edges[i].cap > 0){ d[v] = d[x] + 1; q.push(v); } } } if(d[T] == -1)return false; return true; } int DFS(int x,int a){ if(x == T || a == 0)return a; int flow = 0; for(int& i = cur[x];i != -1;i = edges[i].next){ int v = edges[i].to; if(edges[i].cap > 0 && d[v] == d[x] + 1){ int r = min(edges[i].cap,a - flow); r = DFS(v,r); flow += r; edges[i].cap -= r; edges[i^1].cap += r; } } return flow; } int dinic(int s,int t){ int flow = 0; while(bfs()){ for(int i = s;i <= t;++i)cur[i] = g[i]; flow += DFS(s,INF); } return flow; } int main(){ init(); S = 0; T = n*m+1; for(int i = 1;i <= n*m;++i){ if(vis[i])continue; if(a[i].sc > 0){ add2(S,i,a[i].sc); ans += a[i].sc; } else add2(i,T,-a[i].sc); for(int j = h[i];j != -1;j = e[j].next) add2(e[j].to,i,INF); } ans2 = dinic(S,T); ans -= ans2; printf("%d\n",max(ans,0)); return 0; }
No Leanote account ? Sign up now.