首页 > 代码库 > HDU 4862
HDU 4862
http://acm.hdu.edu.cn/showproblem.php?pid=4862
#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <queue>using namespace std ;const int INF=0xfffffff ;struct node{ int s,t,cap,cost,nxt ;}e[200005] ;int sumflow ;int cnt,head[1005],vis[1005],dis[1005],pre[1005] ;void add(int s,int t,int cap,int cost){ e[cnt].s=s ;e[cnt].t=t ;e[cnt].cap=cap ;e[cnt].cost=cost ;e[cnt].nxt=head[s] ;head[s]=cnt++ ; e[cnt].s=t ;e[cnt].t=s ;e[cnt].cap=0 ;e[cnt].cost=-cost ;e[cnt].nxt=head[t] ;head[t]=cnt++ ;}int spfa(int s,int t,int N){ for(int i=0 ;i<=N ;i++) dis[i]=INF ; dis[s]=0 ; memset(vis,0,sizeof(vis)) ; memset(pre,-1,sizeof(pre)) ; vis[s]=1 ; queue <int> q ; q.push(s) ; while(!q.empty()) { int u=q.front() ; q.pop() ; vis[u]=0 ; for(int i=head[u] ;i!=-1 ;i=e[i].nxt) { int tt=e[i].t ; if(e[i].cap && dis[tt]>dis[u]+e[i].cost) { dis[tt]=dis[u]+e[i].cost ; pre[tt]=i ; if(!vis[tt]) { vis[tt]=1 ; q.push(tt) ; } } } } if(dis[t]==INF)return 0 ; return 1 ;}int mincost ;int MCMF(int s,int t,int N){ int flow,minflow ; mincost=flow=0 ; while(spfa(s,t,N)) { minflow=INF ; for(int i=pre[t] ;i!=-1 ;i=pre[e[i].s]) minflow=min(minflow,e[i].cap) ; flow+=minflow ; for(int i=pre[t] ;i!=-1 ;i=pre[e[i].s]) { e[i].cap-=minflow ; e[i^1].cap+=minflow ; } mincost+=dis[t]*minflow ; } sumflow=flow ;//最大流 return sumflow ;}char g[15][15] ;int gm[15][15] ;int main(){ int T ; scanf("%d",&T) ; for(int cas=1 ;cas<=T ;cas++) { cnt=0 ; memset(head,-1,sizeof(head)) ; int N,M,K ; scanf("%d%d%d",&N,&M,&K) ; for(int i=0 ;i<N ;i++) scanf("%s",g[i]) ; int S,T,V ; S=0 ;T=2*N*M+1 ;V=T+1 ; add(S,V,K,0) ; for(int i=1 ;i<=N*M ;i++) { add(S,i,1,0) ; add(i+N*M,T,1,0) ; add(V,i+N*M,1,0) ; } int ct=1 ; for(int i=0 ;i<N ;i++) { for(int j=0 ;j<M ;j++) { gm[i][j]=ct++ ; } } for(int i=0 ;i<N ;i++) { for(int j=0 ;j<M ;j++) { for(int k=j+1 ;k<M ;k++) { if(g[i][j]==g[i][k]) { add(gm[i][j],gm[i][k]+N*M,1,-(g[i][j]-‘0‘-(k-j-1))) ; } else { add(gm[i][j],gm[i][k]+N*M,1,k-j-1) ; } } for(int k=i+1 ;k<N ;k++) { if(g[i][j]==g[k][j]) { add(gm[i][j],gm[k][j]+N*M,1,-(g[i][j]-‘0‘-(k-i-1))) ; } else { add(gm[i][j],gm[k][j]+N*M,1,k-i-1) ; } } } } printf("Case %d : ",cas) ; if(MCMF(S,T,2*N*M+3)==N*M) printf("%d\n",-mincost) ; else puts("-1") ; } return 0 ;}
最小k路径覆盖模型,解法是建二分图求最优匹配
建图如下,重点是V点的建立,这个点和S点连容量k费用0的边和拆的另一半点连容量1费用0的边,可以保证小于等于k次完成(每次匹配一定要消耗S-V的一个单位流量,因为如果不消耗匹配不会停止,这是这个模型建图的最精髓之处),别的点就是正常的费用流求二分图最优匹配的建图方法,最后看求出的最大流是否等于N*M,等于证明有解
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。