题解：P3665 [USACO17OPEN] Switch Grass P

zzwdsj · 2025-02-08 11:10:12 · 题解

~~测试点下载：测试点.zip~~

思路

两个结论：

异色点对的最短距离一定是一条边。证明：当一条路径上的边两端颜色均相同是，这条路径两端颜色也相同，所以如果一条路径上两端颜色不同，那么这条路径上必有一条边两端颜色不同。那么如果异色点对的最短距离是一条（边数大于一的）路径，那么选这条路径上的一条两端颜色不同的边肯定比选这条路径更优。
异色点对的最短距离一定是一条最小生成树上的边。证明：如果一条两端异色的边 (u,v) 没有被加入最小生成树。u 到 v 必有一条只经过最小生成树上边的路径，且这条路径上的边权均不大于 (u,v) 的边权，与 (u,v) 形成环。已知点 u 与点 v 异色，那么 u 到 v 只经过最小生成树上边的路径上必有一条两端异色的边 (u_0,v_0)。(u_0,v_0) 的边权比 (u,v) 小，所以选 (u_0,v_0)（最小生成树上的边）一定更优。

设 \min n_{i,j} 为最小生成树上点 i 的儿子中颜色为 j 的儿子连接点 i 的边权构成的可重集；dis_i 为任意 j（\min n_{i,j} 不为空，i 的颜色不为 j）\min n_{i,j} 中的最小值构成的可重集；ans 为任意 i (dis_i 不为空)dis_i 中的最小值最小值构成的可重集。

建树时。先跑一遍 Kruskal，求出原图的最小生成树，只保留生成树上的边。然后跑 dfs 按照定义求出 \min n_{i,j}，dis_i 和 ans，同时记下每个点的父亲记作 f_i，每个点与父亲相连的边的边权记作 l_i，每个点的颜色记作 v_i。

将点 x 的颜色修改为 j 时，进行一下操作以更新 \min n_{i,j}，dis_i 和 ans：

更新 ans：由于在下面修改了 dis_{f_x}，dis_{f_x} 可能有新的最小值，应该删掉原本的最小值。在 ans 中删除 dis_{f_x} 的最小值。
当 x 与 f_x 异色时，更新 dis_{f_x}：由于在操作 3 中更新了 \min n_{f_x,v_x}，\min n_{f_x,v_x} 可能有新的最小值，而当 x 与 f_x 异色时 \min n_{f_x,v_x} 的最小值对 dis_{f_x} 有贡献，应该删掉原本的最小值。在 dis_{f_x} 中删除 \min n_{f_x,v_x} 的最小值（此时直到更新 v_x 前 v_x 仍是修改前 v_x 的颜色）。
更新 \min n_{f_x,v_x}：由于修改颜色后，x 颜色改变了，按照 \min n_{f_x,v_x} 的定义，l_X，不在 \min n_{f_x,v_x} 里。在 \min n_{f_x,v_x} 中删除 l_x。
当 x 与 f_x 异色时，更新 dis_{f_X}：同 2，由于在操作 3 中更新了 \min n_{f_x,v_x}，\min n_{f_x,v_x} 可能有新的最小值。而当 x 与 f_x 异色时 \min n_{f_x,v_x} 的最小值对 dis_{f_x} 有贡献，应该加上现在的最小值。在 dis_{f_x} 中插入 \min n_{f_x,v_x} 的最小值（此时直到更新 v_x 前 v_x 仍是修改前 v_x 的颜色）。
更新 ans：由于在 6 和 8 中修改了 dis_x，dis_x 可能有新的小值，应该删掉原本的最小值。在 ans 中删除 dis_x 的最小值。
更新 dis_x：由于修改颜色后，x 的颜色可能不为 v_x，那么 x 的子节点中颜色为 v_x 的节点可能可以对 dis_x 产生贡献。在 dis_x 中插入 \min n_{x,v_x} 的最小值。
更新 v_x : 将 v_x 更新为 y。
更新 dis_x：由于修改颜色后，x 的儿子中与 v_x 同色的儿子不能对 dis_x 产生贡献，但之前考虑了它的贡献。在 dis_x 中删除 \min n_{x,v_x} 的最小值。（此后的 v_x 为 x 修改后的颜色）
更新 ans：同 5，由于在 6 和 8 中修改了 dis_x，dis_x 可能有新的小值，应该加上现在的最小值。在 ans 插入 dis_x 的最小值。
当 x 与 f_x 异色时，更新 dis_{f_X}：由于在 11 中修改了 \min n_{f_x,v_x}，\min n_{f_x,v_x} 可能有新的小值，应该删掉原本的最小值。在 dis_{f_X} 中删除 \min n_{f_x,v_x} 的最小值。
更新 \min n_{f_x,v_x}：由于修改颜色后，x 颜色改变了，按照 \min n_{f_x,v_x} 的定义，l_X，在 \min n_{f_x,v_x} 里。在 \min n_{f_x,v_x} 中插入 l_x。
当 x 与 f_x 异色时，更新 dis_{f_X}：由于在 11 中修改了 \min n_{f_x,v_x}，\min n_{f_x,v_x} 可能有新的小值，应该加上现在的最小值。在 dis_{f_X} 插入 \min n_{f_x,v_x} 的最小值。
更新 ans：由于在上面修改了 dis_{f_x}，dis_{f_x} 可能有新的最小值，应该加上现在的最小值。在 ans 插入 dis_{f_x} 的最小值。

