| ||||||||||
| 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 | |||||||||
奇怪的建图+全局最短路,附Cpp代码题意:
给定 n, m.
之后m行,每行是一个集合。
每一个集合里任意两个元素之间的距离都是1.
距离之间具有传递性,就是最短路。
最后求出一个点,这个点到其他所有点的距离和最小,即
求ans令 ∑(i=1..n)dis[ans][i] 最小。
然后输出平均距离(乘100倍保留整数),
即 sum / (n-1) * 100
分析:
Floyd大法好!
代码:cpp
#include<cstdio>
using namespace std;
const int INF = 0x3f3f3f3f;
int n, m, G[300][300], q[300], ans = INF;
signed main(void) {
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
G[i][j] = i == j ? 0 : INF;
for (int i = 0, j, k, c; i < m; i++)
for (scanf("%d", &c), j = 0; j < c; j++)
for (scanf("%d", q + j), k = 0, q[j]--; k < j; k++)
G[q[k]][q[j]] = G[q[j]][q[k]] = 1;
for (int k = 0; k < n; k++)
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
G[i][j] = G[i][j] < G[i][k] + G[k][j] ? G[i][j] : G[i][k] + G[k][j];
for (int i = 0, j, sum; i < n; ans = ans < sum ? ans : sum, i++)
for (j = sum = 0; j < n; j++)
sum += G[i][j];
printf("%d\n", 100 * ans / (n - 1));
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator