Description：

Solution：

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n;

#define MAXN 152

int w[MAXN][MAXN];

int sum[MAXN];

int g[MAXN][MAXN];

int la[MAXN],lb[MAXN];

bool va[MAXN],vb[MAXN];

#define INF 0x3f3f3f3f

int delta;

int match[MAXN];

bool find(int k)

{

	va[k] = true;

	for(int i = 1;i <= n;++i)

	{

		if(!vb[i])

		{

			if(la[k] + lb[i] == g[k][i])

			{

				vb[i] = true;

				if(match[i] == -1 || find(match[i]))

				{

					match[i] = k;

					return true;

				}

			}

			else

			{

				delta = min(delta,la[k] + lb[i] - g[k][i]);

			}

		}

	}

	return false;

}

int main()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)

	{

		for(int j = 1;j <= n;++j)

		{

			scanf("%d",&w[i][j]);

			sum[j] += w[i][j];

		}

	}

	for(int i = 1;i <= n;++i)

	{

		for(int j = 1;j <= n;++j)

		{

			g[i][j] = -(sum[i] - w[j][i]);

		}

	}

	for(int i = 1;i <= n;++i)

	{

		la[i] = -INF;

		lb[i] = 0;

		for(int j = 1;j <= n;++j)

		{

			la[i] = max(la[i],g[i][j]);

		}

	}

	memset(match,-1,sizeof(match));

	for(int i = 1;i <= n;++i)

	{

		while(true)

		{

			memset(va,false,sizeof(va));

			memset(vb,false,sizeof(vb));

			delta = INF;

			if(find(i))break;

			for(int k = 1;k <= n;++k)

			{

				if(va[k])la[k] -= delta;

				if(vb[k])lb[k] += delta;

			}

		}

	}

	int ans = 0;

	for(int i = 1;i <= n;++i)

	{

		ans += g[match[i]][i];

	}

	cout << -ans << endl;

	return 0;

}