noip模拟赛 仓库

分析:非常像货车运输那道题.先求一下最大生成树.求完之后会发现并不好处理.通常这类求生成树的题目不会就分析kruscal算法的性质.每往最大生成树中加一条边，如果配重大于这条边权，那么这条边所连的两个集合就都要建一个仓库.也可以这么想：本来在所有点都建仓库，如果配重小于这条边的边权，那么少建一个仓库.把所有的边权放进一个数组里，排个序，二分一下就好了.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

int n,m,q,fa[100010],p[100010],cnt;
struct node
{
    int u,v,w;
}e[100010];

bool cmp(node a,node b)
{
    return a.w > b.w;
}

int find(int x)
{
    if (x == fa[x])
        return x;
    return fa[x] = find(fa[x]);
}

bool cmp2(int x,int y)
{
    return x > y;
}

int main()
{
    scanf("%d%d%d",&n,&m,&q);
    for (int i = 1; i <= n; i++)
        fa[i] = i;
    for (int i = 1; i <= m; i++)
        scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
    sort(e + 1,e + 1 + m,cmp);
    for (int i = 1; i <= m; i++)
    {
        int fu = find(e[i].u),fv = find(e[i].v);
        if (fu != fv)
        {
            fa[fu] = fv;
            p[++cnt] = e[i].w;
        }
    }
    sort(p + 1,p + 1 + cnt,cmp2);
    while (q--)
    {
        int temp;
        scanf("%d",&temp);
        int l = 1,r = cnt,ans = 0;
        while (l <= r)
        {
            int mid = (l + r) >> 1;
            if (p[mid] >= temp)
            {
                ans = mid;
                l = mid + 1;
            }
            else
                r = mid - 1;
        }
        printf("%d
",n - ans);
    }

    return 0;
}