【CF1023F】Mobile Phone Network（dsu，MST）

题意：

保证原边以边权单调非减的顺序读入

思路：先把未知边加入，再加入原始边做MST，考虑从大到小，用数据结构维护，每一条原始边相当两个链赋值操作，每一条未知边相当于一个询问，答案即为询问之和

LCT和树剖都能维护

但因为没有强制在线，可以使用并查集维护

考虑做完MST后预处理出深度，父亲，父边权值三个信息

枚举没有用过的原始边，用类似树剖的方法用并查集每次将一个操作中所有的点缩成一个，暴力更改边权

若有未赋值过的边则无解

 #include<cstdio>

 #include<cstring>

 #include<string>

 #include<cmath>

 #include<iostream>

 #include<algorithm>

 #include<map>

 #include<set>

 #include<queue>

 #include<vector>

 #include<bitset>

 using namespace std;

 typedef long long ll;

 typedef unsigned int uint;

 typedef unsigned long long ull;

 typedef pair<int,int> PII;

 typedef vector<int> VI;

 #define fi first

 #define se second

 #define MP make_pair

 #define N      1100000

 #define M      51

 #define MOD 1000000007

 #define eps 1e-8

 #define pi     acos(-1)

 #define oo     1e9

 struct arr

 {

     int x,y,z;

 }a[N];

 struct node

 {

     int x,y;

     node(int a,int b)

     {

         x=a;

         y=b;

     }

 };

 int f[N],g[N],fa[N],dep[N],b[N];

 vector<node>c[N];

 int find(int k)

 {

     if(fa[k]!=k) fa[k]=find(fa[k]);

     return fa[k];

 }

 void dfs(int u)

 {

     dep[u]=dep[f[u]]+;

     for(int i=;i<=(int)c[u].size()-;i++)

     {

         int v=c[u][i].x;

         if(v!=f[u])

         {

             f[v]=u;

             g[v]=c[u][i].y;

             dfs(v);

         }

     }

 }

 int main()

 {

     int n,k,m;

     scanf("%d%d%d",&n,&k,&m);

     for(int i=;i<=n;i++) fa[i]=i;

     for(int i=;i<=k;i++)

     {

         int x,y;

         scanf("%d%d",&x,&y);

         c[x].push_back(node(y,));

         c[y].push_back(node(x,));

         fa[find(x)]=find(y);

     }

     for(int i=;i<=m;i++) scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);

     for(int i=;i<=m;i++)

     {

         int t1=find(a[i].x);

         int t2=find(a[i].y);

         if(t1!=t2)

         {

             fa[t1]=t2;

             c[a[i].x].push_back(node(a[i].y,a[i].z));

             c[a[i].y].push_back(node(a[i].x,a[i].z));

             b[i]=;

         }

     }

     f[]=;

     dfs();

     for(int i=;i<=n;i++) fa[i]=i;

     ll ans=;

     for(int i=;i<=m;i++)

      if(!b[i])

      {

          int x=find(a[i].x),y=find(a[i].y);

          while(x!=y)

          {

              if(dep[x]<dep[y]) swap(x,y);

              if(!g[x])

              {

                  ans+=a[i].z;

                  g[x]=a[i].z;

              }

              fa[x]=find(f[x]);

              x=find(x);

          }

     }

     for(int i=;i<=n;i++)

      if(!g[i])

      {

          printf("-1\n");

          return ;

      }

     printf("%lld\n",ans);

     return ;

 }

巴特西

【CF1023F】Mobile Phone Network（dsu，MST）

最新文章

热门文章