poj 3422 Kaka's Matrix Travels (最小费用最大流模板)

题目链接: poj 3422

题目大意: 给出NxN的数字矩阵，左上角走到右下角(只能向右或向下走)，sum记录走过点值的和

走过的点值置为0，问走K次，求sum的最大值

解题思路: 开始想到的是K次最长路，结果WA了

因为每次走最长路会导致下次走的时候不是最优解

建立费用流模型，把每个顶点T，分成两个顶点T和T''

因为要限制每个顶点的值只加一次，T->T''容量为1，费用为T的值：

1.建立超级源点，源点指向顶点T1，容量为K，费用0

2.建立超级汇点，顶点T(2*n)指向汇点，容量为K，费用为0

3.每个顶点拆分为两个点，加两条边 (Ti指向Ti''，容量为1，费用为T的值)

(Ti指向Ti''，容量为K，费用为0)

4.若能从T1走到T2，则T1''连T2，容量为K，费用为0

然后求一次最小费用最大流就是最终结果

代码:

#include 
  
   
#include 
   
     #include 
    
      #define MAX 5100 #define INF 0x3f3f3f3f #define Min(a,b) (a
     
      是最小费用流 { dis[v2]=dis[v1]+Edge[i].w; path[v2]=v1,Fi[v2]=i; if(!vis[v2]) { vis[v2]=1; que[s++]=v2; } } } } if(dis[E]==INF) return false; return true; } int Find() { int i,sum=0,MIN=INF; for(i=E;i!=-1;i=path[i]) { if(path[i]!=-1) MIN=Min(MIN,Edge[Fi[i]].c); } for(i=E;i!=-1;i=path[i]) { if(path[i]!=-1) { Edge[Fi[i]].c-=MIN; Edge[Edge[Fi[i]].r].c+=MIN; sum=sum+(Edge[Fi[i]].w*MIN); } } return sum; } int Solve() { int sum=0; while(BFS()) sum+=Find(); return sum; } int main() { int i,j,n,k,a,b,c,d,num[53][53]; while(scanf("%d%d",&n,&k)!=EOF) { Index=0; memset(pre,-1,sizeof(pre)); for(i=1;i<=n;i++) for(j=1;j<=n;j++) scanf("%d",&num[i][j]); S=0,E=n*n*2+1; Add_edge(S,1,k,0); //左边 Add_edge(E-1,E,k,0); //右边 int v1,v2,j1,x,y; for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { v1=(i-1)*n+j; Add_edge(v1*2-1,v1*2,1,num[i][j]); //分点边1 Add_edge(v1*2-1,v1*2,k,0); //分点边2 for(j1=0;j1<2;j1++) { x=i+Fx[j1][0],y=j+Fx[j1][1]; if(x>=1&&x<=n&&y>=1&&y<=n) { v2=(x-1)*n+y; Add_edge(v1*2,v2*2-1,k,0); //各点间 } } } } printf("%d\n",Solve()); } return 0; }

poj 3422 Kaka's Matrix Travels (最小费用最大流 模板)