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