#include <iostream>
using namespace std;

const int N = 300;
const int MAX = 500000;
int K, C, M;
int dis[N][N];

void read()
{
	scanf("%d%d%d", &K, &C, &M);
	int i, j;
	for(i=1; i<=K+C; i++)
		for(j=1; j<=K+C; j++)
		{
			scanf("%d", &dis[i][j]);
			if( dis[i][j] == 0 ) dis[i][j] = MAX;
		}
}

void dijkstra( int p, int n)
{
	bool vis[N];
	memset(vis, false, sizeof(vis));
	vis[p] = true;
	int i, minn, loc;
	while( true )
	{
		minn = MAX;
		for(i=1; i<=n; i++)
			if( !vis[i] && dis[p][i] < minn)
			{
				minn = dis[p][i];
				loc = i;
			}
		if( minn == MAX) return;

		vis[loc] = true;
		for(i=1; i<=n; i++)
			if( !vis[i] && dis[p][i] > minn + dis[loc][i])
				dis[p][i] = minn + dis[loc][i];
	}
}
void Dijkstra()
{
	for(int i=1; i<=K; i++)
		dijkstra(i, K+C);
}

bool a[N][N], used[N];
int n, m;
int b[N];

bool find( int now )
{
	int i, j;
	for(i=1; i<=m; i++)
		if( !used[i] && a[now][i] )
		{
			used[i] = true;
			j = b[i];
			b[i] = now;
			if(j == -1 || find(j) ) return true;
			b[i] = j;
		}
	return false;
}

bool match()
{
	int i;
	memset(b, -1, sizeof(b));
	for(i=1; i<=n; i++)
	{
		memset(used, false, sizeof(used));
//		fill(vis, vis + m + 1, false);
		if( !find(i) ) return false;
	}
	return true;
}

bool judge( int mid )
{
	int i, j, k;
	memset(a, false, sizeof(a));
	for(i=1; i<=K; i++)
		for(j=K+1; j<=C+K; j++)
			if(dis[i][j] <= mid)
			{
				for(k=1; k<=M; k++)
					a[ j-K ][ (i-1) * M + k ] = true;
			}
	n = C;
	m = M*K;
//	cout<<mid<<endl;
//	for(i=1; i<=n; i++, cout<<endl)	for(j=1; j<=m; j++) cout<<a[i][j]<<' ';
	return  match();
}

int get_value()
{
	int left = 1, right = MAX, mid;
	while( left < right )
	{
		mid = (left + right)/2;
		if( judge (mid) ) right = mid;
		else left = mid + 1;
	}
	return right;
}

void floyd()
{
	int n = K + C;
	for( int k=1; k<=n; k++)
		for( int i=1; i<=n; i++)
			for( int j=1; j<=n; j++)
				if( dis[i][j] > dis[i][k] + dis[k][j]) dis[i][j] = dis[i][k] + dis[k][j];
}
int main()
{
	read();
	floyd();
//	Dijkstra();
//	for(int i=1; i<=K; i++, cout<<endl) for(int j=K+1; j<=K+C; j++) cout<<dis[i][j]<<' ';
	printf("%d\n", get_value());
	return 0;
}

• Re:why wa? (16) forsona 2009-03-07 21:27:42