1565: [NOI2009]植物大战僵尸
Time Limit: 10 Sec Memory Limit: 64 MB
Submit: 1972 Solved: 917
[Submit][Status][Discuss]
Description
Input
Output
仅包含一个整数，表示可以获得的最大能源收入。注意，你也可以选择不进行任何攻击，这样能源收入为0。
Sample Input
3 2
10 0
20 0
-10 0
-5 1 0 0
100 1 2 1
100 0
10 0
20 0
-10 0
-5 1 0 0
100 1 2 1
100 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 。
Source
Solution
一开始想到的是，在网格图上加限制然后搞搞，发现其实不对，因为能吃掉的植物和网格什么的无关，而是和植物们的攻击有关
很容易想到，如果一个植物被另一个植物保护，那么必须吃掉另一个植物，才能吃掉这个植物，所以，很显然顺序是需要考虑的，但又发现，如果多个植物可以互相保护（也就是连成环，很显然这些植物都是无敌的RMB玩家）
这种类型很容易就联想到最小割模型（最大权闭合子图），又因为环上植物无敌，所以不去考虑环上植物，那么把环上的扔掉即可
开始想写Tarjan，写完后发现不行，于是换拓扑排序，然后发现太久太久没写过了，竟然快忘了....
这里可以直接建网络流图,拓扑一遍,在增广的时候加限制即可.(不过需要一些特殊的技巧)
或者先对保护的点连边,拓扑一遍,然后再建新图跑网络流即可 值得注意的是:保护的点需要加上它左边的点(很显然僵尸不能跳过一个植物吃后面的)
Code
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
using namespace std;
int read()
{
int x=,f=; char ch=getchar();
while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}
while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}
return x*f;
}
#define maxn 1000
#define maxm 1000010
int n,m,total,score[maxn];
struct EdgeNode{int next,to,cap;}edge[maxm];
int head[maxn],cnt=;
void addedge(int u,int v,int w) {cnt++; edge[cnt].next=head[u]; head[u]=cnt; edge[cnt].to=v; edge[cnt].cap=w;}
void insertedge(int u,int v,int w) {addedge(u,v,w); addedge(v,u,);} struct RoadNode{int next,to;}road[maxm>>];
int last[maxn],tot;
void addroad(int u,int v) {tot++; road[tot].next=last[u]; last[u]=tot; road[tot].to=v;}
void insertroad(int u,int v) {addroad(u,v);}
bool visit[maxn]; int du[maxn],s,t;
void Paint(int now)
{
visit[now]=;
for (int i=last[now]; i; i=road[i].next)
if (!visit[road[i].to]) Paint(road[i].to);
}
void TopoSort()
{
s=,t=n*m;
stack<int>st;
for (int i=s; i<=t; i++) if (!du[i]) st.push(i); else visit[i]=;
while (!st.empty())
{
int now=st.top(); st.pop(); visit[now]=;
for (int i=last[now]; i; i=road[i].next)
{
du[road[i].to]--;
if (!du[road[i].to]) st.push(road[i].to);
}
//printf("%d\n",now);
}
for (int i=s; i<=t; i++) if (visit[i]) Paint(i);
}
int dis[maxn],cur[maxn],S,T;
#define inf 0x7fffffff
bool bfs()
{
queue<int>q;
for (int i=S; i<=T; i++) dis[i]=-;
q.push(S); dis[S]=;
while (!q.empty())
{
int now=q.front(); q.pop();
for (int i=head[now]; i; i=edge[i].next)
if (edge[i].cap && dis[edge[i].to]==-)
dis[edge[i].to]=dis[now]+,q.push(edge[i].to);
}
return dis[T]!=-;
}
int dfs(int loc,int low)
{
if (loc==T) return low;
int w,used=;
for (int i=cur[loc]; i; i=edge[i].next)
if (edge[i].cap && dis[edge[i].to]==dis[loc]+)
{
w=dfs(edge[i].to,min(low-used,edge[i].cap));
edge[i].cap-=w; edge[i^].cap+=w; used+=w;
if (used==low) return low; if (edge[i].cap) cur[loc]=i;
}
if (!used) dis[loc]=-;
return used;
}
int dinic()
{
int tmp=;
while (bfs())
{
for (int i=S; i<=T; i++) cur[i]=head[i];
tmp+=dfs(S,inf);
}
return tmp;
}
void Build()
{
S=,T=n*m+;
for (int i=; i<=n*m; i++)
if (!visit[i])
{
if (score[i]>) insertedge(i,T,score[i]); else insertedge(S,i,-score[i]);
for (int j=last[i]; j; j=road[j].next)
if (!visit[road[j].to]) insertedge(i,road[j].to,inf);
total+=score[i]>?score[i]:;
}
}
int locate(int x,int y) {return (x-)*m+y;}
int main()
{
n=read(),m=read();
for (int i=; i<=n; i++)
for (int j=; j<=m; j++)
{
int now=locate(i,j),num;
score[now]=read(); num=read();
for (int x,y,k=; k<=num; k++)
x=read()+,y=read()+,insertroad(now,locate(x,y)),du[locate(x,y)]++;
if (j>) insertroad(now,locate(i,j-)),du[locate(i,j-)]++;
}
TopoSort();
Build();
int maxflow=dinic();// printf("%d %d\n",total,maxflow);
printf("%d\n",total-maxflow);
return ;
}
一写这种需要重构图的,用上road啊last,tot啊什么的,总会莫名其妙的写混...还要肉眼对拍浪费时间