题目大意是给定N个垃圾桶，每个垃圾桶内装有N种数量不同的垃圾，现你把垃圾分类，要求每个垃圾桶装一种垃圾，移动一个单位的垃圾消耗1的代价，求最小的移动代价，使得完成垃圾分类。

这个问题可以构建出二分图的最佳匹配的模型。把原有的垃圾桶看作X集合中的顶点，垃圾种类看作Y集合中的顶点，边(a,b)表示a垃圾桶装b类垃圾，所需移动的代价。求二分图的最小权完备匹配，匹配边权值之和最小值就是要求的结果。

为了能够使用求最大权匹配的KM算法，只需把所有边的权值取相反数，求最大权匹配，结果再取相反数即可。

/* 
 * Problem: Ural1076 Trash
 * Author: Guo Jiabao
 * Time: 2009.3.25 22:20
 * State: Solved
 * Memo: KM
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int MAX=301,INF=0x7FFFFFFF;
using namespace std;
int N,M,U;
int adj[MAX][MAX];
int Match[MAX],L[MAX],Slack[MAX];
bool vis[MAX];
void init()
{
    int i,j,c;
    freopen("trash.in","r",stdin);
    freopen("trash.out","w",stdout);
    scanf("%d",&N);M=N+1;U=N+N;
    for (i=1;i<=N;i++)
    {
        c=0;
        for (j=M;j<=U;j++)
        {
            scanf("%d",&adj[i][j]);
            c+=adj[i][j];
        }
        for (j=M;j<=U;j++)
            adj[i][j]=c-adj[i][j];
    }
    for (i=1;i<=N;i++)
        for (j=M;j<=U;j++)
            adj[i][j]=-adj[i][j];
}
bool path(int i)
{
    vis[i]=true;
    for (int j=M;j<=U;j++)
    {
        if (!vis[j])
        {
            int t=L[i]+L[j]-adj[i][j];
            if (t==0)
            {
                vis[j]=true;
                if (Match[j]==0 || path(Match[j]))
                {
                    Match[j]=i;
                    return true;
                }
            }
            else if (t<Slack[j])
                Slack[j]=t;
        }
    }
    return false;
}
void KM()
{
    int i,j,delta;
    for (i=1;i<=N;i++)
    {
        L[i]=-INF;
        for (j=M;j<=U;j++)
            if (adj[i][j]>L[i])
                L[i]=adj[i][j];
    }
    for (i=1;i<=N;i++)
    {
        for (;;)
        {
            memset(vis,0,sizeof(vis));
            for (j=M;j<=U;j++)
                Slack[j]=INF;
            if (path(i)) break;
            delta=INF;
            for (j=M;j<=U;j++)
                if (!vis[j] && Slack[j]<delta)
                    delta=Slack[j];
            for (j=1;j<=N;j++)
                if (vis[j])
                    L[j]-=delta;
            for (j=M;j<=U;j++)
                if (vis[j])
                    L[j]+=delta;
        }
    }
}
void print()
{
    int i,Ans=0;
    for (i=M;i<=U;i++)
        Ans+=adj[Match[i]][i];
    Ans=-Ans;
    printf("%dn",Ans);
}
int main()
{
    init();
    KM();
    print();
    return 0;
}