【BZOJ 1565】 [NOI2009]植物大战僵尸

1565: [NOI2009]植物大战僵尸Time Limit:10 SecMemory Limit:64 MBSubmit:1488Solved:707[Submit][Status][Discuss]Description

Input

Output

仅包含一个整数，表示可以获得的最大能源收入。注意，你也可以选择不进行任何攻击，这样能源收入为0。

Sample Input

3 210 020 0-10 0-5 1 0 0100 1 2 1100 0

Sample Output

25

HINT

在样例中, 植物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 。

最大权闭合图转化为网络流模型。

闭合子图：

V中顶点的所有出边均指向V内部顶点

而这道题吃到某个植物a可能需要先吃掉别的植物b（在他的右边或者保护着他），那么我们把a连向b。

发现符合题意的图就是最大权闭合图~

那么按照最大权闭合图的建图方法：

1.s向正权点连流量为权值的边

2.负权点向t连流量为权值的绝对值的边

3.有边相连的两点连流量为inf的边

答案就是正权点的权值总和减去最小割。

#include <iostream>#include <algorithm>#include <cstring>#include <cstdio>#include <cstdlib>#include <queue>#define inf 0x3f3f3f3f#define M 1000using namespace std;int now,tot,s,t,va[M],du[M],H[M],h[M],ok[M],d[M],v[M],cur[M];int n,m;queue<int> q;struct edge1{int x,y,ne;}e[500000];struct edge{int from,to,cap,flow,ne;}E[500000];int C(int x,int y){return (x-1)*m+y;}void Add(int x,int y){e[++tot].y=y;e[tot].x=x;e[tot].ne=H[x];H[x]=tot;du[y]++;}void Addedge(int from,int to,int cap){E[++tot]=(edge){from,to,cap,0,h[from]};h[from]=tot;E[++tot]=(edge){to,from,0,0,h[to]};h[to]=tot;}bool bfs(){for (int i=s;i<=t;i++)v[i]=0;v[s]=1;d[s]=0;q.push(s);while (!q.empty()){int x=q.front();q.pop();for (int i=h[x];i;i=E[i].ne){edge e=E[i];if (!v[e.to]&&e.cap>e.flow){v[e.to]=1;d[e.to]=d[x]+1;q.push(e.to);}}}return v[t];}int dfs(int x,int a){if (x==t||!a) return a;int flow=0;for (int &i=cur[x];i;i=E[i].ne){edge &e=E[i];if (d[e.to]!=d[x]+1) continue;int f=dfs(e.to,min(a,e.cap-e.flow));if (f){flow+=f;a-=f;e.flow+=f;E[i^1].flow-=f;if (!a) break;}}return flow;}int dinic(){int flow=0;while (bfs()){for (int i=s;i<=t;i++)cur[i]=h[i];flow+=dfs(s,inf);}return flow;}void Topsort(){queue<int> q;for (int i=1;i<=now;i++)if (!du[i]) ok[i]=1,q.push(i);while (!q.empty()){int x=q.front();q.pop();for (int i=H[x];i;i=e[i].ne){int y=e[i].y;du[y]–;if (!du[y]){ok[y]=1;q.push(y);}}}}int main(){scanf("%d%d",&n,&m);for (int i=1;i<=n;i++)for (int j=1;j<=m;j++){now++;int w;scanf("%d%d",&va[now],&w);for (int k=1;k<=w;k++){int x,y;scanf("%d%d",&x,&y);x++,y++;Add(now,C(x,y));}if (j!=m) Add(now+1,now);}Topsort();s=0,t=now+1;int ans=0;tot=1;for (int x=1;x<=now;x++)if (ok[x]){if (va[x]>0) ans+=va[x],Addedge(s,x,va[x]);else Addedge(x,t,-va[x]);for (int i=H[x];i;i=e[i].ne){int y=e[i].y;if (ok[y])Addedge(y,x,inf);}}cout<<ans-dinic()<<endl;return 0;}

感悟：

1.WA是因为E数组开小

2.突然明白最大权闭合图的答案为什么是正权和-最小割了:

对于每个正权点，如果他通过inf的边连着负权点，代表要得到这个正权必须付出负权点的代价，否则就不能得到正权；

而最小割中因为s-正权点-负权点-t构成一条通路，这条路中必须割掉s-正权点的边或者负权点-t的边，，割掉前者表示不要这个正权点了，割掉后者表示付出了负权点的代价然后得到正权~

德有多高，艺有多深。