来自"NOCOW"

一看就知道是带权的二分图最大匹配，用最小费用最大流实现，而最小费用最大流用SPFA实现。

我的垃圾代码：

#include<iostream>
#define maxn 500
#define maxq 10000
#define mx 1000000
using namespace std;
long c[maxn][maxn]={0},g[maxn][maxn]={0},d[maxn]={0};
int q[maxq]={0},pre[maxn]={0};
bool vis[maxn]={0};
bool b=1;
long n,s=1,t;
long p=0;
void augment()
{
    int i=t;
    long a=mx;
    while (i>s)
    {
        if (c[pre[i]][i]<a) a=c[pre[i]][i];
        i=pre[i];
    }
    i=t;
    while (i>s)
    {
        c[pre[i]][i]-=a;
        c[i][pre[i]]+=a;
        i=pre[i];
    }
}
void SPFA()
{
    memset(q,0,sizeof(q));
    memset(vis,0,sizeof(vis));
    memset(pre,0,sizeof(pre));
    int l=1,r=1;
    for (int i=1;i<=t;++i) d[i]=mx;
    d[s]=0;
    q[1]=s;
    vis[s]=1;
    while (l<=r)
    {
        if (l==1 && r==maxq) break;
        long x=q[l];
        for (int i=1;i<=t;++i)
        if (d[x]+g[x][i]<d[i] && c[x][i]>0)
        {
            d[i]=d[x]+g[x][i];
            pre[i]=x;
            if (!vis[i]){vis[i]=1;++r;if (r>maxq) r=1;q[r]=i;}
        }
        vis[x]=0;
        ++l;if (l>maxq) l=1;
    }
    if (d[t]!=mx) {p+=d[t];augment();b=1;return;}
    b=0;
}
int main(void)
{
    cin>>n;
    t=2*n+2;
    for (int i=1;i<=n;++i)
    {
        int s=0;
        for (int j=1;j<=n;++j)
        {
            c[1+i][1+n+j]=1;
            cin>>g[1+i][1+n+j];
            s+=g[1+i][1+n+j];
        }
        for (int j=1;j<=n;++j)
        {
            g[1+i][1+n+j]=s-g[1+i][1+n+j];
            g[1+n+j][1+i]=-g[1+i][1+n+j];
        }
    }
    for (int i=1;i<=n;++i)
    {
        c[1][1+i]=1;
        c[1+n+i][t]=1;
    }
    b=1;
    while (b) SPFA();
    cout<<p<<"\n";
    return 0;
}
from churchill

建模非常重要。题目中说，要使每个垃圾桶向外转移的垃圾数最少，那么由于垃圾总数是一定的，那么转换一下，就是求留在垃圾桶内不需要转移的垃圾尽量多，那么很容易建出图来，以垃圾桶为X集合，垃圾种类为Y集，如果垃圾桶Xi中 ，垃圾Yi的数量为a，那么Xi，Yi连一条权为a的边，再求最优匹配，使所选边的权值最大，再用总权值减去这些边的值。

program cao;
const
  maxn=150;
 
var
  w:array[0..maxn,0..maxn] of longint;
  x,y:array[0..maxn] of boolean;
  lx,ly,c:array[0..maxn] of longint;
  d,e,f,g,h,i,j,k,l,n,m,p,q,all:longint;
 
procedure init;
begin
  all:=0;
  read(n);
  for i:=1 to n do
    for j:=1 to n do
    begin
      read(w[i,j]);
      inc(all,w[i,j]);
    end;
end;
 
function dfs(v:longint):boolean;
var
  i:longint;
begin
  if v=0 then exit(true);
  x[v]:=true;
  for i:=1 to n do
    if (y[i]=false)and(lx[v]+ly[i]=w[v,i]) then
    begin
      y[i]:=true;
      if dfs(c[i]) then
      begin
        c[i]:=v;
        exit(true);
      end;
    end;
  exit(false);
end;
 
procedure main;
begin
  for i:=1 to n do
    for j:=1 to n do
      if w[i,j]>lx[i] then lx[i]:=w[i,j];
  for k:=1 to n do
    repeat
      fillchar(x,sizeof(x),0);
      fillchar(y,sizeof(y),0);
      if dfs(k) then break;
      d:=maxlongint;
      for i:=1 to n do
        if x[i] then
          for j:=1 to n do
            if (y[j]=false)and(lx[i]+ly[j]-w[i,j]<d) then
              d:=lx[i]+ly[j]-w[i,j];
      for i:=1 to n do
      begin
        if x[i] then dec(lx[i],d);
        if y[i] then inc(ly[i],d);
      end;
    until false;
end;
 
procedure print;
begin
  for i:=1 to n do
    dec(all,w[c[i],i]);
  writeln(all);
end;
 
begin
  init;
  main;
  print;
end.

http://www.withflying.com/?p=138

http://www.withflying.com