货物运输

解析

首先明确题意：只要经过的每条边权值不超过 $l$$l$ 就行。因为城市可以无限量加油。

这题不需在线，可以离线解决。把边和询问的信息都保存下来，按照边权 $w$$w$ 对边排序，按照询问的 $l$$l$ 对询问排序。 这样，解决的较小的 $l$$l$，对较大的询问也有帮助。

建立并查集。对于每个询问 $i$$i$，找出若干条边 $j$$j$ 使得 $a_j\le l_i$$a_j\leq l_i$。 每合并两个节点，如果它们不在一个连通块内，$ans$$ans$ 就减去原来两个独立的集合内的组合，加上联通后的集合的节点组合。公式如下。

对于每个排序过后的询问都应当保存原始下标。找回原始询问编号保存答案即可。

也有大神说：“是否强制在线对这种做法其实没有影响吧，边权离散化之后可以直接预处理出所有答案。”

代码

​x
// 1443D
#include <bits/stdc++.h>
#define int long long
#define SIZE 100010
#define all(x) x.begin(), x.end()
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;

struct edge
{
    int u, v, w;
} a[SIZE];

struct query
{
    int l, pos;
} q[SIZE];

int f[SIZE];
int s[SIZE];
int res[SIZE];
int siz[SIZE];
bool operator <(edge a, edge b)
{
    return a.w<b.w;
}
bool operator <(query a, query b)
{
    return a.l<b.l;
}
int n, m, T;

int getRoot(int x)
{
    if(x==f[x]) return x;
    return f[x]=getRoot(f[x]);
}

int ans=0;
void mg(int x, int y)
{
    int fx=getRoot(x);
    int fy=getRoot(y);
    if(fx==fy) return;
    f[fx]=fy;
    ans-=siz[fx]*(siz[fx]-1)/2;
    ans-=siz[fy]*(siz[fy]-1)/2;
    siz[fy]+=siz[fx];
    ans+=siz[fy]*(siz[fy]-1)/2;
}

void init()
{
    for(int i=0; i<=n; i++) 
        f[i]=i, siz[i]=1;
}

signed main()
{
    while(cin>>n>>m>>T)
    {
        ans=0;
        for(int i=1; i<=m; i++)
            cin>>a[i].u>>a[i].v>>a[i].w;
        sort(a+1, a+m+1);
        for(int i=1; i<=T; i++)
            cin>>q[i].l, q[i].pos=i;
        sort(q+1, q+T+1);
        init();
        int j=1;
        for(int i=1; i<=T; i++)
        {
            while(j<=m && a[j].w<=q[i].l)
            {
                mg(a[j].u, a[j].v);
                j++;
            }
            //debug(ans)
            res[q[i].pos]=ans;
        }
        for(int i=1; i<=T; i++)
            cout<<res[i]<<endl;
    }

    return 0;
}