4032085_ac_454ms_5916k.cpp

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

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

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

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

int n, s, t;
int minc;



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;
}
*/
#include <stdio.h>
#include <vector>
#define inf 10000000
using namespace std;

int n, k, minc;
int st, ed;
struct node
{
	int id;
	int c, f, w;
};

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 que[1000000];
int v[3000], fa[3000];
vector <node> graph[3000];

bool find_way()
{
	int id;
	int i, s;
	int f, r;

	for(i = 0; i < n; i++)
		v[i] = inf;
	v[st] = 0;
	f = r = -1;
	que[++r] = st;
	while(f!=r)
	{
		++f;
		s = que[f];
		for(i = 0; i < graph[s].size(); i++)
		{
			id = graph[s][i].id;
			if(graph[s][i].f<graph[s][i].c&&v[s]+graph[s][i].w<v[id])
			{
				v[id] = v[s]+graph[s][i].w;
				que[++r] = id;
				fa[id] = s;
			}
		}
	}
	if(v[ed] < inf)
		return true;
	return false;
}

void add_way()
{
	int i, j, l, tmp;

	i = ed;
	do
	{
		j = i;
		i = fa[j];
		for(l = 0; l < graph[i].size(); l++)
		{
			if(graph[i][l].id == j)
			{
				graph[i][l].f++;
				tmp = -graph[i][l].f;
				break;
			}
		}
		for(l = 0; l < graph[j].size(); l++)
		{
			if(graph[j][l].id == i)
			{
				graph[j][l].f = tmp;
				break;
			}
		}
	}while(i!=st);
	minc += v[ed];
}

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

	for (i = 0; i < 3000; i++)
	{
		graph[i].clear();
	}
	for (i = 1; i <= N; i++)
	{
		t.id = i;
		t.c = 1;
		t.f = t.w = 0;
		graph[0].push_back(t);
	}
	for (i = N + 1; i <= N + M * N; i++)
	{
		t.id = N + 1 + M * N;
		t.c = 1;
		t.f = t.w = 0;
		graph[i].push_back(t);
	}
	for(i = 1; i <= N; i++)
	{
		st = N + 1;
		for (j = 1; j <= M; j++)
		{
			for (k = 1; k <= N; k++)
			{
				t.id = st;
				t.c = 1;
				t.w = k * tm[i - 1][j - 1];
				t.f = 0;
				graph[i].push_back(t);
				t.id = i;
				t.c = t.f = 0;
				t.w = -k * tm[i - 1][j - 1];
				graph[st].push_back(t);
				st++;
			}
		}
	}
	minc = 0;
	st = 0;
	ed = N + 1 + M * N;
	n = ed + 1;
}

int main()
{
	int cas;

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