在样例中, 植物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 。
膜拜曾经参加过NOI的大牛Orz…… 题面还是很有意思的，当时很火的植物大战僵尸，想当年这个游戏可是充斥着我的整个小学生活的。也几乎是因为这个我荒废了学习…… 说起网络流的话我自认为很拿手，因为在高中阶段我破题最多应该就是网络流(再一次GDKOI里我写出了网络流，别提多开心)。以致于到后面什么图论题都会想办法往网络流方向上靠。但是，老实说，这题这样的模型我还是第一次见。 经过学习，可以知道，这一类问题就是最大权闭合子图问题，即给出一些点，每个点有点权(有正有负)，求一个闭合子图，使得子图内点的权值和最大。其中，闭合图定义为，对于u∈闭合图，若有边<u,v>，那么v∈闭合图。很显然，本题基本符合这一模型，那么我们就具体来说说这一类问题的方法。 这个问题当然又是有国家集训队的大牛写的论文的，具体见 胡伯涛《最小割模型在信息学竞赛中的应用》Orz…… 我们的做法是在原图的基础上构造一个新图，令源点连接所有点权为正的点流量即为点权，所有点权为负的点连接汇点流量取点权的相反数。对这样一个图求最小割，那么，最大权闭合子图的权值=正点权值和-最小割。问题就得到了解决，具体的证明看论文吧，其实也挺好理解的，我大致说说证明的思路。 首先定义简单割：满足所有割中的所有边都与源点s或者汇点t相连的割。 那么，可以证明，在新图中最小割一定是简单割，同时简单割分出来的、还有源点s的点集={s}U{闭合子图}。接着，我们对图的权值进行表示。简单割的权值(c1)=s与割另一边权值为正的点权值和(s1)+t与割另一边负的点权绝对值和(s2)。然后闭合子图的点权值和(c2)=闭合子图中正点权值和(s3)-闭合子图中负点权绝对值和(s2)。二者相加得c1+c2=s1+s2+s3-s2=s1+s3=所有正点权值和(s4)，进行变形得c2=s4-c1。由于s4是定值，所以显然，当c1最小即c1为最小割的时候s4(闭合子图点权和)最大。故"最大权闭合子图的权值=正点权值和-最小割"得证。 看证明的时候时刻注意每一个概念的含义，然后这里的每一个定理和引理都是适用于我们自己新建的图的，并不一定适用于所有的图。我自己看证明的时候曾经忽略了这个，然后就觉得证明有误，可以找出反例，但是实际上在规定的图中这些定理都是满足的。 然后关于本题，如果说有先决条件(u,v)，那么我们连边并不是想当然的连接(u,v)，而是连接(v,u)。这个的几何意义在于，如果要走到v(流经v)，那么也一定要流经u(流量守恒原理)。有多个先决条件的情况也是如此，根据求最大流的算法，一定会尽量的满足所有先决条件，当无法满足时(负权和大于正权)，又因流量限制会使得最后的结果仍让是非负的。好吧我都快把自己给说晕了，反正就是那个意思。 除此之外，本体还可能不是一个DAG，所以在这之前我们要先进行tarjan。即如果存在某个连通分量中点的个数大于1，那么次连通分量内的所有点都无法到达，在建立新的流网络时就不把这个点加入。整个过程具体见代码： #include<iostream> #include<cstdio> #include<algorithm> #include<cstdlib> #include<cmath> #include<cstring> #include<iomanip> #include<vector> #include<queue> #define INF 2e9 #define LL long long #define MAX_V 1000 using namespace std; namespace Dinic { struct Edge { int dest,cap; Edge *next,*pair; Edge() {} Edge(int _dest,int _cap,Edge* _next):dest(_dest),cap(_cap),next(_next){} }; Edge *e[MAX_V],*c[MAX_V],*p[MAX_V]; int Stack[MAX_V],Queue[MAX_V],dist[MAX_V]; int s,t,top; long long maxflow; inline void addedge(int a,int b,int c) { e[a]=new Edge(b,c,e[a]); e[b]=new Edge(a,0,e[b]); e[a]->pair=e[b],e[b]->pair=e[a]; } bool lab() { memset(dist,0x3f,sizeof(dist)); dist[s]=0; Queue[1]=s; for (int l=1,r=1;l<=r;l++) { int i=Queue[l]; for (Edge *j=e[i];j;j=j->next) if (j->cap && dist[j->dest]>dist[i]+1) { dist[j->dest]=dist[i]+1; if (j->dest==t) return 1; Queue[++r]=j->dest; } } return 0; } inline void aug() { int top=0; Stack[++top]=s; memcpy(c,e,sizeof(e)); while (top) { int i=Stack[top]; if (i!=t) { Edge *j; for (j=c[i];j;j=j->next) if (j->cap && dist[j->dest]==dist[i]+1) break; if (j) top++,Stack[top]=j->dest,c[i]=p[top]=j; else top--,dist[i]=INF; } else { int delta=INF; for (int i=top;i>=2;i--) delta=std::min(delta,p[i]->cap); maxflow+=delta; for (int i=top;i>=2;i--) { p[i]->cap-=delta,p[i]->pair->cap+=delta; if (!p[i]->cap) top=i-1; } } } } long long dinic() { maxflow=0; while (lab()) aug(); return maxflow; } } int sorce[MAX_V],dfn[MAX_V],low[MAX_V],cnt[MAX_V],belong[MAX_V]; int n,m,dindex=0,bcnt; vector<int> g[MAX_V]; deque<int> stack; bool v[MAX_V]; inline void tarjan(int dep) { v[dep]=1; dfn[dep]=low[dep]=++dindex; stack.push_back(dep); for(int i=0;i<g[dep].size();i++) { int ff=g[dep][i]; if (!dfn[ff]) { tarjan(ff); low[dep]=min(low[dep],low[ff]); } else if (v[ff]) low[dep]=min(low[dep],dfn[ff]); } if (low[dep]==dfn[dep]) { bcnt++; int ff=0; while (ff!=dep) { ff=stack.back(); stack.pop_back(); belong[ff]=bcnt; v[ff]=0,cnt[bcnt]++; } } } inline void dfs(int dep) { v[dep]=1; for(int i=0;i<g[dep].size();i++) if (!v[g[dep][i]]) dfs(g[dep][i]); } int main() { scanf("%d%d",&n,&m); for(int i=0;i<n*m;i++) { int k; scanf("%d%d",&sorce[i],&k); for(int j=0;j<k;j++) { int x,y; scanf("%d%d",&x,&y); g[i].push_back(x*m+y); } int x=i/m,y=i%m; if (y>0) g[i].push_back(i-1); } for(int i=0;i<m*n;i++) if (!dfn[i]) tarjan(i); tarjan求连通分量 memset(v,0,sizeof(v)); for(int i=0;i<m*n;i++) if (cnt[belong[i]]>1&&!v[i]) dfs(i); 把形成环的点标记为不可到达 int s=Dinic::s=n*m; int t=Dinic::t=s+1; long long ans=0; for(int i=0;i<m*n;i++) if (!v[i]) { if (sorce[i]>0) Dinic::addedge(s,i,sorce[i]),ans+=sorce[i]; 正点权的边 if (sorce[i]<0) Dinic::addedge(i,t,-sorce[i]); 负点权的边 for(int j=0;j<g[i].size();j++) if (!v[j]) Dinic::addedge(g[i][j],i,INF); 先决关系 } printf("%lld\n",ans-Dinic::dinic()); Dinic求最大流最小割，ans-最小割即为结果 } 这里我用了Dinic模板，时间大概只用的300MS+，然而改成之前自己写的普通宽搜增广路算法，时间一下就变成了2000MS+，果然Dinic大法好！