\(\\\)
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;
}