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

奇怪的建图+全局最短路,附Cpp代码

Posted by yousiki at 2016-07-26 16:53:15 on Problem 2139
题意:
给定 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:
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