\(\\\)
有 \(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#include #include #include #include #include #include #include #define N 310#define M 50010#define R register#define gc getchar#define inf 1000000000using 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 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]