code

#include<bits/stdc++.h>
using namespace std;
int n,m,k,q,v[200005],l[200005],fa[200005]/*用于存储并查集中每个节点的父亲*/,f[200005],x,y;
vector<pair<int,int> >mp[200005];
multiset<int>dis[200005],ans;
unordered_map<int,multiset<int> >minn[200005];
//定义见上文
struct edge
{
    int x,y,l;
    bool operator<(const edge t)const{return l<t.l;}    
}e[200005];
int find(int x)
{
    if(fa[x]!=x)fa[x]=find(fa[x]);
    return fa[x];
}
//并查集的实现
void dfs(int x,int fa)
{
    f[x]=fa;
    for(pair<int,int> i:mp[x])if(i.first!=fa) minn[x][v[i.first]].insert(i.second),l[i.first]=i.second,dfs(i.first,x);
    for(auto i:minn[x])if(i.first!=v[x])dis[x].insert(*i.second.begin());
    if(dis[x].size())ans.insert(*dis[x].begin());
}
//按照定义求出 ans,minn[i][j]和dis[i]
int main()
{
    scanf("%d%d%d%d",&n,&m,&k,&q);
    for(int i=1;i<=m;i++)scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].l);
    for(int i=1;i<=n;i++)scanf("%d",&v[i]);
    sort(e+1,e+m+1),iota(fa+1,fa+n+1,1);//此函数的功能是把fa[1],fa[2],...,fa[n]依次赋值为1,2,...,n。
    for(int i=1,cnt=0;i<=m&&cnt<n-1;i++)
        if(find(e[i].x)!=find(e[i].y))
            fa[find(e[i].x)]=find(e[i].y),mp[e[i].x].push_back({e[i].y,e[i].l}),mp[e[i].y].push_back({e[i].x,e[i].l}),cnt++;
    //Kruskal 的过程
    dfs(1,0);
    while(q--)
    {
        scanf("%d%d",&x,&y);
        if(f[x])
        {
            if(dis[f[x]].size())ans.erase(ans.find(*dis[f[x]].begin()));//见上文操作1
            if(v[x]!=v[f[x]])dis[f[x]].erase(dis[f[x]].find(*minn[f[x]][v[x]].begin()));//见上文操作2
            minn[f[x]][v[x]].erase(minn[f[x]][v[x]].find(l[x]));//见上文操作3
            if(v[x]!=v[f[x]]&&minn[f[x]][v[x]].size())dis[f[x]].insert(*minn[f[x]][v[x]].begin());//见上文操作4
        }
        if(dis[x].size())ans.erase(ans.find(*dis[x].begin()));//见上文操作5
        if(minn[x][v[x]].size())dis[x].insert(*minn[x][v[x]].begin());//见上文操作6
        v[x]=y;//见上文操作7
        if(minn[x][v[x]].size()&&dis[x].size())dis[x].erase(dis[x].find(*minn[x][v[x]].begin()));//见上文操作8
        if(dis[x].size())ans.insert(*dis[x].begin());//见上文操作9
        if(f[x])
        {
            if(v[x]!=v[f[x]]&&minn[f[x]][v[x]].size())dis[f[x]].erase(dis[f[x]].find(*minn[f[x]][v[x]].begin()));//见上文操作10
            minn[f[x]][v[x]].insert(l[x]);//见上文操作11
            if(v[x]!=v[f[x]])dis[f[x]].insert(*minn[f[x]][v[x]].begin());//见上文操作12
            if(dis[f[x]].size())ans.insert(*dis[f[x]].begin());//见上文操作13
        }
        printf("%d\n",*ans.begin());
    }
    return 0;
}