首页 > 代码库 > poj 2139 Six Degrees of Cowvin Bacon , floyd
poj 2139 Six Degrees of Cowvin Bacon , floyd
点击打开链接
题意:给定牛的关系图,求其中一头牛与其他牛关系路程之和sum最小,然后输出 sum*100/(n-1)
floyd求任意两点间的最短路程
注意: inf不能太大,因为 f[i][k] + f[k][j] 做加法时可能会溢出!
#include <cstdio> #include <cstring> const int maxn = 300 + 5; const int inf = 1<<29; int n, m; int f[maxn][maxn]; int a[maxn]; void floyd() { int i, j, k; for(k=1; k<=n; ++k) for(i=1; i<=n; ++i) for(j=1; j<=n; ++j) { if(f[i][j]> f[i][k] + f[k][j]) f[i][j] = f[i][k] + f[k][j]; } } int main() { int i, j, k, ans, ret; while(~scanf("%d%d",&n, &m)) { for(i=0; i<=n; ++i) { for(j=0; j<=n; ++j) f[i][j] = inf; f[i][i] = 0; } while(m--) { scanf("%d", &k); for(i=0; i<k; ++i) { scanf("%d", &a[i]); for(j=0; j<i; ++j) f[a[i]][a[j]] = f[a[j]][a[i]] = 1; } } floyd(); ans = inf; for(i=1; i<=n; ++i) { ret = 0; for(j=1; j<=n; ++j) ret += f[i][j]; if(ans > ret) ans = ret; } printf("%d\n", ans*100/(n-1)); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。