题解 P2457 【[SDOI2006]仓库管理员的烦恼】

· · 题解

大大的水题，裸的最小费用流。

1.统计出每一种货物的数量总和sum[i]，那么对于第i种货物，将它放到第j位置时的代价就是sum[i]-map[j][i]。

2.虚拟一个源点和一个汇点，虚拟n个点代表n种货物，另外n个点代表n个仓库。（所以总共有n*2+1个点）。

3.将源点和1～n个点连一条流量为1，费用为0的边。（代表每一种货物都需要安放）

4.将i和j+n之间连一条流量为1，费用为sum[i]-map[j][i]的边。（表示将第i种货物放到第j个仓库的代价）

5.将j+n和汇点之间连一条流量为1，费用为零的边。（表示第j个仓库能且仅能放一种货物，就避免了把不同的货物放到同一个仓库中）

然后直接跑最小费用流就可以了。

鼓掌～～鼓掌～～

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
int n,map[155][155],sum[155];
struct node
{
    int next,to,dis,cap;
}edge[50005];
int head[1001],size=1;
void putin(int from,int to,int dis,int cap)
{
    size++;
    edge[size].next=head[from];
    edge[size].to=to;
    edge[size].dis=dis;
    edge[size].cap=cap;
    head[from]=size;
}
void in(int from,int to,int dis,int cap)
{
    putin(from,to,dis,cap);
    putin(to,from,-dis,0);
}
bool vis[1001];
int dist[1001],pre[1001],cost;
bool spfa(int r,int t)
{
    memset(dist,127/3,sizeof(dist));
    int mmax=dist[0];
    queue<int>mem;
    mem.push(r);
    dist[r]=0;
    vis[r]=1;
    while(!mem.empty())
    {
    int x=mem.front();mem.pop();
    vis[x]=0;
    for(int i=head[x];i!=-1;i=edge[i].next)
    {
        int y=edge[i].to;
        if(edge[i].cap&&dist[y]>dist[x]+edge[i].dis)
        {
        dist[y]=dist[x]+edge[i].dis;
        pre[y]=i;
        if(!vis[y])
        {
            mem.push(y);
            vis[y]=1;
        }
        }
    }
    }
    if(dist[n*2+1]==mmax)return 0;
    else return 1;
}
void change()
{
    int x=n*2+1;
    while(x!=0)
    {
    cost+=edge[pre[x]].dis;
    edge[pre[x]].cap-=1;
    edge[pre[x]^1].cap+=1;
    x=edge[pre[x]^1].to;
    }
}
int main()
{
    freopen("[SDOI2006]仓库管理员的烦恼.in","r",stdin);
    freopen("[SDOI2006]仓库管理员的烦恼.out","w",stdout);
    int i,j;
    memset(head,-1,sizeof(head));
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
        scanf("%d",&map[i][j]),sum[j]+=map[i][j];
    for(i=1;i<=n;i++)
    {
    in(0,i,0,1);
    in(i+n,n*2+1,0,1);
    for(j=1;j<=n;j++)
        in(i,j+n,sum[i]-map[j][i],1);
    }
    while(spfa(0,n*2+1))change();
    printf("%d\n",cost);
    return 0;
}