代码：
1 #include2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 8 int n, m, q; 9 int pre[20100], num[20100];10 11 struct node{12 int begin;13 int end;14 int w;15 int index;16 }mm[100100], qq[5005];17 18 bool cmp(node a, node b)19 {20 return a.w < b.w;21 }22 23 void init()24 {25 for(int i = 1; i <= n; i++)26 {27 pre[i] = i;28 num[i] = 1;29 }30 }31 32 int find(int x)33 {34 if(x != pre[x])35 pre[x] = find(pre[x]);36 return pre[x];37 }38 39 int merge(int x, int y)40 {41 int fx = find(x);42 int fy = find(y);43 if(fx != fy)44 {45 if(num[fx] > num[fy])46 {47 int temp = fx;48 fx = fy;49 fy = temp;50 }51 pre[fx] = fy;52 num[fy] += num[fx];53 }54 return num[fy];55 }56 57 int main()58 {59 int t, ans[5005];60 scanf("%d", &t);61 while(t--)62 {63 scanf("%d%d%d", &n, &m, &q);64 init();65 for(int i = 0; i < m; i++)66 {67 scanf("%d%d%d", &mm[i].begin, &mm[i].end, &mm[i].w);68 }69 sort(mm, mm + m, cmp);70 for(int i = 0; i < q; i++)71 {72 scanf("%d", &qq[i].w); 73 qq[i].index = i;74 }75 sort(qq, qq + q, cmp);76 int cnt = 0;77 for(int i = 0; i < q; i++)78 {79 while(mm[cnt].w <= qq[i].w && cnt < m)80 {81 merge(mm[cnt].begin, mm[cnt].end);82 cnt++;83 } 84 ans[qq[i].index] = 0;85 for(int j = 1 ; j <= n; j ++)86 {87 if(pre[j] == j) 88 ans[qq[i].index] += num[j] * (num[j] - 1);89 } 90 } 91 for(int i = 0; i < q; i++)92 printf("%d\n", ans[i]);93 }94 return 0;95 }
总结：
刚开始还以为只是ans[qq[i].index] = num[j] * (num[j] - 1)，结果WA，后来才发现这样计算虽然案例都符合但是是错的，如果案例过了，还WA，还真得考虑下是计算方面引起的错误。