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