\(\\\)

Description

---

有 \(n\) 种货物和 \(n\) 个仓库，开始第 \(i\) 个仓库里有 \(a_{ij}\) 个第 \(j\) 种货物。

现在要让每种货物都只放到一个仓库里，且一个仓库只放一种货物。

货物将在仓库之间移动，总代价就是移动的所有货物的总重。

现不指定哪种货物放到哪个仓库里，求最小总代价。

• \(n\le 150,a_{ij}\le 100\)

\(\\\)

Solution

---

一开始的想法是把限制加到流量上，后来发现不行。

为什么呢？首先这题的建图肯定是一侧货物一侧仓库。

如果是货物 \(\to\) 仓库，我们无法确定最后哪个仓库放哪种货物，所以仓库向汇点的流量无法限制。

如果是仓库 \(\to\) 货物，我们又无法确定每个仓库向每个货物的流量了，因为我们不知道这种货物是否放回到这个仓库里，进而代价会算多 \((\) 有的边费用可能是 \(0\) 没有算上 \()\) 。

\(\\\)

因此我们要把代价加到费用上。

考虑此题的限制：

• 每种货物只能放到一个仓库里
• 每个仓库只能放一种货物

于是原点连出和连入汇点的所有边流量都是 \(1\) ，代表如上限制。

我们预处理 \(sum_i\) 表示第 \(i\) 种货物的总量。

\(\\\)

如果源连货物，货物指向仓库，仓库连汇，则建图方式：

因为是货物向仓库连边，那么如果这一货物要放到这一仓库，原本在这一仓库的此货物就不用产生代价，其他的这一货物都要产生代价。

货物 \(j\) 向仓库 \(i\) 要连一条流量为 \(1\) ，费用为 \(sum_j-a_{ij}\) 的边。

\(\\\)

如果源连仓库，仓库指向货物，货物连汇，则建图方式：

此时所谓的货物，其实是代表的存放这一货物的仓库。

而仓库连向货物，代价就应该是令这一仓库作为存放这一货物的代价。

显然费用和原来思考方式相同。

\(\\\)

Code

---

将第二种建图方式的代码放在了注释里。

#include<cmath>

#include<queue>

#include<cstdio>

#include<cctype>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

#define N 310

#define M 50010

#define R register

#define gc getchar

#define inf 1000000000

using namespace std;

inline int rd(){

  int x=0; bool f=0; char c=gc();

  while(!isdigit(c)){if(c=='-')f=1;c=gc();}

  while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc();}

  return f?-x:x;

}

int n,m,s,t,tot=1,maxn;

int hd[N],pre[N],id[N],dis[N],w[N][N],sum[N];

struct edge{int f,w,to,nxt;}e[M];

inline void add(int u,int v,int f,int w){

  e[++tot].to=v; e[tot].w=w;

  e[tot].f=f; e[tot].nxt=hd[u]; hd[u]=tot;

}

bool vis[N];

queue<int> q;

inline bool spfa(){

  for(R int i=1;i<=maxn;++i) dis[i]=inf,vis[i]=0;

  dis[s]=0; q.push(s);

  while(!q.empty()){

    int u=q.front();

    q.pop(); vis[u]=0;

    for(R int i=hd[u],v;i;i=e[i].nxt)

      if(e[i].f&&(dis[v=e[i].to]>dis[u]+e[i].w)){

        dis[v]=dis[u]+e[i].w;

        pre[v]=u; id[v]=i;

        if(!vis[v]) vis[v]=1,q.push(v);

      }

  }

  return dis[t]<inf;

}

inline int mcmf(){

  int res=0,tmp;

  while(spfa()){

    tmp=inf;

    for(R int i=t;i!=s;i=pre[i]) tmp=min(tmp,e[id[i]].f);

    for(R int i=t;i!=s;i=pre[i]){

      e[id[i]].f-=tmp; e[id[i]^1].f+=tmp;

    }

    res+=tmp*dis[t];

  }

  return res;

}

int main(){

  n=rd();

  s=0; maxn=t=(n<<1)+1;

  for(R int i=1;i<=n;++i){

    add(s,i,1,0); add(i,s,0,0);

    add(n+i,t,1,0); add(t,n+i,0,0);

    for(R int j=1;j<=n;++j) w[i][j]=rd();

  }

  for(R int i=1;i<=n;++i)

    for(R int j=1;j<=n;++j) sum[j]+=w[i][j];

  for(R int i=1;i<=n;++i)

    for(R int j=1;j<=n;++j){

      add(j,n+i,1,sum[j]-w[i][j]);

      add(n+i,j,0,w[i][j]-sum[j]);

    }

  /*

  for(R int i=1;i<=n;++i)

    for(R int j=1;j<=n;++j){

      add(i,n+j,1,sum[j]-w[i][j]);

      add(n+j,i,0,w[i][j]-sum[j]);

    }

  */

  printf("%d\n",mcmf());

  return 0;

}