本文主要是介绍poj 3422(拆点费用流)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：有个方阵，每个格子里都有一个非负数，从左上角走到右下角，每次走一步，只能往右或往下走，经过的数字拿走
每次都找可以拿到数字和最大的路径走，走k次，求最大和
如下图拆点 ，
#include<cstdio>
#include<cstring>
#include<map>
#include<vector>
#include<cmath>
#include<cstdlib>
#include<stack>
#include<queue>
#include <iomanip>
#include<iostream>
#include<algorithm>
using namespace std ;
const int N= 6000 ;
const int M= N*5 ;
const int inf = 1<< 30 ;
struct node
{int u ,v,c,cost,next ;
}edge[M] ;
int head[N],pp[N],pre[N],vist[N],dist[N] ;
int top ;
int g[100][100];void add(int u ,int v,int c,int cost)
{ edge[top].u=u; edge[top].v=v; edge[top].c=c; edge[top].cost=cost; edge[top].next=head[u]; head[u]=top++; edge[top].u=v; edge[top].v=u; edge[top].c=0; edge[top].cost=-cost; edge[top].next=head[v]; head[v]=top++;
} int SPFA(int s,int t)
{ int u , v ; memset(vist,0,sizeof(vist)); memset(pre,-1,sizeof(pre)); for(int i = 0 ; i <= t ; i++) dist[i]=inf ; vist[s]=1;dist[s]=0;pre[s]=s; queue<int>q; q.push(s); while(!q.empty()) { u=q.front(); q.pop(); vist[u]=0; for(int i =head[u];i!=-1;i=edge[i].next) { v=edge[i].v; if(edge[i].c && dist[v] > dist[u]+edge[i].cost) { dist[v] = dist[u]+edge[i].cost ; pre[v]=u; pp[v]=i; if(!vist[v]); { vist[v]=1; q.push(v); } } } } if(dist[t]==inf) return 0; return 1 ;
} int MFMC(int s,int t)
{ int mincost=0,flow=0,minflow ; while(SPFA(s,t)) { minflow=inf; for(int i=t;i!=s;i=pre[i]) minflow=min(minflow,edge[pp[i]].c); for(int i=t;i!=s;i=pre[i]) { edge[pp[i]].c -= minflow; edge[pp[i]^1].c += minflow; } flow += minflow; mincost += dist[t]*minflow ; // printf("****"); } return -mincost ;
} int main()
{int n,k ;while(~scanf("%d%d",&n,&k)){top = 0 ; memset(head,-1,sizeof(head)) ;memset(g,0,sizeof(g)) ;int s = 0 ,t = n*n*2+1 ;for(int i = 1 ; i <= n ; i++)for(int j = 1 ; j <= n ; j++){int tmp = (i-1)*n+j ;scanf("%d",&g[i][j]) ;add(tmp,tmp+n*n,1,-g[i][j]) ;add(tmp,tmp+n*n,k-1,0) ; }for(int i = 1 ; i <= n ; i++)for(int j = 1 ; j <= n ; j++){int tmp = (i-1)*n+j ;int a = (i-1)*n+j+1 ;int b= i*n+j ; if(j<n)add(tmp+n*n,a,k,0);if(i<n)add(tmp+n*n,b,k,0); } add(s,1,k,0);add(n*n*2,t,k,0);int ans = MFMC(s,t);printf("%d\n",ans); }return 0 ;
}这篇关于poj 3422(拆点费用流)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
