Codeforces 1023F Mobile Phone Network

题目链接http://codeforces.com/contest/1023/problem/F

题意:给你一张图,同时有k条边边权未知,你要自己设置,但要保证最小生成树的边包括这k条边权,同时最大化边权和。

思路:见https://blog.csdn.net/u013534123/article/details/81810926?utm_source=blogxgwz0

#include<bits/stdc++.h>
#define MP make_pair
#define PB emplace_back
using namespace std;
typedef long long ll;
template<typename T>
inline T read(T&x){
    x=0;int f=0;char ch=getchar();
    while (ch<'0' || ch>'9') f|=(ch=='-'),ch=getchar();
    while (ch>='0'&& ch<='9') x=x*10+ch-'0',ch=getchar();
    return x=f?-x:x;
}
const int N=5e5+10;
struct Edge{int u,v,w;};
int n,k,m,u,v,w,i,tot,fa[N],f[N],dep[N];
ll ans;
vector<Edge>edge;
vector<pair<int,int> >G[N];
int Find(int x){return x==fa[x]?x:fa[x]=Find(fa[x]);}
void dfs(int u){
    for (int i=0;i<(int)G[u].size();++i){
        int v=G[u][i].first,w=G[u][i].second;
        if (v==f[u]) continue;
        f[v]=u,dep[v]=dep[u]+1;
        if (w) fa[Find(v)]=Find(u);
        dfs(v);
    }
}
int main(){
    read(n),read(k),read(m);
    for (i=1;i<=n;++i) fa[i]=i;
    for (i=1;i<=k;++i){
        read(u),read(v);
        fa[Find(u)]=Find(v);
        G[u].PB(MP(v,0)),G[v].PB(MP(u,0));
    }
    for (i=1;i<=m;++i){
        read(u),read(v),read(w);
        int fu=Find(u),fv=Find(v);
        if (fu^fv){
            fa[fu]=fv;
            G[u].PB(MP(v,1)),G[v].PB(MP(u,1));
        }
        else edge.PB((Edge){u,v,w});
    }
    for (i=1;i<=n;++i) fa[i]=i;
    dfs(1);
    for (i=0;i<(int)edge.size();++i){
        int u=edge[i].u,v=edge[i].v,w=edge[i].w;
        u=Find(u),v=Find(v);
        for (;u^v;){
            ans+=w;
            if (dep[u]>dep[v]) u=fa[u]=Find(f[u]);
            else v=fa[v]=Find(f[v]);
        }
    }
    for (i=1;i<=n;++i) if (Find(i)!=1) return puts("-1"),0;
    printf("%lld\n",ans);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注