[NOI2009]植物大战僵尸 【拓扑排序】【最大权闭合图】【网络流】

【题目链接】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1565
【算法分析】
恩，就是比较裸的最大权闭合图，但是要知道如果形成环的话，网络流是处理不了的。
于是拓扑排序去环，然后最大权闭合图。
【其它】
今天见到NOI2009那里居然有一题未A= =，于是写一个练练手。
1Y。
NOI2009里的送分题。
【CODE】
#include #include const int N=1000;
const int E=1005555;
struct edge{int x,y,c;edge *next,*op;};
struct Node{int x,y;Node *next;};
struct Lint_t{
Node *ls[N],g[E];
int e;
void addedge(int x,int y){
g[++e].x=x; g[e].y=y; g[e].next=ls[x]; ls[x]=&g[e];
}
}Link;
struct Network_t{
int Flow,e,S,T;
edge *ls[N],*fa[N],*cur[N],g[E];
int num[N],d[N];
void addedge(int x,int y,int c){
g[++e].x=x; g[e].y=y; g[e].c=c; g[e].next=ls[x]; ls[x]=&g[e]; g[e].op=&g[e+1];
g[++e].x=y; g[e].y=x; g[e].c=0; g[e].next=ls[y]; ls[y]=&g[e]; g[e].op=&g[e-1];
}

void relabel(int k){
cur[k]=ls[k];
int mm=T;
for (edge *t=ls[k];t;t=t->next)
if (t->c && d[t->y] mm=d[t->y];
d[k]=mm+1;
}

void change(){
int nf=0x7FFFFFFF;
for (int i=T;i!=S;i=fa[i]->x)
if (fa[i]->c for (int i=T;i!=S;i=fa[i]->x){
fa[i]->c-=nf;
fa[i]->op->c+=nf;
}
Flow+=nf;
}

void sap(){
int i;
Flow=0;
for (i=S;i<=T;i++) {
num[i]=0;
d[i]=0;
cur[i]=ls[i];
}
i=S;
while (d[S]<=T){
edge *&t=cur[i];
for (;t;t=t->next)
if (t->c && d[t->y]+1==d[t->x]) break;
if (t){
fa[t->y]=t;
i=t->y;
if (i==T){
change();
i=S;
}
}
else{
if (! –num[d[i]]) break;
relabel(i);
++num[d[i]];
if (i!=S) i=fa[i]->x;
}
}
}
}Network;

int n,m,Sum;
int W[N],pos[50][50],L[N],du[N],v[N];

void init(){
scanf("%d%d",&m,&n);
int cnt=0,i,j,k,x,y;
for (i=1;i<=m;i++)
for (j=1;j<=n;j++)
pos[i][j]=++cnt;
for (i=1;i<=m;i++)
for (j=1;j<=n;j++){
scanf("%d%d",&W[pos[i][j]],&cnt);
for (k=0;k scanf("%d%d",&x,&y);
x++; y++;
Link.addedge(pos[i][j],pos[x][y]);
du[pos[x][y]]++;
}
if (j>1){
Link.addedge(pos[i][j],pos[i][j-1]);
du[pos[i][j-1]]++;
}
}
}

void topsort(){
int head=0,tail=0,i;
n*=m;
for (i=1;i<=n;i++)
if (!du[i]) L[++tail]=i;
while (head!=tail){
head++;
for (Node *t=Link.ls[L[head]];t;t=t->next){
du[t->y]–;
if (!du[t->y]) L[++tail]=t->y;
}
}
memset(v,0,sizeof(v));
for (int i=1;i<=tail;i++)
v[L[i]]=1;
}

void build(){
Network.S=0; Network.T=n+1;
Sum=0;
for (int i=1;i<=n;i++) if (v[i]){
for (Node *t=Link.ls[i];t;t=t->next)
if (v[t->y])
Network.addedge(t->y,i,0x7FFFFFFF);
if (W[i]>0){
Network.addedge(0,i,W[i]);
Sum+=W[i];
}
else Network.addedge(i,n+1,-W[i]);
}
}

int main(){
Link.e=Network.e=0;
memset(Link.ls,0,sizeof(Link.ls));
memset(Network.ls,0,sizeof(Network.ls));
init();
topsort();
build();
Network.sap();
printf("%dn",Sum-Network.Flow);
}