3285656_ac_110ms_440k.c

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <string.h>
#define INF 2100000000

int cost[231][231];

void floyd(int Q)
{
	int i, j, k;
 
	for(k = 1; k <= Q; k++)
	{
		for(i = 1; i <= Q; i++)
		{
			if(cost[i][k]!=INF)
			{
				for(j = 1; j <= Q; j++)
				{
					if(cost[i][k]+cost[k][j]<cost[i][j])
					{
						cost[i][j]=cost[i][k]+cost[k][j]; 
					}
				}
			}
		}  
	}
}

int k, c, m;
int link[31][201];
int cap[31], b[31];
int map[201][31];

void getgraph(int max)
{
	int i, j;

	memset(map,0,sizeof(map));
	for(i = k+1; i <= k+c; i++)
	{
		for(j = 1; j <= k; j++)
		{
			if(cost[i][j]!=0&&cost[i][j]<=max)
			{
				map[i-k][j] = 1;
			}
		}
	}
}

int find(int v)
{
	int i, j;

	for(i = 1; i <= k; i++)
	{
		if(map[v][i]&&!b[i])
		{
			b[i] = 1;
			if(cap[i])
			{
				cap[i]--;
				link[i][++link[i][0]] = v;
				return 1;
			}
			else
			{
				for(j = 1; j <= link[i][0]; j++)
					if(find(link[i][j]))
					{
						link[i][j] = v;
						return 1;
					}
			}
		}
	}
	return 0;
}

int match(int mid)
{
	int i;

	for(i = 0; i <= k; i++)
	{
		cap[i] = m;
	}
	getgraph(mid);
	memset(link,0,sizeof(link));
	for(i = 1; i <= c; i++)
	{
		memset(b,0,sizeof(b));
		if(!find(i))
		{
			return 0;
		}
	}
	return 1;
}

void solve()
{
	int min, max, mid;

	min = 0;max = 10000;

	while(min < max)
	{
		mid = (min+max)>>1;
		if(match(mid))
			max = mid;
		else
			min = mid+1;
	}
	printf("%d\n",min);
}

int main()
{
	int i, j;

	scanf("%d%d%d",&k,&c,&m);
	for(i = 1; i <= k+c; i++)
	{
		for(j = 1; j <= k+c; j++)
		{
			scanf("%d",&cost[i][j]);
			if(cost[i][j]==0&&i!=j)
				cost[i][j] = INF;
		}
	}
	floyd(k+c);
	solve();
	return 0;
}