题目描述
仓库管理员M最近一直很烦恼，因为他的上司给了他一个艰难的任务：让他尽快想出一种合理的方案，把公司的仓库整理好。
已知公司共有n个仓库和n种货物，由于公司进货时没能很好的归好类，使得大部分的仓库里面同时装有多种货物，这就给搬运工作人员搬运货物时带来了很多的麻烦。
仓库管理员M的任务就是设计一种合理的方案，把仓库里面的货物重新整理，把相同的货物放到同一个仓库，以便于日后的管理，在整理过程中肯定需要把某些货物从一个仓库搬运到另一个仓库，已知每一次搬运货物所付出的代价等于搬运该货物的重量。
编程任务：
请你帮助仓库管理员M设计搬运方案，使得把所有的货物归好类：使每种货物各自占用一个仓库，或者说每个仓库里只能放一种货物。同时要求搬运货物时所付出的所有的总的代价最小。
输入输出格式
输入格式：
第一行为n (1 <= n <= 150)，仓库的数量。
以下为仓库货物的情况。第i+1行依次为第i个仓库中n种货物的数量x(0 <= x <= 100)。
输出格式：
把所有的货物按要求整理好所需的总的最小代价。
输入输出样例
输入样例#1：
4
62 41 86 94
73 58 11 12
69 93 89 88
81 40 69 13
输出样例#1：
650
说明
样例说明：方案是：第1种货物放到仓库2中；第2种货物放到仓库3中；第3种货物放到仓库4中；第4种货物放到仓库1中
统计出每一种货物的数量总和sum[i]，那么对于第i种货物，将它放到第j位置时的代价就是sum[i]-map[j][i]
可以想到最小费用最大流
虚构原点，汇点为0,2*n+1
i点与j+n点连一条权值sum[i]-map[j][i]，流为1的边
0与i点建一条权值为0，流为1的边
j+n与2*n+1建一条权值为0，流为1的边
跑最小费用流
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
struct Node
{
int next,to,cap,dis;
}edge[];
int num=,head[],n,ans,inf,pre[],map[][],s[];
bool vis[];
int dist[];
void add(int u,int v,int dis,int cap)
{
num++;
edge[num].next=head[u];
edge[num].cap=cap;
edge[num].to=v;
edge[num].dis=dis;
head[u]=num;
num++;
edge[num].next=head[v];
edge[num].cap=;
edge[num].to=u;
edge[num].dis=-dis;
head[v]=num;
}
bool SPFA()
{
memset(vis,,sizeof(vis));
memset(dist,/,sizeof(dist));
inf=dist[];
queue<int>Q;
Q.push();
vis[]=;
dist[]=;
while (Q.empty()==)
{
int u=Q.front();
Q.pop();
vis[u]=;
for (int i=head[u];i!=-;i=edge[i].next)
{
int v=edge[i].to;
if (edge[i].cap&&dist[v]>dist[u]+edge[i].dis)
{
dist[v]=dist[u]+edge[i].dis;
pre[v]=i;
if (vis[v]==)
{
vis[v]=;
Q.push(v);
}
}
}
}
if (dist[*n+]==inf) return ;
return ;
}
void change()
{
int x=*n+;
while (x)
{
ans+=edge[pre[x]].dis;
edge[pre[x]].cap-=;
edge[pre[x]^].cap+=;
x=edge[pre[x]^].to;
}
}
int main()
{int i,j;
cin>>n;
memset(head,-,sizeof(head));
for (i=;i<=n;i++)
{
for (j=;j<=n;j++)
{
scanf("%d",&map[i][j]);
s[j]+=map[i][j];
}
}
for (i=;i<=n;i++)
add(,i,,);
for (i=n+;i<=*n;i++)
add(i,*n+,,);
for (i=;i<=n;i++)
{
for (j=n+;j<=*n;j++)
{
add(i,j,s[j-n]-map[i][j-n],);
}
}
while (SPFA()) change();
cout<<ans;
}