题目链接：http://poj.org/problem?id=2831
题意：
题目大意：给张图，然后问你，如果某边的权值下降为V，那么这个边有无可能在最小生成树中呢？节点数≤1000，边数≤100000，询问数≤100000。
思路：prim。
考虑prim的算法过程：每次加入一个点，并且加入该点的条件是dis[i]是还没加入点的dis[]中最小的。
所以执行prim时，用数组no[]保存某点加入的次序，numm[i]保存第i个加入的点的id
查询边（a，b）时（假设a的加入次序先于b），则枚举no[a]+1 ~ no[b]加入的点的dis[]，若存在x<=dis[k]，原prim算法过程可被打破，边（a，b）会被选择，
因为该边是当前最佳的边；否则还是原算法过程进行。
1 #include <iostream>
2 #include <cstdio>
3 #include <cmath>
4 #include <cstring>
5 #include <iomanip>
6 using namespace std;
7
8 const int maxd = 1000001;
9 const int N = 1005;
10 const int M = 1000001;
11
12 int map1[N][N], dis[N], vis[N], no[N], numm[N];
13 struct Path
14 {
15 int a, b, c;
16 }p[M];
17
18 void prim(int n)
19 {
20 int cur;
21 for(int i=1; i<=n; i++) dis[i] = maxd;
22 memset(vis, 0, sizeof(vis));
23 cur = 1; dis[cur] = 0; vis[cur] = 1;
24 no[cur] = 1; numm[1] = cur;
25 //找n-1轮
26 for(int i=2; i<=n; i++)
27 {
28 //枚举上一次加入的点与各个点的距离，更新最小距离dis[i]
29 for(int j=1; j<=n; j++)
30 {
31 if(vis[j]==0 && dis[j]>map1[cur][j])
32 dis[j] = map1[cur][j];
33 }
34 //选出最短的边，把该边连接的点加入结果集
35 int mind = maxd;
36 for(int j=1; j<=n; j++)
37 {
38 if(vis[j]==0 && dis[j]<mind)
39 {
40 mind = dis[j];
41 cur = j;
42 }
43 }
44 vis[cur] = 1;
45 no[cur] = i;
46 numm[i] = cur;
47 }
48 }
49
50 void init(int n)
51 {
52 for(int i=1; i<=n; i++)
53 for(int j=1; j<=n; j++)
54 map1[i][j] = maxd;
55 }
56
57 int main()
58 {
59 int n, m, q, pi, x;
60 scanf("%d%d%d",&n, &m, &q);
61 init(n);
62 for(int i=1; i<=m; i++)
63 {
64 scanf("%d%d%d",&p[i].a,&p[i].b,&p[i].c);
65 if(map1[p[i].a][p[i].b]>p[i].c)
66 map1[p[i].a][p[i].b] = map1[p[i].b][p[i].a] = p[i].c;
67 }
68 //prim走一遍，保存no[],numm[],dis[]
69 prim(n);
70
71 for(int i=1; i<=q; i++)
72 {
73 scanf("%d%d",&pi,&x);
74 int a = no[p[pi].a], b = no[p[pi].b], temp, flag = 0, bno, bnum, sno, snum;
75 if(a>b){bno = a; bnum = p[pi].a; sno = b; snum = p[pi].b;}
76 else {bno = b; bnum = p[pi].b; sno = a; snum = p[pi].a;}
77 //枚举p[pi].a 和 p[pi].b两点之间加入的点
78 //若x<=dis[],则该边为这轮的最优边，可成为最小生成树中的一边
79 for(int k=sno+1; k<=bno; k++)
80 {
81 if(x<=dis[numm[k]])
82 {
83 flag = 1;
84 break;
85 }
86 }
87 if(flag==1)
88 printf("Yes ");
89 else
90 printf("No ");
91 }
92 return 0;
93 }
2 #include <cstdio>
3 #include <cmath>
4 #include <cstring>
5 #include <iomanip>
6 using namespace std;
7
8 const int maxd = 1000001;
9 const int N = 1005;
10 const int M = 1000001;
11
12 int map1[N][N], dis[N], vis[N], no[N], numm[N];
13 struct Path
14 {
15 int a, b, c;
16 }p[M];
17
18 void prim(int n)
19 {
20 int cur;
21 for(int i=1; i<=n; i++) dis[i] = maxd;
22 memset(vis, 0, sizeof(vis));
23 cur = 1; dis[cur] = 0; vis[cur] = 1;
24 no[cur] = 1; numm[1] = cur;
25 //找n-1轮
26 for(int i=2; i<=n; i++)
27 {
28 //枚举上一次加入的点与各个点的距离，更新最小距离dis[i]
29 for(int j=1; j<=n; j++)
30 {
31 if(vis[j]==0 && dis[j]>map1[cur][j])
32 dis[j] = map1[cur][j];
33 }
34 //选出最短的边，把该边连接的点加入结果集
35 int mind = maxd;
36 for(int j=1; j<=n; j++)
37 {
38 if(vis[j]==0 && dis[j]<mind)
39 {
40 mind = dis[j];
41 cur = j;
42 }
43 }
44 vis[cur] = 1;
45 no[cur] = i;
46 numm[i] = cur;
47 }
48 }
49
50 void init(int n)
51 {
52 for(int i=1; i<=n; i++)
53 for(int j=1; j<=n; j++)
54 map1[i][j] = maxd;
55 }
56
57 int main()
58 {
59 int n, m, q, pi, x;
60 scanf("%d%d%d",&n, &m, &q);
61 init(n);
62 for(int i=1; i<=m; i++)
63 {
64 scanf("%d%d%d",&p[i].a,&p[i].b,&p[i].c);
65 if(map1[p[i].a][p[i].b]>p[i].c)
66 map1[p[i].a][p[i].b] = map1[p[i].b][p[i].a] = p[i].c;
67 }
68 //prim走一遍，保存no[],numm[],dis[]
69 prim(n);
70
71 for(int i=1; i<=q; i++)
72 {
73 scanf("%d%d",&pi,&x);
74 int a = no[p[pi].a], b = no[p[pi].b], temp, flag = 0, bno, bnum, sno, snum;
75 if(a>b){bno = a; bnum = p[pi].a; sno = b; snum = p[pi].b;}
76 else {bno = b; bnum = p[pi].b; sno = a; snum = p[pi].a;}
77 //枚举p[pi].a 和 p[pi].b两点之间加入的点
78 //若x<=dis[],则该边为这轮的最优边，可成为最小生成树中的一边
79 for(int k=sno+1; k<=bno; k++)
80 {
81 if(x<=dis[numm[k]])
82 {
83 flag = 1;
84 break;
85 }
86 }
87 if(flag==1)
88 printf("Yes ");
89 else
90 printf("No ");
91 }
92 return 0;
93 }