「SDOI2014」集合 题解

「SDOI2014」集合 题解

顺手将洛谷上的题解搬运了过来。

简要题意

给定一个 $n$ 个点 $m$ 条边的带权无向图，有 $3$ 个集合 $A$、$B$、$C$，并有 $q$ 次操作：

• 修改操作：给定 $x,S$，将第 $x$ 个点从其所在的集合移动到集合 $S$ 中。
• 查询操作：给定 $S,T$，询问两个端点分别在集合 $S$ 和集合 $T$ 的所有边中最小的边权是多少。

对于前 $50\%$ 的数据，$1\le n\le 100$，$1\le m\le 10000$，$1\le q\le 20000$。
对于后 $50\%$ 的数据，$1\le n\le 100000$，$1\le m\le 500000$，$1\le q\le 100000$，且无向图上任意两个点之间至多能选出 $3$ 条不相交的路径。

题解

这题作为一个省选题，数据强度感人。

这题的正解前 $50\%$ 复杂度为 $O(m+qn\log{m})$，后 $50\%$ 的复杂度为 $O(m+q\log{n})$。但是一方面数据实在太水，一方面近十年来评测机的速度加了不少，十年前也没有 O2，导致：

• 当时边不排序的 $O(qm)$ 暴力只能得到 $20$ 分，现在可以得到 $50$ 分。
• 边排序的 $O(qm)$ 暴力照常理也应该只得 $20$ 分（以现在的评测机速度最多 $50$ 分），但实际上不管在当时还是现在都可以拿到 $100$ 分，并且运行时间暴打正解。
• 复杂度为 $O(m+q\sqrt[]{n}\log{m})$ 的做法应该只能得到 $50$ 分，但是现在的评测机实在是太快了，所以得到了 $100$ 分。

这里把官方题解给一下，实际上在这道题的讨论中就有，但是在讨论中实在是太不显眼了，故我在题解里再写一遍。

对于前 $50\%$ 的部分，$O(qm)$ 暴力是显然的。但实际上我们完全可以开 $6$ 个堆动态维护每两两集合间的答案，这样我们就得到了 $O(m+qn\log{m})$ 的做法。当然，你可以像这篇题解一样对点的度数分类讨论，根据根号分类的传统艺能得到 $O(m+q\sqrt[]{n}\log{m})$ 的做法，但这对提高分数没有帮助。

重点是后 $50\%$ 的数据，他给了一个特殊性质：
无向图上任意两个点之间至多能选出 $3$ 条不相交的路径。

我们来思考这个性质代表的是什么，可以证明至多产生 $3$ 片生成森林。

证明（搬自上面的讨论）：
对于一片生成森林，如果两个点在同一个树上，则他们在树上的路径可以看成是一条增广路。如果将这片森林删除，则这些点之间的最大流至少减 $1$，那么三次之后，任意两点的最大流都为 $0$，即所有边都没了。
$\Box$

这意味着什么呢？我们只需要解决树（森林）的问题，然后把三个答案取个 $\min$ 就好了。

考虑树上怎么做，对于父亲边，可以直接暴力改。对于儿子边，我们发现只有每个集合最小的那条边有用，这也是常数级的。注意此时对于父亲，“每种集合最小的儿子”可能被改了，要判。

这些操作可以用 bfs 序（父亲和儿子在 bfs 序上是连续的）+ 线段树、或者可删除堆、或者 multiset 维护。只不过当时应该是 Pascal，所以 multiset 不能用，堆也要手写就是了。但是本人比较懒，用了 multiset。

修改和查询的复杂度都是 $O(\log{n})$ 的，所以总复杂度为 $O(m+q\log{n})$ 的。

Code

#include <bits/stdc++.h>
#define il inline

int n,m,q; char z[9];

il int Id(int x,int y){if (x>y) std::swap(x,y); return x?(x<2?2+y:3+y):y;}

