Mobile Phone Network CodeForces - 1023F（并查集lca+修改环）

题意：

 　　就是有几个点，你掌控了几条路，你的商业对手也掌控了几条路，然后你想让游客都把你的所有路都走完，那么你就有钱了，但你又想挣的钱最多，真是的过分。。哈哈

　　游客肯定要对比一下你的对手的路 看看那个便宜 就走哪个，（你的路的价钱和对手相等时 优先走你的）；

　思路想到了 但写不出来。。。真的有点巧妙了

　　用并查集来记录环路  如果两个点不能加入到并查集，那么肯定是加入这两个点后就构成了一个环路  记录下构成环路的u和v两点 其它点加入并查集 并加入到邻接表

dfs走一遍 记录下每个点的父结点 和 每个点的等级  用于找lca

　之后 遍历没加入到并查集的u 和 v，找它们的lca  在找lca的路上同时修改 边的权值 使这两个点 到lca的路上的边的权值等于 这两个点之间的权值（没加入到并查集的边）

　为什么？画画图。。在u 到 v的这条路上只要你的边有一条比你的对手的贵。。那游客肯定不走你的呀

　so就修改一下  并再次用并查集记录  那么当有重复的u 或 v 时  已经修改过的边就不会再修改了（题中保证输入时边的权值从小到大输入）

 

#include <bits/stdc++.h>
#define mem(a, b) memset(a, b, sizeof(a))
#define rap(i, a, n) for(int i=a; i<=n; i++)
#define rep(i, a, n) for(int i=a; i<n; i++)
#define lap(i, a, n) for(int i=n; i>=a; i--)
#define lep(i, a, n) for(int i=n; i>a; i--)
#define rd(a) scanf("%d", &a)
#define rlld(a) scanf("%lld", &a)
#define rc(a) scanf("%c", &a)
#define rs(a) scanf("%s", a)
#define pd(a) printf("%d\n", a);
#define plld(a) printf("%lld\n", a);
#define pc(a) printf("%c\n", a);
#define ps(a) printf("%s\n", a);
#define MOD 2018
#define LL long long
#define ULL unsigned long long
using namespace std;
const int maxn = 500010, INF = 0x7fffffff;
int n, m, k, cnt;
int head[maxn], ans;
int f[maxn], fa[maxn], pre[maxn], res[maxn], d[maxn];

void init()
{
    mem(head, -1);
    cnt = ans = 0;
}

int find(int x)
{
    return f[x] == x?x:(f[x]=find(f[x]));
}

struct node
{
    int u, v, ty, next;
}Node[maxn<<1];

struct edge
{
    int u, v, w;
}Edge[maxn<<1];

void add_edge(int u, int v, int w)
{
    Edge[ans].u = u;
    Edge[ans].v = v;
    Edge[ans++].w = w;
}


void add_(int u, int v, int ty)
{
    Node[cnt].u = u;
    Node[cnt].v = v;
    Node[cnt].ty = ty;
    Node[cnt].next = head[u];
    head[u] = cnt++;
}

void add(int u, int v, int ty)
{
    add_(u, v, ty);
    add_(v, u, ty);
}

void dfs(int u)
{
    for(int i=head[u]; i!=-1; i=Node[i].next)
    {
        node e = Node[i];
        if(e.v == pre[u]) continue;
        pre[e.v] = u;
        d[e.v] = d[u] + 1;
//        cout<< u << "  " << e.v <<endl;
        dfs(e.v);
    }    
}

int main()
{
    init();
    rd(n), rd(m), rd(k);
    int u, v, w;
    for(int i=0; i<=n; i++)
        f[i] = i;
    
    for(int i=0; i<m; i++)
    {
        rd(u), rd(v);
        add(u, v, 0);
        f[find(u)] = find(v);
    }
    for(int i=0; i<k; i++)
    {
        rd(u), rd(v), rd(w);
        int l = find(u);
        int r = find(v);
        if(l == r) add_edge(u, v, w);
        else f[l] = r, add(u, v, 1);
    }
    dfs(1);
//    cout<< 111 <<endl;
    for(int i=0; i<=n; i++) f[i] = i;
    for(int i=0; i<ans; i++)
    {
        int r = find(Edge[i].u), l = find(Edge[i].v);
        while(r != l)
        {
            if(d[r] > d[l]) res[r] = Edge[i].w, f[r] = find(pre[r]), r = f[r];
            else res[l] = Edge[i].w, f[l] = find(pre[l]), l = f[l];    
        }
    }
    LL sum = 0;
    for(int i=1; i<=n; i++)
    {
        for(int j=head[i]; j!=-1; j=Node[j].next)
        {
            node e = Node[j];
            if(e.v == pre[i] && e.ty == 0)
            {
                if(f[i] == i)
                {
                    puts("-1");
                    return 0;
                }
                sum += res[i];
            }
        }
    }

    printf("%lld\n",sum);
    return 0;
}