題目大意是給定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;
}