Description：
N个订单（每个订单订K种商品），M个供应商（每个供应商供应K种商品），K种商品，后N行，表示每一个订单的详细信息，后M行表示每个供应商供应的详细信息，后K 个N * M的矩阵表示第m个供应商送第k种商品到第n个订单的花费
Solution：
建图，分商品来建，对于第k种商品：
· 源点连N个订单对于该商品的需求，费用0，容量为需求量
·N个订单对应连M个供应商，费用为第k个矩阵中对于的费用，容量为inf
·M个供应商链接汇点，费用0，容量为供应量
Code:
小错误还是很多，基本操作，一开始开的空间计算错误，加边操作中对于反向边的val和cost操作反了
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#define inf (1 << 28)
using namespace std;
const int maxn = 111;
const int maxk = 111;
const int maxm = 111*111*2;
int need[maxn][maxk];
int have[maxn][maxm];
int cost[maxm][maxn];
int allneed[maxk];
int allhave[maxk];
int n,m,k;
struct node
{
int to,val,cost,pre;
}e[maxm];
int id[maxn * 4];
int cnt;
void add(int from,int to,int val,int cost)
{
e[cnt].to = to;
e[cnt].val = val;
e[cnt].cost = cost;
e[cnt].pre = id[from];
id[from] = cnt++;
swap(from,to);
e[cnt].to = to;
e[cnt].val = 0;
e[cnt].cost = -cost;
e[cnt].pre = id[from];
id[from] = cnt++;
}
void init()
{
memset(allhave,0,sizeof(allhave));
memset(allneed,0,sizeof(allneed));
memset(id,-1,sizeof(id));
cnt = 0;
}
spfa 版mcmf算法，一开始忘了加vis数组了，花费的计算算成了一整段的，应该分段计算花费
int dis[maxn];
int pre[maxn];
int path[maxn];
int vis[maxn];
bool spfa(int s,int t)
{
memset(pre,-1,sizeof(pre));
memset(vis,0,sizeof(vis));
for(int i = 0;i < maxn ;++i)
dis[i] = inf;
dis[s] = 0;
vis[s] = 1;
queue<int> q;
q.push(s);
while(q.size())
{
int now = q.front();
q.pop();
for(int i = id[now];~i;i = e[i].pre)
{
int to = e[i].to;
int val = e[i].val;
int cost = e[i].cost;
if(val > 0 && dis[now] + cost < dis[to])
{
dis[to] = dis[now] + cost;
pre[to] = now;
path[to] = i;
if(!vis[to])
{
vis[to] = 1;
q.push(to);
}
}
}
vis[now] = 0;
}
if(pre[t] == -1)return false;
return true;
}
int mcmf(int s,int t)
{
int c = 0;
while(spfa(s,t))
{
int mf = inf;
for(int now = t;now != s;now = pre[now])
{
if(e[path[now]].val < mf)
mf = e[path[now]].val;
}
for(int now = t;now != s;now = pre[now])
{
e[path[now]].val -= mf;
e[path[now]^1].val += mf;
c += mf * e[path[now]].cost;
}
}
return c;
}
建图操作
对于供应商到汇点的加边操作，放错了循环……
int main()
{
int ans;//最小费用
int s,t;//源点汇点
while(~scanf("%d%d%d",&n,&m,&k),n+m+k)
{
init();
ans = 0;
s = 0;
t = n + m + 1;
//第i个订单对于第j种商品的需求量
for(int i = 1;i <= n;++i)
{
for(int j = 1;j <= k;++j)
{
scanf("%d",&need[i][j]);
allneed[j] += need[i][j];
}
}
//第i个供应商对于第j种商品的供应量
for(int i = 1;i <= m;++i)
{
for(int j = 1;j <= k;++j)
{
scanf("%d",&have[i][j]);
allhave[j] += have[i][j];
}
}
int flag = 1;//需求是否能被满足
for(int i = 1;i <= k;++i)
{
memset(id,-1,sizeof(id));
cnt = 0;
if(allhave[i] < allneed[i])
flag = 0;
for(int j = 1;j <= n;++j)
{
add(s,j,need[j][i],0);
for(int l = 1;l <= m;++l)
{
scanf("%d",&cost[l][j]);
if(!flag)continue;
add(j,n+l,inf,cost[l][j]);
}
}
for(int l = 1;l <= m;++l)
add(n+l,t,have[l][i],0);
if(!flag)continue;
ans += mcmf(s,t);
}
if(!flag)printf("-1
");
else printf("%d
",ans);
}
return 0;
}