首页 > 代码库 > hdu4862 2014多校B题/ 费用流(最优情况下用不大于K条路径覆盖)(不同的解法)
hdu4862 2014多校B题/ 费用流(最优情况下用不大于K条路径覆盖)(不同的解法)
题意: 一个数字矩阵,可以出发K次,每次可以从右边或者下面走,要求(在收益最大情况下)覆盖全图,不能则输出-1。(规则:每次跳一步的时候若格子数字相等则获得该数字的能量,每跳一步消耗距离的能量)。每个格子走且仅能走一次。
选<=K条路径,最优情况来覆盖全图。
显然用拆点为二分图。
一种解法:边(流量,费用)
源点向X部连边(1,0)Y部向汇点连边(1,0)X到Y,若能到,则有边(1,消耗-获得)。关键点(解决每个点都覆盖,恰好起到填补的作用):在X部最上面添加一个点,源点连之(k,0)它向所有Y点连边(1,0)。跑最小费用最大流即可。
第二种:(感想zz1215提供的建图思路)
源点向X部连边(1,0)Y部向汇点连边(1,0),Y到X,若能到,则有边(1,消耗-获得)(注意这里是回流),每个点I-->I`有边(1,-w_inf),这里的w_inf为相对大数,只要保证该费用较“小”即可(相对其他费用,他是最廉价的,这样必优先流这条边。添加超级源点,向源点连边(K,0)。增广K次中,若一直增大,则取最大,否则到开始下降的时候要BREAK。(先曾后减的)。
PS:开始时候因为定位编号搞错有没有!编号(i,j)=i*m+j,而不是i*n+j!!!
图:
代码:
#include<iostream> //24ms #include<cstdio> #include<algorithm> #include<queue> #include<string> using namespace std; int n,m,k; const int inf=0x3f3f3f3f; int a[25][25]; int head[500];int e[10000][4];int nume=0; void inline adde(int i,int j,int c,int w) { e[nume][0]=j;e[nume][1]=head[i];head[i]=nume; e[nume][2]=c;e[nume++][3]=w; e[nume][0]=i;e[nume][1]=head[j];head[j]=nume; e[nume][2]=0;e[nume++][3]=-w; } int inq[500];int d[500]; bool spfa(int &sumcost) { for(int i=0;i<=2*n*m+3;i++) { inq[i]=0;d[i]=inf; } int minf=inf; queue<int>q; int prv[300];int pre[300]; q.push(2*n*m+2); inq[2*n*m+2]=1; d[2*n*m+2]=0; while(!q.empty()) { int cur=q.front(); q.pop();inq[cur]=0; for(int i=head[cur];i!=-1;i=e[i][1]) { int v=e[i][0]; if(e[i][2]>0&&d[v]>e[i][3]+d[cur]) { d[v]=e[i][3]+d[cur]; prv[v]=cur; pre[v]=i; if(!inq[v]) { q.push(v); inq[v]=1; } } } } if(d[2*n*m+1]==inf)return 0; int cur=2*n*m+1; while(cur!=2*n*m+2) { minf=min(minf,e[pre[cur]][2]); cur=prv[cur]; } cur=2*n*m+1; while(cur!=2*n*m+2) { e[pre[cur]][2]-=minf;e[pre[cur]^1][2]+=minf; cur=prv[cur]; } sumcost+=d[2*n*m+1]*minf; return 1; } int mincost() { int sum=0; while(spfa(sum)); return sum; } void init() { nume=0; for(int i=0;i<=2*n*m+3;i++) { head[i]=-1; } } int main() { int T; scanf("%d",&T); for(int iii=1;iii<=T;iii++) { scanf("%d%d%d",&n,&m,&k); init(); string s; for(int i=0;i<n;i++) { cin>>s; for(int j=0;j<m;j++) { a[i][j]=s[j]-'0'; } } printf("Case %d : ",iii); if(min(n,m)>k) { printf("-1\n");continue; } for(int i=0;i<n;i++) //起点2*n*m+2,终点2*n*m+1 for(int j=0;j<m;j++) { for(int ii=i+1;ii<n;ii++) { int temp=(a[i][j]==a[ii][j]?a[i][j]:0); adde(m*i+j,m*ii+j+n*m+1,1,ii-i-1-temp); } for(int jj=j+1;jj<m;jj++) { int temp=(a[i][j]==a[i][jj]?a[i][j]:0); adde(m*i+j,m*i+jj+n*m+1,1,jj-j-1-temp); } } for(int i=0;i<n*m;i++) adde(2*n*m+2,i,1,0); adde(2*n*m+2,n*m,k,0); for(int i=n*m+1;i<=2*n*m;i++) { adde(n*m,i,1,0); adde(i,2*n*m+1,1,0); } /* for(int i=0;i<=2*n*m+2;i++) for(int j=head[i];j!=-1;j=e[j][1]) printf("%d->%d:c:%d,w:%d\n",i,e[j][0],e[j][2],e[j][3]);*/ printf("%d\n",-mincost()); } return 0; }
方法二:
#include<iostream> //31ms #include<cstdio> #include<queue> #include<string> using namespace std; int n,m,k; const int inf=0x3f3f3f3f; const int winf=100000; int a[25][25]; int head[500];int e[20001][4];int nume=0; void inline adde(int i,int j,int c,int w) { e[nume][0]=j;e[nume][1]=head[i];head[i]=nume; e[nume][2]=c;e[nume++][3]=w; e[nume][0]=i;e[nume][1]=head[j];head[j]=nume; e[nume][2]=0;e[nume++][3]=-w; } int inq[500];int d[500]; bool spfa(long long &sumcost) { for(int i=0;i<=2*n*m+3;i++) { inq[i]=0;d[i]=inf; } int prv[500];int pre[500]; int minf=inf; queue<int>q; q.push(n*m); inq[n*m]=1; d[n*m]=0; while(!q.empty()) { int cur=q.front(); q.pop(); inq[cur]=0; for(int i=head[cur];i!=-1;i=e[i][1]) { int v=e[i][0]; if(e[i][2]>0&&d[v]>e[i][3]+d[cur]) { d[v]=e[i][3]+d[cur]; prv[v]=cur; pre[v]=i; if(!inq[v]) { q.push(v); inq[v]=1; } } } } if(d[2*n*m+1]==inf)return 0; int cur=2*n*m+1; while(cur!=n*m) { minf=min(minf,e[pre[cur]][2]); cur=prv[cur]; } cur=2*n*m+1; while(cur!=n*m) { e[pre[cur]][2]-=minf; e[pre[cur]^1][2]+=minf; cur=prv[cur]; } sumcost+=d[2*n*m+1]*(long long)minf; return 1; } long long mincost() { long long sum=0; long long lastsum=0; while(spfa(sum)) //变小的时候跳出 { if(lastsum>=-sum){return -lastsum;} lastsum=-sum; } return sum; } void init() { nume=0; for(int i=0;i<=2*n*m+3;i++) { head[i]=-1; } } int main() { int T; scanf("%d",&T); for(int iii=1;iii<=T;iii++) { scanf("%d%d%d",&n,&m,&k); init(); string s; for(int i=0;i<n;i++) { cin>>s; for(int j=0;j<m;j++) { a[i][j]=s[j]-'0'; } } printf("Case %d : ",iii); if(min(n,m)>k) { printf("-1\n");continue; } for(int i=0;i<n;i++) //起点n*m,终点:2*n*m+1 for(int j=0;j<m;j++) { for(int ii=i+1;ii<n;ii++) { int temp=(a[i][j]==a[ii][j]?a[i][j]:0); adde(m*i+j+n*m+1,m*ii+j,1,ii-i-1-temp); } for(int jj=j+1;jj<m;jj++) { int temp=(a[i][j]==a[i][jj]?a[i][j]:0); adde(m*i+j+n*m+1,m*i+jj,1,jj-j-1-temp); } } for(int i=0;i<n*m;i++) adde(2*n*m+2,i,1,0); adde(n*m,n*m*2+2,k,0); for(int i=n*m+1;i<=2*n*m;i++) { adde(i-n*m-1,i,1,-winf); adde(i,2*n*m+1,1,0); } /* for(int i=0;i<=2*n*m+2;i++) for(int j=head[i];j!=-1;j=e[j][1]) printf("%d->%d:c:%d,w:%d\n",i,e[j][0],e[j][2],e[j][3]);*/ cout<<-mincost()-n*m*winf<<endl; } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。