首页 > 代码库 > 【poj3422】 Kaka's Matrix Travels
【poj3422】 Kaka's Matrix Travels
http://poj.org/problem?id=3422 (题目链接)
题意
N*N的方格,每个格子中有一个数,寻找从(1,1)走到(N,N)的K条路径,使得取到的数的和最大。
Solution
同【codevs1277】 方格取数
代码
// poj3422#include<algorithm>#include<iostream>#include<cstring>#include<cstdlib>#include<cstdio>#include<cmath>#include<queue>#define LL long long#define inf 2147483640#define Pi acos(-1.0)#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);using namespace std; const int maxn=100010;struct edge {int from,to,next,c,w;}e[maxn<<1];int head[maxn],dis[maxn],vis[maxn],f[maxn],p[maxn];int cnt=1,n,m,es,et,K; void link(int u,int v,int c,int w) { e[++cnt]=(edge){u,v,head[u],c,w};head[u]=cnt; e[++cnt]=(edge){v,u,head[v],-c,0};head[v]=cnt;}int SPFA() { queue<int> q; memset(dis,-1,sizeof(dis)); q.push(es);dis[es]=0;f[es]=inf; while (!q.empty()) { int x=q.front();q.pop(); vis[x]=0; for (int i=head[x];i;i=e[i].next) if (e[i].w && dis[e[i].to]<dis[x]+e[i].c) { dis[e[i].to]=dis[x]+e[i].c; f[e[i].to]=min(f[x],e[i].w); p[e[i].to]=i; if (!vis[e[i].to]) q.push(e[i].to),vis[e[i].to]=1; } } if (dis[et]==-1) return 0; for (int i=p[et];i;i=p[e[i].from]) e[i].w-=f[et],e[i^1].w+=f[et]; return f[et]*dis[et];}int EK() { int ans=0; for (int i=1;i<=K;i++) ans+=SPFA(); return ans;} int main() { scanf("%d%d",&n,&K); es=n*n+1;et=n*n+2; for (int i=1;i<=n;i++) for (int x,y,w,j=1;j<=n;j++) { scanf("%d",&w); x=(i-1)*n+j;y=x+n*n+2; link(x,y,w,1);link(x,y,0,inf); if (i<n) link(y,x+n,0,inf); if (j<n) link(y,x+1,0,inf); } link(es,1,0,inf);link(n*n+n*n+2,et,0,inf); printf("%d",EK()); return 0;}
【poj3422】 Kaka's Matrix Travels
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。