好贷网好贷款

HDOJ 2448 - Mining Station on the Sea 构图最小费用最大流..阅读理解..

发布时间:2016-12-4 3:50:41 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"HDOJ 2448 - Mining Station on the Sea 构图最小费用最大流..阅读理解..",主要涉及到HDOJ 2448 - Mining Station on the Sea 构图最小费用最大流..阅读理解..方面的内容,对于HDOJ 2448 - Mining Station on the Sea 构图最小费用最大流..阅读理解..感兴趣的同学可以参考一下。

                  题意:                           有M个station..有N个port以及N个船...现在每艘船都在某些station上..它们要回到port...保证存在可行方案..现在给出某个station存在航道的距离..以及某些port和stadion间的航道的距离...边是双向的..但一艘船进入了某个port就不能出来了...问所有的船都进入port的最小总距离...                   题解:                          提议描述具有迷惑性...虽然边是双向边..但是限制了进入port就不能出来..那么实际上station到port的边都是单向的...                          根据输入的关系..先入读初始的两两点间距离后跑Floyd得出两两间的最短距离..然后对网络流的图构边.超级源点向所有的station做边..容量为其船的数量费用为0..所有的port向超级汇点做边..容量为1费用为0...然后所有的station向所有Floyd后可达的port做边..容量为1,费用为其Floyd后的距离...然后跑最小费用最大流...最小费用就是答案..                          当然.. 本题也可以用KM搞~一回事.. Program: #include<iostream> #include<algorithm> #include<stdio.h> #include<string.h> #include<math.h> #include<queue> #define MAXN 505 #define MAXM 8000005 #define oo 1000000007 #define ll long long using namespace std; struct MCMF { struct node { int x,y,c,v,next; }line[MAXM]; int Lnum,_next[MAXN],pre[MAXN],dis[MAXN],flow,cost; bool inqueue[MAXN]; void initial(int n) { Lnum=-1; for (int i=0;i<=n;i++) _next[i]=-1; } void addline(int x,int y,int c,int v) { line[++Lnum].next=_next[x],_next[x]=Lnum; line[Lnum].x=x,line[Lnum].y=y,line[Lnum].c=c,line[Lnum].v=v; line[++Lnum].next=_next[y],_next[y]=Lnum; line[Lnum].x=y,line[Lnum].y=x,line[Lnum].c=0,line[Lnum].v=-v; } bool SPFA(int s,int e) { int x,k,y; queue<int> Q; while (!Q.empty()) Q.pop(); memset(dis,0x7f,sizeof(dis)); memset(inqueue,false,sizeof(inqueue)); Q.push(s); dis[s]=0,pre[s]=-1; while (!Q.empty()) { x=Q.front(),Q.pop(),inqueue[x]=false; for (k=_next[x];k!=-1;k=line[k].next) if (line[k].c) { y=line[k].y; if (dis[y]>dis[x]+line[k].v) { dis[y]=dis[x]+line[k].v; pre[y]=k; if (!inqueue[y]) { inqueue[y]=true; Q.push(y); } } } } if (dis[e]>oo) return false; flow=oo,cost=0; for (k=pre[e];k!=-1;k=pre[line[k].x]) flow=min(flow,line[k].c),cost+=line[k].v; cost*=flow; for (k=pre[e];k!=-1;k=pre[line[k].x]) line[k].c-=flow,line[k^1].c+=flow; return true; } void MinCostMaxFlow(int s,int e,int &Aflow,int &Acost) { Aflow=0,Acost=0; while (SPFA(s,e)) { Aflow+=flow; Acost+=cost; } } }T; int num[405],dis[402][402]; void Floyd(int n) { int k,i,j; for (k=1;k<=n;k++) for (i=1;i<=n;i++) for (j=1;j<=n;j++) { if (dis[i][k]==-1 || dis[k][j]==-1) continue; if (dis[i][j]!=-1 && dis[i][j]<=dis[i][k]+dis[k][j]) continue; dis[i][j]=dis[i][k]+dis[k][j]; } } int main() { int n,m,k,p,i,j,x,y,d,s,e,Af,Ac; while (~scanf("%d%d%d%d",&n,&m,&k,&p)) { s=n+m+10,e=s+1,T.initial(e); memset(num,0,sizeof(num)); for (i=1;i<=n;i++) scanf("%d",&x),num[x]++; // n个vessel for (i=1;i<=m;i++) T.addline(s,i,num[i],0); // m个station for (i=1;i<=n;i++) T.addline(i+m,e,1,0); // n个port memset(dis,-1,sizeof(dis)); while (k--) { scanf("%d%d%d",&x,&y,&d); if (dis[x][y]!=-1 && dis[x][y]<=d) continue; dis[x][y]=dis[y][x]=d; } while (p--) { scanf("%d%d%d",&x,&y,&d),x+=m; if (dis[y][x]!=-1 && dis[y][x]<=d) continue; dis[y][x]=d; } Floyd(n+m); for (i=1;i<=m;i++) for (j=1;j<=n;j++) if (dis[i][j+m]!=-1) T.addline(i,j+m,1,dis[i][j+m]); T.MinCostMaxFlow(s,e,Af,Ac); printf("%d\n",Ac); } return 0; }

上一篇:android内置搜索对话框(浮动搜索)例子
下一篇:C/C++内存分配

相关文章

相关评论