[SDOI2006]仓库管理员的烦恼

题目描述

仓库管理员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：

说明

样例说明：方案是：第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的边

跑最小费用流

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<queue>
 6 using namespace std;
 7 struct Node
 8 {
 9   int next,to,cap,dis;
10 }edge[200001];
11 int num=1,head[1001],n,ans,inf,pre[1001],map[201][201],s[201];
12 bool vis[1001];
13 int dist[1001];
14 void add(int u,int v,int dis,int cap)
15 {
16   num++;
17   edge[num].next=head[u];
18   edge[num].cap=cap;
19   edge[num].to=v;
20   edge[num].dis=dis;
21   head[u]=num;
22   num++;
23   edge[num].next=head[v];
24   edge[num].cap=0;
25   edge[num].to=u;
26   edge[num].dis=-dis;
27   head[v]=num;
28 }
29 bool SPFA()
30 {
31   memset(vis,0,sizeof(vis));
32   memset(dist,127/3,sizeof(dist));
33   inf=dist[0];
34   queue<int>Q;
35   Q.push(0);
36   vis[0]=1;
37   dist[0]=0;
38   while (Q.empty()==0)
39     {
40       int u=Q.front();
41       Q.pop();
42       vis[u]=0;
43       for (int i=head[u];i!=-1;i=edge[i].next)
44     {
45       int v=edge[i].to;
46       if (edge[i].cap&&dist[v]>dist[u]+edge[i].dis)
47         {
48           dist[v]=dist[u]+edge[i].dis;
49           pre[v]=i;
50           if (vis[v]==0)
51         {
52           vis[v]=1;
53           Q.push(v);
54         }
55         }
56     }
57     }
58   if (dist[2*n+1]==inf) return 0;
59   return 1;
60 }
61 void change()
62 {
63   int x=2*n+1;
64   while (x)
65     {
66       ans+=edge[pre[x]].dis;
67       edge[pre[x]].cap-=1;
68       edge[pre[x]^1].cap+=1;
69       x=edge[pre[x]^1].to;
70     }
71 }
72 int main()
73 {int i,j;
74   cin>>n;
75   memset(head,-1,sizeof(head));
76   for (i=1;i<=n;i++)
77     {
78       for (j=1;j<=n;j++)
79         {
80       scanf("%d",&map[i][j]);
81       s[j]+=map[i][j];
82     }
83     }
84   for (i=1;i<=n;i++)
85     add(0,i,0,1);
86   for (i=n+1;i<=2*n;i++)
87     add(i,2*n+1,0,1);
88   for (i=1;i<=n;i++)
89     {
90       for (j=n+1;j<=2*n;j++)
91     {
92       add(i,j,s[j-n]-map[i][j-n],1);
93     }
94     }
95   while (SPFA()) change();
96   cout<<ans;
97 }