namespace Sub1
{
    const int N=105;
    
    int b[N],g[N][N]; struct node{int x,y; il friend bool operator < (node x,node y){return g[x.x][x.y]>g[y.x][y.y];}}; std::priority_queue<node> h[6];

    il void main()
    {
        int u,v,w; node x; while (m--) scanf("%d%d%d",&u,&v,&w),(!g[u][v]||g[u][v]>w)&&(g[u][v]=g[v][u]=w);
        for (u=1; u<=n; u++) for (v=1; v<=n; v++) if (g[u][v]) h[0].push({u,v});
        for (scanf("%d",&q); q; q--)
            if (scanf("%s",z),z[0]=='M')
            {
                scanf("%d",&u),b[u]=z[4]-65;
                for (v=1; v<=n; v++) if (g[u][v]) h[Id(b[u],b[v])].push({u,v});
            }
            else
            {
                for (u=Id(z[3]-65,z[4]-65); h[u].size(); h[u].pop())
                    if (x=h[u].top(),Id(b[x.x],b[x.y])==u){printf("%d\n",g[x.x][x.y]); break;}
                if (!h[u].size()) puts("No Found!");
            }
    }
}

namespace Sub2
{
    const int N=1e5+5,M=10*N;

    int b[N],to[M],nx[M],wt[M],hd[N],sze=1; std::multiset<int> S[6]; bool o[N],O[M];
    struct TREE
    {
        int fa[N],fv[N]; std::multiset<int> s[N][3];

        il void Dfs(int u)
        {
            o[u]=1; int i,v;
            for (i=hd[u]; i; i=nx[i]) if (!o[v=to[i]]&&!O[i>>1])
                O[i>>1]=1,fa[v]=u,fv[v]=wt[i],Dfs(v);
        }

        il void Init()
        {
            memset(o,0,n+1); int i;
            for (i=1; i<=n; i++) if (!fa[i]) Dfs(i);
            for (i=1; i<=n; i++) if (fa[i]) s[fa[i]][0].insert(fv[i]);
            for (i=1; i<=n; i++) if (s[i][0].size()) S[0].insert(*s[i][0].begin());
        }

        il void Chg(int c,int x)
        {
            if (b[x]==c) return; int i,j;
            if (fa[x])
            {
                for (i=0; i<3; i++) if (s[fa[x]][i].size()) j=Id(b[fa[x]],i),S[j].erase(S[j].find(*s[fa[x]][i].begin()));
                s[fa[x]][b[x]].erase(s[fa[x]][b[x]].find(fv[x])),s[fa[x]][c].insert(fv[x]);
                for (i=0; i<3; i++) if (s[fa[x]][i].size()) S[Id(b[fa[x]],i)].insert(*s[fa[x]][i].begin());
            }
            for (i=0; i<3; i++) if (s[x][i].size()) j=Id(b[x],i),S[j].erase(S[j].find(*s[x][i].begin())),S[Id(c,i)].insert(*s[x][i].begin());
        }
    }T[3];

    il void Add(int u,int v,int w){to[++sze]=v,nx[sze]=hd[u],wt[sze]=w,hd[u]=sze;}

    il void main()
    {
        int u,v,w; while (m--) scanf("%d%d%d",&u,&v,&w),Add(u,v,w),Add(v,u,w);
        for (w=0; w<3; w++) T[w].Init();
        for (scanf("%d",&q); q; q--)
            if (scanf("%s",z),z[0]=='M') scanf("%d",&u),w=z[4]-65,T[0].Chg(w,u),T[1].Chg(w,u),T[2].Chg(w,u),b[u]=w;
            else S[w=Id(z[3]-65,z[4]-65)].size()?(printf("%d\n",*S[w].begin())):(puts("No Found!"));
    }
}

int main()
{
    scanf("%d%d",&n,&m);

    if (n<101) Sub1::main(); else Sub2::main();

    return 0;
}