Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

贴个代码,自己闲着无聊写了个堆

Posted by a280920481 at 2018-10-24 16:05:14 on Problem 2139
//这题似乎是O(n*n*n*logn)的复杂度.然而只用了32ms,挺奇怪的,本来以为会TLE
#include <iostream>
#include <stdio.h>
#include <vector>
using namespace std;

int list[301][301];//与第i个节点相连的第j个节点是第几个节点
int du[301];//第i个节点的度

int d[301];//节点距离

struct node
{
	int number;
	int d;
};

vector<node> jd;
bool fedge[301][301];
int total[301];//记录每头牛的总距离

void mypush(node x);
void mypop();


int main()
{
	node a, b;//临时变量
	int N, M, K;
	scanf_s("%d%d", &N, &M);
	for (int i = 0; i < M; i++)
	{
		scanf_s("%d", &K);
		for (int j = 0; j < K; j++)
		{
			scanf_s("%d", &total[j]);
			total[j]--;
		}
		for (int j = 0; j < K; j++)
		{
			for (int u = j + 1; u < K; u++)
			{
				fedge[total[j]][total[u]] = true;
				fedge[total[u]][total[j]] = true;
			}
		}
	}

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if (fedge[i][j])
			{
				list[i][du[i]] = j;
				du[i]++;
			}
		}
	}
	//图已构建

	for (int i = 0; i < 301; i++)
	{
		total[i] = 0;
	}

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			d[j] = 100000;
		}
		d[i] = 0;
		a.d = 0;
		a.number = i;
		mypush(a);
		while (!jd.empty())
		{
			a = jd.front();
			mypop();
			for (int j = 0; j < du[a.number]; j++)
			{
				if (d[list[a.number][j]] > a.d + 1)
				{
					d[list[a.number][j]] = a.d + 1;
					b.number = list[a.number][j];
					b.d = a.d + 1;
					mypush(b);
				}
			}
		}
		for (int j = 0; j < N; j++)
		{
			total[i] += d[j];
		}

	}
	int min = 10000;

	for (int i = 0; i < N; i++)
	{
		if (min > total[i])
		{
			min = total[i];
		}
	}

	printf_s("%d\n", (int)(100.0*min / (N - 1)));

	return 0;

}

//堆的实现
void mypush(node x)
{
	static int me, fa;
	static node l;

	me = jd.size();
	jd.push_back(x);
	while (me)
	{
		fa = (me - 1) / 2;
		if (jd[fa].d > jd[me].d)
		{
			l = jd[fa];
			jd[fa] = jd[me];
			jd[me] = l;
		}
		else
		{
			break;
		}
		me = fa;
	}
	return;
}

void mypop()
{
	static int me, son, size;
	static node l;

	jd[0] = jd.back();
	jd.pop_back();
	size = jd.size() - 1;
	me = 0;

	while (2 * me < size)
	{
		son = 2 * me + 1;
		if ((son < size) && (jd[son + 1].d < jd[son].d))
		{
			son++;
		}
		if (jd[son].d < jd[me].d)
		{
			l = jd[son];
			jd[son] = jd[me];
			jd[me] = l;
		}
		else
		{
			break;
		}
		me = son;
	}

	return;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator