4031991_re.cpp

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

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

struct node
{
	int c, w, f;
}net[1000][1000];

struct Node
{
	int v, fa;
}best[3000];

int n, s, t;
int minc;

int N, M;
int tm[50][50];

void init()
{
	int i, j;

	scanf("%d%d", &N, &M);
	for (i = 0; i < N; i++)
	{
		for (j = 0; j < M; j++)
		{
			scanf("%d", &tm[i][j]);
		}
	}
}

int Find_Way()
{
	int i, j;
	int quit;

	for(i = 0; i < n; i++)
		best[i].v = inf;
	best[s].v = 0;
	do
	{
		quit = 1;
		for(i = 0; i < n; i++)
		{
			if(best[i].v < inf)
			{
				for(j = 0; j < n; j++)
				{
					if(net[i][j].f<net[i][j].c&&best[i].v+net[i][j].w<best[j].v)
					{
						best[j].v = best[i].v+net[i][j].w;
						best[j].fa = i;
						quit = 0;
					}
				}
			}
		}
	}while(!quit);
	if(best[t].v < inf)
		return 1;
	return 0;
}

void Add_Way()
{
	int i, j;

	i = t;
	do
	{
		j = i;
		i = best[j].fa;
		net[i][j].f++;
		net[j][i].f = -net[i][j].f;
	}while(i!=s);
	minc += best[t].v;
}

void get_graph()
{
	int i, j, k, st;

	memset(net,0,sizeof(net));
	for (i = 1; i <= N; i++)
	{
		net[0][i].c = 1;
	}
	for (i = N + 1; i <= N + M * N; i++)
	{
		net[i][N + 1 + M * N].c = 1;
	}
	for(i = 1; i <= N; i++)
	{
		st = N + 1;
		for (j = 1; j <= M; j++)
		{
			for (k = 1; k <= N; k++)
			{
				net[i][st].c = 1;
				net[i][st].w = k * tm[i - 1][j - 1];
				net[st][i].w = -net[i][st].w;
				st++;
			}
		}
	}
	minc = 0;
	s = 0;
	t = N + 1 + M * N;
	n = t + 1;
}

int main()
{
	int cas;

	scanf("%d", &cas);
	while(cas--)
	{
		init();
		get_graph();
		while(Find_Way())
			Add_Way();
		printf("%.6lf\n",1.0 * minc / N);
	}
	return 0;
}