Description
W 公司有 m 个仓库和 n 个零售商店。第 i 个仓库有 ai 个单位的货物；第 j 个零售商店需要 bj 个单位的货物。
货物供需平衡，即 ∑ai=∑bj 。
从第 i 个仓库运送每单位货物到第 j 个零售商店的费用为 cij 。
试设计一个将仓库中所有货物运送到零售商店的运输方案，使总运输费用最少。
Input
第 1 行有 2 个正整数 m 和 n ，分别表示仓库数和零售商店数。
接下来的一行中有 m 个正整数 ai ，表示第 i 个仓库有 ai 个单位的货物。
再接下来的一行中有 n 个正整数 bj ，表示第 j 个零售商店需要 bj 个单位的货物。
接下来的 m 行，每行有 n 个整数，表示从第 i 个仓库运送每单位货物到第 j 个零售商店的费用 cij 。
Output
两行分别输出最小运输费用和最大运输费用。
Sample Input
2 3
220 280
170 120 210
77 39 105
150 186 122
Sample Output
48500
69140
Hint
1≤n,m≤100
题解
这 跟上一道题有什么区别吗？！「网络流24题」负载平衡问题
还是有点区别的
从s往每个仓库连边，容量ai 费用0
从每个商店向t连边，容量bj 费用0
每个仓库向每个商店连边 容量INF 费用cij
还讲一下记事本打代码的初体验吧
注意力瞬间集中是真的，没那么在意手速也是真的
挂了两次 第一次CE（dfs(x,INF)
第二次 居然挂在n,m反向读入？？？woc？？？
#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