Gym - 101137K kruscal中的dp

题目大意:有一张n个点m条边的无向图。占领第i个点需要ai个人，在第i个点空降一个人需要bi的花费。占领第i条边需要ci个人，当占领某条边后，人便可以在边上自由行走。求占领所有点的最小花费。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fod(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
const int N=3e5+10;
typedef long long ll;
struct Edge{
    ll u,v,c;
    Edge(ll u=0,ll v=0,ll c=0):u(u),v(v),c(c){}
    bool operator < (const Edge &rhs)const {
        return rhs.c>c;
    }   
}e[N];
ll a[N],b[N],sum[N];
int fa[N],n,m;
int fnd(int x){return fa[x]==x?fa[x]:fa[x]=fnd(fa[x]);}
ll solve()
{
    fo(i,1,n) fa[i]=i;
    ll ans=0;
    for(int i=1;i<=m;i++)
    {
        int idx=fnd(e[i].u),idy=fnd(e[i].v);    
        if(idx==idy) continue ;
        ll minb=min(b[idy],b[idx]);
        ll maxa=max(max(a[idx],a[idy]),e[i].c);
        ll tmp=maxa*minb;
        sum[idy]=min(sum[idx]+sum[idy],tmp);
        fa[idx]=idy;
        a[idy]=maxa;
        b[idy]=minb;
    }   
    fo(i,1,n) if(i==fnd(i)) ans+=sum[i];
    return ans;
}
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {   
        fo(i,1,n) {scanf("%lld%lld",&a[i],&b[i]);sum[i]=1ll*a[i]*b[i];}
        for(ll u,v,c,i=1;i<=m;i++) {
            scanf("%lld%lld%lld",&u,&v,&c);
            e[i]=Edge(u,v,c);
        }
        sort(e+1,e+1+m); 
        printf("%lld",solve());
    }
    return 0;
}

最后

以上就是畅快丝袜为你收集整理的Gym - 101137K kruscal中的dp的全部内容，希望文章能够帮你解决Gym - 101137K kruscal中的dp所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。