poj 3422 Kaka's Matrix Travels 费用流

题意:

给1个n*n的矩阵,每次从左上角走到右下角并取走其中的数,求走k次能取到的最大和。

分析:

费用流边的容量有限制的作用,费用有求和的作用,对每一个点只能取1次,容易想到把这个点拆成两个点并连上容量为1,费用为该点数的边。但明显有的流要“跳过”这个点,如何处理呢?可以加1条容量为无穷,费用为0的边,这样不参加这点费用计算的流就能够"跳过"这个点了。

代码:

//poj 3422
//sep9
#include <iostream>
#include <queue>
using namespace std;
const int maxN=10024;
const int maxM=20024;
struct Edge
{
int v,f,w,nxt;
}e[4*maxM+10];
int g[maxN+10];
int nume,src,sink;

queue<int> Q;
bool inq[maxN+10];
int dist[maxN+10];
int prev[maxN+10],pree[maxN+10];

void addedge(int u,int v,int c,int w)
{
e[++nume].v=v;e[nume].f=c;e[nume].w=w;e[nume].nxt=g[u];g[u]=nume;
e[++nume].v=u;e[nume].f=0;e[nume].w=-w;e[nume].nxt=g[v];g[v]=nume;
}

bool find_path()
{
while(!Q.empty()) Q.pop();
memset(dist,⑴,sizeof(dist));
memset(inq,false,sizeof(inq));
Q.push(src);
inq[src]=true;
dist[src]=0;
while(!Q.empty()){
int u=Q.front();Q.pop();
inq[u]=false;
for(int i=g[u];i;i=e[i].nxt){
if(e[i].f>0&&dist[u]+e[i].w>dist[e[i].v]){
dist[e[i].v]=dist[u]+e[i].w;
prev[e[i].v]=u;
pree[e[i].v]=i;
if(!inq[e[i].v]){
Q.push(e[i].v);
inq[e[i].v]=true;
}
}
}
}
return dist[sink]==⑴?false:true;
}

int max_cost_flow(int f)
{
int res=0;
while(f>0){
if(find_path()==false)
return ⑴;
int d=f;
for(int v=sink;v!=src;v=prev[v])
d=min(d,e[pree[v]].f);
f-=d;
res+=d*dist[sink];
for(int v=sink;v!=src;v=prev[v]){
e[pree[v]].f-=d;
e[pree[v]^1].f+=d;
}
}
return res;
}

void init()
{
memset(g,0,sizeof(g));
nume=1;
}

int main()
{
init();
int i,j,n,k;
scanf("%d%d",&n,&k);
src=2*n*n,sink=src+1;
for(i=0;i<n;++i)
for(j=0;j<n;++j){
int x;
scanf("%d",&x);
int u=i*n+j;
int v=u+n*n;
addedge(u,v,1,x);
addedge(u,v,INT_MAX,0);
if(i>0){
int t=(i⑴)*n+j+n*n;
addedge(t,u,INT_MAX,0);
}
if(j>0){
int t=i*n+(j⑴)+n*n;
addedge(t,u,INT_MAX,0);
}
}
addedge(src,0,k,0);
addedge(2*n*n⑴,sink,k,0);
printf("%d",max_cost_flow(k));
return 0;
}

波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

波比源码 » poj 3422 Kaka's Matrix Travels 费用流

发表评论

Hi, 如果你对这款模板有疑问,可以跟我联系哦!

联系站长
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