金融网站cms,集团 投入巨资 做网站,江苏省现代化示范校建设网站,网站建设费用摊销P4015 运输问题 文章目录题目描述#xff1a;输入格式#xff1a;输出格式#xff1a;输入输出样例#xff1a;题解#xff1a;代码#xff1a;题目描述#xff1a; 输入格式#xff1a; 输出格式#xff1a;
两行分别输出最小运输费用和最大运输费用。
输入输出样例…P4015 运输问题
文章目录题目描述输入格式输出格式输入输出样例题解代码题目描述 输入格式 输出格式
两行分别输出最小运输费用和最大运输费用。
输入输出样例
输入 #1
2 3
220 280
170 120 210
77 39 105
150 186 122输出 #1
48500
69140题解
最小费用最大流(MCMF)问题 根据样例数据分析 橙色为第一个仓库晕倒各零售商店的单位费用 绿色为第二个 一边是仓库一边是商店典型的二分图还是完全二分图 我们可以在仓库的左边设置一个源点S右边设置一个终点T。S指向每一个仓库容量为ai费用为0而每一个商店指向T容量为bi费用为0 从仓库到商店的边容量是min仓库货物量ai商店容量bi费用为读入的值 为了方便处理我们可以将S点记为编号1仓库为编号1 ~ m商店为m1 ~ nmT点为201 然后直接跑最小费用最大流就可以了 找到最大后将费用取反再跑一遍即可找到最小
代码
#includeiostream
#includecmath
#includecstdio
#includecstring
#includequeue
#includestack
#includevector
#includemap
#includeset
#includealgorithm#define I_copy_this_answer return 0;using namespace std;int n,m,head[1100];
int cnt1;
int mincost,maxwater;
int flow[1100];
int b[1100],cost[310][310];
int pre[1100],last[1100],dis[1100],vis[1100],a[1100];
int s0;
//last记录边pre记录点
struct node{int next,to,dis,flow;
}edge[100860]; void addedge(int next,int to,int dis,int flow)
{edge[cnt].toto;edge[cnt].disdis;edge[cnt].flowflow;edge[cnt].nexthead[next];head[next]cnt;
}int spfa()
{memset(flow,0x3f,sizeof(flow));memset(dis,0x3f,sizeof(dis));memset(vis,0,sizeof(vis));queue int q;q.push(s);dis[s]0;vis[s]1;pre[201]-1; //初始化汇点的前点 while(!q.empty()){int uq.front();q.pop();vis[u]0;for(int ihead[u];i;iedge[i].next){int vedge[i].to;int wedge[i].dis;int ledge[i].flow;if(dis[u]wdis[v]l0) //没有流量的话这条路就增广不了最短距离是建立在增广路存在的基础上的 {dis[v]dis[u]w;last[v]i; //last指的是这个点(v)与上个点(u)相连的边的编号 pre[v]u; //pre指的是这条路径上这个点(v)的上一个点 flow[v]min(flow[u],l); //把当前边流量与上个点的流量对比解决出现仓库货物比需要的少的情况 if(!vis[v]){q.push(v);vis[v]1;}}}}return pre[201]!-1; //如果不是这个值就说明这个点被刷新增广成功
}void mcmf()
{while(spfa()){mincostdis[201]*flow[201]; //从源点出发到汇点的单位费用再乘以单位由于每次只增广一条路而且仓库和商店是直接连接的可以这样写 int t201;while(t!0){edge[last[t]].flow-flow[201]; //回溯修改每条边的流量因为该算法中途找到的增广路不是最后的增广路所以这个要等到最后来改变 edge[last[t]^1].flowflow[201];tpre[t];}}
}void build_edge(int t)//t用来控制边权的正负为了方便求最小和最大
{for(int i1;im;i){addedge(0,i,0,a[i]);addedge(i,0,0,0);//与源点S相连 } for(int i1;im;i)for(int j1;jn;j){addedge(i,jm,cost[i][j]*t,b[j]);addedge(jm,i,-cost[i][j]*t,0);//仓库与商店相连 }for(int i1;in;i){addedge(im,201,0,b[i]);//与汇点T相连 addedge(201,im,0,0);}
}int main()
{int i,j;scanf(%d %d,m,n);for(i1;im;i){int t1;scanf(%d,a[i]); }for(i1;in;i)scanf(%d,b[i]);for(i1;im;i)for(j1;jn;j)scanf(%d,cost[i][j]); //仓库与商店的边权 build_edge(1); //建立边权为正的边跑最小费用最大流 mcmf();//最小费用最大流(Min Cost Max Flow 的缩写 printf(%d,mincost); maxwater0;mincost0; cnt1;memset(head,0,sizeof(head));build_edge(-1);//建立边权为符的边 mcmf();printf(\n%d,-mincost);
}
