首页 > 代码库 > HDU 4862 Jump
HDU 4862 Jump
题意:
n*m的格子 每个格子有个数字 你可以任选起点 每一步向下或者向右 每一步的花费是曼哈顿距离-1 如果一步的两端的格子数字一样那么你会得到这个数字的花费 问 最多选k次起点 在遍历完所有格子前提下最多剩下多少花费
思路:
题目可以表示为用最多k条路径去覆盖n*m 思路就转向了二分图
X集合表示每个点的出 Y集合表示入 如果f格子能走到g格子 那么建边gx->fy流量为1费用为花费减得到
那么如何满足至多k个起点呢?
加入一个虚点 从这个点向所有Y集合连边流量1费用0
那么这个点可以认为是超级起点 从他开始走向真正起点的入
最后从源点S向所有X点连边流量1费用0 向虚点连边流量k费用0 从所有Y点向汇点T连边流量1费用0
这时最小费用流所得的费用的相反数即为剩下的花费 流即表示经过的点数
代码:
#include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; #define M 200 #define inf ((1U<<31)-1) int t,cas,n,m,p,ansflow,ans,tot,S,T; int head[M],pre[M],vis[M],dis[M],maz[M][M]; struct edge { int u,v,w,c,next; }ed[M*M]; queue<int> qu; void add(int U,int V,int W,int C) { ed[tot].u=U; ed[tot].v=V; ed[tot].w=W; ed[tot].c=C; ed[tot].next=head[U]; head[U]=tot++; } int spfa() { int i,u,v; while(!qu.empty()) qu.pop(); for(i=0;i<M;i++) { vis[i]=0; dis[i]=inf; pre[i]=-1; } qu.push(S); vis[S]=1; dis[S]=0; while(!qu.empty()) { u=qu.front(); qu.pop(); vis[u]=0; for(i=head[u];~i;i=ed[i].next) { if(!ed[i].w) continue; v=ed[i].v; if(dis[v]>dis[u]+ed[i].c) { dis[v]=dis[u]+ed[i].c; pre[v]=i; if(!vis[v]) { vis[v]=1; qu.push(v); } } } } return dis[T]!=inf; } int mcmf() { int i,res=0,flow=0,tmp; while(spfa()) { tmp=inf; for(i=pre[T];~i;i=pre[ed[i].u]) { if(tmp>ed[i].w) tmp=ed[i].w; } for(i=pre[T];~i;i=pre[ed[i].u]) { ed[i].w-=tmp; ed[i^1].w+=tmp; res+=ed[i].c; } flow+=tmp; } ansflow=flow; return res; } int main() { int i,j,k,cost; char input[110]; scanf("%d",&t); while(t--) { printf("Case %d : ",++cas); scanf("%d%d%d",&n,&m,&p); for(i=1;i<=n;i++) { scanf("%s",input+1); for(j=1;j<=m;j++) maz[i][j]=input[j]-'0'; } S=0; T=n*m*2+2; memset(head,-1,sizeof(head)); tot=0; add(S,n*m*2+1,p,0); add(n*m*2+1,S,0,0); for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { add(S,(i-1)*m+j,1,0); add((i-1)*m+j,S,0,0); add(n*m+(i-1)*m+j,T,1,0); add(T,n*m+(i-1)*m+j,0,0); add(n*m*2+1,n*m+(i-1)*m+j,1,0); add(n*m+(i-1)*m+j,n*m*2+1,0,0); for(k=j+1;k<=m;k++) { cost=k-j-1; if(maz[i][j]==maz[i][k]) cost-=maz[i][j]; add((i-1)*m+j,n*m+(i-1)*m+k,1,cost); add(n*m+(i-1)*m+k,(i-1)*m+j,0,-cost); } for(k=i+1;k<=n;k++) { cost=k-i-1; if(maz[i][j]==maz[k][j]) cost-=maz[i][j]; add((i-1)*m+j,n*m+(k-1)*m+j,1,cost); add(n*m+(k-1)*m+j,(i-1)*m+j,0,-cost); } } } ans=mcmf(); if(n*m==ansflow) printf("%d\n",-ans); else puts("-1"); } return 0; }
HDU 4862 Jump
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。