| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
贴个代码,自己闲着无聊写了个堆//这题似乎是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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator