Description
Output
仅包含一个整数，表示可以获得的最大能源收入。注意，你也可以选择不进行任何攻击，这样能源收入为0。
3 2
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 。
想法
僵尸攻击\(P_{r,c}\)的植物的前提是已攻击所有可以保护这个植物的植物 明显是一个“最大权闭合图”问题，最小割解决。
需要特别判断的是这个图中不能有环，因为环中的植物互相保护，都不能被攻击。 除环外，所有可走到环的点也不能有，因为有了这些点闭合图中就必须有环。 所有要先dfs一遍把这些点都标出来。 跑dinic时注意不能走到这些点上。
代码
#include<cstdio>
#include<iostream>
#include<algorithm>
#define INF 200000000
using namespace std;
const int N = 605;
const int M = 605*605+605;
int read(){
char ch=getchar();
int x=0,f=1;
while((ch<'0' || ch>'9') && ch!='-') ch=getchar();
if(ch=='-') f=-1,ch=getchar();
while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
return f*x;
}
struct node{
int v,f;
node *next,*rev;
}pool[M<<1],*h[N];
int cnt;
void addedge(int u,int v,int f){
node *p=&pool[++cnt],*q=&pool[++cnt];
p->v=v;p->next=h[u];h[u]=p; p->f=f;p->rev=q;
q->v=u;q->next=h[v];h[v]=q; q->f=0;q->rev=p;
}
int n,m;
int C[25][35];
int vis[N],cir[N];
void findcir(int u){
int v;
vis[u]=1;
for(node *p=h[u];p;p=p->next)
if(p->f){
if(!vis[v=p->v]) {
findcir(v);
if(cir[v]) cir[u]=1;
}
else if(vis[v]==1) cir[u]=1;
else if(cir[v]) cir[u]=1;
}
vis[u]=2;
}
int S,T;
int level[N],que[N];
bool bfs(){
int head=0,tail=0,u,v;
for(int i=S;i<=T;i++) level[i]=-1;
level[S]=1; que[tail++]=S;
while(head<tail){
int u=que[head++];
for(node *p=h[u];p;p=p->next)
if(p->f && level[v=p->v]==-1 && !cir[v]){
level[v]=level[u]+1;
que[tail++]=v;
}
if(level[T]!=-1) return true;
}
return false;
}
int find(int u,int f){
int s=0,t,v;
if(u==T) return f;
for(node *p=h[u];p;p=p->next)
if(p->f && s<f && level[v=p->v]==level[u]+1 && !cir[v]){
t=find(v,min(p->f,f-s));
if(t){
s+=t;
p->f-=t;
p->rev->f+=t;
}
}
if(!s) level[u]=-1;
return s;
}
int dinic(){
int f=0;
while(bfs()) f+=find(S,INF);
return f;
}
int main()
{
int u,v,w;
n=read();m=read();
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
int t=(i-1)*m;
C[i][j]=read();w=read();
for(int k=0;k<w;k++){
u=read();v=read();
addedge(u*m+v+1,t+j,INF);
}
}
for(int i=1;i<=n;i++){
int t=(i-1)*m;
for(int j=m-1;j>0;j--)
addedge(t+j,t+j+1,INF);
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(vis[(i-1)*m+j]!=2)
findcir((i-1)*m+j);
S=0; T=n*m+1;
int sum=0;
for(int i=1;i<=n;i++){
int t=(i-1)*m;
for(int j=1;j<=m;j++){
if(cir[t+j]) continue;
if(C[i][j]>0) {
addedge(S,t+j,C[i][j]);
sum+=C[i][j];
}
else if(C[i][j]<0)
addedge(t+j,T,-C[i][j]);
}
}
sum-=dinic();
printf("%d\n",sum);
return 0;
}
转载于:https://www.cnblogs.com/lindalee/p/8414383.html
相关资源：数据结构—成绩单生成器
