和POJ 1714一樣。。
http://blog.csdn.net/huanghongxun/article/details/50967578
#include <cstdio>
#include <algorithm>
#include <cstring>
const int N = , M = N * ;
#define adj(i,j) for(int i=h[j];i;i=p[i])if(v[i]!=fa&&!vis[v[i]])
using namespace std;
int h[N], p[M], w[M], v[M], cnt = ;
int n, k, vis[N], ans, rt, c;
void add(int a, int b, int c) {
v[++cnt] = b; w[cnt] = c; p[cnt] = h[a]; h[a] = cnt;
}
int mx[N], sz[N], mi, dis[N];
void dfssize(int x, int fa) {
sz[x] = ; mx[x] = ;
adj(i,x) {
dfssize(v[i], x);
sz[x] += sz[v[i]];
if (sz[v[i]] > mx[x]) mx[x] = sz[v[i]];
}
}
void dfsrt(int r, int x, int fa) {
if (sz[r] - sz[x] > mx[x]) mx[x] = sz[r] - sz[x];
if (mx[x] < mi) mi = mx[x], rt = x;
adj(i,x) dfsrt(r, v[i], x);
}
void dfsdis(int x, int d, int fa) {
dis[c++] = d;
adj(i,x) dfsdis(v[i], d + w[i], x);
}
int calc(int x, int d) {
int ans = ;
c = ;
dfsdis(x, d, );
sort(dis, dis + c);
for (int i = , j = c - ; i < j; ++i) {
for (; dis[i] + dis[j] > k && i < j; --j);
ans += j - i;
}
return ans;
}
void dfs(int x) {
int fa = ;
mi = n;
dfssize(x, fa); dfsrt(x, x, fa);
ans += calc(rt, );
vis[rt] = ;
adj(i, rt) {
ans -= calc(v[i], w[i]);
dfs(v[i]);
}
}
int main() {
int u, v, w, i, m; char redundancy[];
while(scanf("%d%d", &n, &m) != EOF && (n || k)) {
memset(vis, , sizeof vis);
memset(h, , sizeof h);
cnt = ans = ;
for (i = ; i < m; i++) {
scanf("%d%d%d%s", &u, &v, &w, redundancy);
add(u, v, w); add(v, u, w);
}
scanf("%d", &k);
dfs();
printf("%d\n", ans);
}
return ;
}
3365: [Usaco2004 Feb]Distance Statistics 路程統計
Description
在得知了自己農場的完整地圖後(地圖形式如前三題所述),約翰又有了新的問題.他提供
一個整數K(1≤K≤109),希望你輸出有多少對農場之間的距離是不超過K的.
Input
第1到I+M行:與前三題相同;
第M+2行:一個整數K.
Output
農場之間的距離不超過K的對數.
Sample Input
E
E
S
N
W
S
Sample Output
5
Hint
有五對道路之間的距離小于10
1-4,距離為3
4-7,距離為2
1-7,距離為5
3-5,距離為7
3-6,距離為9