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

枚举每条边, 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