[POJ 3422]K方格取数、费用流

【题目大意】一个人K次从左上角走到右下角（只能向下走或向右走），走过格子可以把上面的分数取掉，取掉以后该分数变为0，求走K次得到的最大分数。

【算法分析】典型的费用流，将每个格子拆点，连一条边费用为A[I,J]，容量为1，另外一条边费用为0，容量为INF，剩下的不用说了。

【其它】1A
6397386 edward2 3422 Accepted 1316K 63MS G++ 2008B 2010-02-01 18:35:54 水过留痕

【CODE】
#include #include #define N 100000
#define inf 0x7FFFFFFF
struct gtp{int x,y,next,op,c,w;}g[1000000];
int n,S,T,e,ls[N],fa[N],d[N],cost,list[N],v[N];

void addedge(int x,int y,int c,int w){
e++;
g[e].x=x; g[e].y=y; g[e].c=c; g[e].w=w; g[e].op=e+1;
g[e].next=ls[x]; ls[x]=e;
e++;
g[e].x=y; g[e].y=x; g[e].c=0; g[e].w=-w; g[e].op=e-1;
g[e].next=ls[y]; ls[y]=e;
}

int pos(int x,int y){
return (x-1)*n+y;
}

void init(){
int m;
scanf("%d%d",&n,&m);
S=0; T=n*n*2+1;
addedge(S,1,m,0);
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++){
int w;
scanf("%d",&w);
addedge(pos(i,j),pos(i,j)+n*n,1,w);
addedge(pos(i,j),pos(i,j)+n*n,inf,0);
if (i!=n) addedge(pos(i,j)+n*n,pos(i+1,j),inf,0);
if (j!=n) addedge(pos(i,j)+n*n,pos(i,j+1),inf,0);
}
addedge(n*n*2,T,inf,0);
}

bool spfa(){
for (int i=S;i<=T;i++){
d[i]=-1;
v[i]=0;
}
d[0]=0; list[0]=0; v[0]=1;
int head=-1,tail=0;
while (head!=tail){
head++; if (head>=N) head=0;
for (int t=ls[list[head]];t;t=g[t].next)
if (g[t].c && d[g[t].x]+g[t].w>d[g[t].y]){
d[g[t].y]=d[g[t].x]+g[t].w;
fa[g[t].y]=t;
if (!v[g[t].y]){
v[g[t].y]=1;
tail++; if (tail>=N) tail=0;
list[tail]=g[t].y;
}
}
v[list[head]]=0;
}
if (d[T]>-1) return true;
return false;
}

void change(){
cost+=d[T];
int nf=inf;
for (int i=T;i!=S;i=g[fa[i]].x)
if (g[fa[i]].c for (int i=T;i!=S;i=g[fa[i]].x){
g[fa[i]].c-=nf;
g[g[fa[i]].op].c+=nf;
}
}

void maxflow_mincost(){
cost=0;
while (spfa()) change();
}

int main(){
init();
maxflow_mincost();
printf("%dn",cost);
}