W 公司有 m 个仓库和 n 个零售商店。第 i 个仓库有 ai 个单位的货物；第 j 个零售商店需要 bj 个单位的货物。
货物供需平衡，即 ∑ai=∑bj 。
从第 i 个仓库运送每单位货物到第 j 个零售商店的费用为 cij 。
试设计一个将仓库中所有货物运送到零售商店的运输方案，使总运输费用最少。
第 1 行有 2 个正整数 m 和 n ，分别表示仓库数和零售商店数。
接下来的一行中有 m 个正整数 ai ，表示第 i 个仓库有 ai 个单位的货物。
再接下来的一行中有 n 个正整数 bj ，表示第 j 个零售商店需要 bj 个单位的货物。
接下来的 m 行，每行有 n 个整数，表示从第 i 个仓库运送每单位货物到第 j 个零售商店的费用 cij 。
两行分别输出最小运输费用和最大运输费用。
2 3 220 280 170 120 210 77 39 105 150 186 122
48500 69140
1≤n,m≤100
学YJQ大佬用记事本打代码的第一题
这 跟上一道题有什么区别吗？！「网络流24题」负载平衡问题
还是有点区别的
从s往每个仓库连边，容量ai 费用0
从每个商店向t连边，容量bj 费用0
每个仓库向每个商店连边 容量INF 费用cij
还讲一下记事本打代码的初体验吧
注意力瞬间集中是真的，没那么在意手速也是真的
挂了两次 第一次CE（dfs(x,INF)
第二次 居然挂在n,m反向读入？？？woc？？？
果然还是个菜鸡啊QAQ
#include<cmath> #include<queue> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; #define R register const int INF=999999999; int n,m,s,t; struct emm{ int e,f,v,c; }a[100007]; int h[207]; int tot=1; void con(int u,int v,int w,int f) { a[++tot].f=h[u]; h[u]=tot; a[tot].e=v; a[tot].v=w; a[tot].c=f; a[++tot].f=h[v]; h[v]=tot; a[tot].e=u; a[tot].c=-f; return; } void scan() { scanf("%d%d",&m,&n); s=0,t=n+m+1; for(R int i=1;i<=m;++i) { int x; scanf("%d",&x); con(s,i,x,0); } for(R int i=1;i<=n;++i) { int x; scanf("%d",&x); con(i+m,t,x,0); } for(R int i=1;i<=m;++i) for(R int j=1;j<=n;++j) { int x; scanf("%d",&x); con(i,j+m,INF,x); } return; } queue<int>q; bool sf[207]; int d[207]; bool spfa() { memset(sf,0,sizeof(sf)); memset(d,127,sizeof(d)); d[s]=0;sf[s]=1;q.push(s); while(!q.empty()) { int x=q.front();q.pop(); for(int i=h[x];i;i=a[i].f) if(d[a[i].e]>d[x]+a[i].c&&a[i].v) { d[a[i].e]=d[x]+a[i].c; if(!sf[a[i].e]) { sf[a[i].e]=1; q.push(a[i].e); } } sf[x]=0; } return d[t]<INF; } long long ans=0; int dfs(int x,int al) { if(x==t||!al)return al; int fl=0; for(int i=h[x];i;i=a[i].f) if(d[a[i].e]==d[x]+a[i].c&&a[i].v&&!sf[a[i].e]) { sf[a[i].e]=1; int f=dfs(a[i].e,min(al,a[i].v)); if(f) { fl+=f; al-=f; ans+=f*a[i].c; a[i].v-=f; a[i^1].v+=f; if(!al)break; } } if(!fl)d[x]=-INF; return fl; } void run() { while(spfa()) { sf[t]=1; while(sf[t]) { memset(sf,0,sizeof(sf)); dfs(s,INF); } } cout<<ans<<endl; for(int i=2;i<=tot;i+=2) { a[i].v+=a[i^1].v; a[i^1].v=0; swap(a[i].c,a[i^1].c); } ans=0; while(spfa()) { sf[t]=1; while(sf[t]) { memset(sf,0,sizeof(sf)); dfs(s,INF); } } cout<<-ans<<endl; return; } int main() { scan(); run(); return 0; }下次要用没有自动对齐的纯·记事本 2333
转载于:https://www.cnblogs.com/qwerta/p/9379732.html
相关资源：JAVA上百实例源码以及开源项目