hdu 4081 Qin Shi Huang's National Road System(次小生成树变形) - c++编程基础

设为首页加入收藏

当前位置：

首页 -> 基础 -> c++编程基础

TOP

hdu 4081 Qin Shi Huang's National Road System(次小生成树变形)

2014-11-23 17:34:21 来源: 作者: 【大中小】浏览:11次

Tags：hdu 4081 Qin Shi Huang' National Road System 生成变形

枚举每条边, ans=(val[u]+val[v]) / (prim - g[u][v])；

而prim则是包含边的生成树中最小的那个权值和。

先求出原图的最小生成树。use[u][v] = 2时，边在MST上， use[u][v] = 1时，存在边。

f[u][v]表示u->v的最小瓶颈路。

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define FF(i, a, b) for(int i=a; i=b; i--)
#define REP(i, n) for(int i=0; i


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：POJ 水题若干	下一篇：元素查找