题目描述：
雾。
题目分析：
这题目也太水了.
很明显是一个最小权的二分图匹配.
我们从物品向仓库建边，花费即为除了原本在本仓库的物品重量之和.
跑一下费用流就好了
题目链接：
Ac 代码：
#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
const int inf=0x7fffffff;
const int maxm=1e6+100;
int head[maxm],to[maxm<<1],net[maxm<<1],cost[maxm<<1],cap[maxm<<1];
int cnt=1;
int n;
inline void add(int u,int v,int c1,int c2){cnt++;to[cnt]=v,cap[cnt]=c1,cost[cnt]=c2,net[cnt]=head[u],head[u]=cnt;}
inline void addedge(int u,int v,int c1,int c2){add(u,v,c1,c2),add(v,u,0,-c2);}
namespace MCMF{
int flow[maxm],pre[maxm],id[maxm],dis[maxm],maxflow,mincost;
bool vis[maxm];
std::queue<int> dl;
inline bool SPFA(int s,int t)
{
while(!dl.empty()) dl.pop();
memset(dis,127/3,sizeof(dis)),memset(pre,-1,sizeof(pre));
dl.push(s),dis[s]=0,pre[s]=0,vis[s]=1,flow[s]=inf;
while(!dl.empty())
{
int now=dl.front();
dl.pop();
vis[now]=0;
for(int i=head[now];i;i=net[i])
if(cap[i]&&dis[to[i]]>dis[now]+cost[i])
{
dis[to[i]]=dis[now]+cost[i];
pre[to[i]]=now;
id[to[i]]=i;
flow[to[i]]=std::min(cap[i],flow[now]);
if(!vis[to[i]]) vis[to[i]]=1,dl.push(to[i]);
}
}
return pre[t]!=-1;
}
inline void change_cap(int s,int t,int x)
{
int now=t;
while(now!=s)
{
cap[id[now]]-=x,cap[id[now]^1]+=x;
now=pre[now];
}
}
inline int mcmf(int s,int t)
{
maxflow=0,mincost=0;
while(SPFA(s,t))
{
maxflow+=flow[t],mincost+=flow[t]*dis[t];
change_cap(s,t,flow[t]);
}
return mincost;
}
}
std::vector<int> w[maxm];
int num[maxm];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
int x;
scanf("%d",&x);
w[j].push_back(x);
num[j]+=x;
}
int s=0,t=2*n+10;
for(int i=1;i<=n;i++) addedge(s,i,1,0),addedge(i+n,t,1,0);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
addedge(i,j+n,1,num[i]-w[i][j-1]);
}
printf("%d\n",MCMF::mcmf(s,t));
return 0;
}