Articles8
Tags2
Categories0

CodeForces图论刷题之路 2-1245D. Shichikuji and Power Grid

一道看似很牛逼实际上很sb的最小生成树,绝了。

先对原图建立一个完全图,边权如题所示,再建立一个虚拟源点,每个点和源点都连一条边,权值为建造这个点为发电站的值。然后跑最小生成树。。。艹,这也太sb了。

时间复杂度 O(N2);

代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxe=4e6+50;
const int maxn=2050;
struct node{
    int s,t;
    ll val;
}edge[maxe],ans0[maxn],ans1[maxn];
int bel[maxn];
int vis[maxn];
ll x[maxn],y[maxn],cost[maxn];
int cnt,n,res0,res1;
int cmp(node a,node b){
    return a.val<b.val;
}
int find(int x){
    if(bel[x]!=x){
        return bel[x]=find(bel[x]);
    }
    return x;
}
void merge(int x,int y){
    int fx=find(x);
    int fy=find(y);
    if(fx!=fy){
        bel[max(fx,fy)]=min(fx,fy);
    }
}
void init(){
    for(int i=0;i<=n;i++){
        vis[i]=0;
        bel[i]=i;
    }
    cnt=0;res0=0;res1=0;
}
void add(int a,int b,ll c){
    edge[cnt].s=a;
    edge[cnt].t=b;
    edge[cnt++].val=c;
}
ll kruskal(){
    ll ans=0;
    int count=0;
    sort(edge,edge+cnt,cmp);
    for(int i=0;i<cnt;i++){
        if(find(edge[i].s)!=find(edge[i].t)){
            ans+=edge[i].val;
            merge(edge[i].s,edge[i].t);
            count++;
            if(edge[i].s==0||edge[i].t==0) ans0[++res0]=edge[i];
            else ans1[++res1]=edge[i];
        }
        if(count==n) break;
    }
    return ans;
}
int main(){
    scanf("%d",&n);
    init();
    for(int i=1;i<=n;i++){
        scanf("%lld%lld",&x[i],&y[i]);
    }for(int i=1;i<=n;i++){
        ll x;scanf("%lld",&x);
        add(0,i,x);
    }for(int i=1;i<=n;i++){
        scanf("%lld",&cost[i]);
        for(int j=1;j<i;j++){
            ll c=abs(x[i]-x[j])+abs(y[i]-y[j]);
            c*=(cost[i]+cost[j]);
            add(i,j,c);
        }
    }
    printf("%lld\n",kruskal());
    printf("%d\n",res0);
    for(int i=1;i<=res0;i++){
        printf("%d ",max(ans0[i].s,ans0[i].t));
    }printf("\n%d\n",res1);
    for(int i=1;i<=res1;i++){
        printf("%d %d\n",ans1[i].s,ans1[i].t);
    }
} 
Author:西瓜喵喵.
Link:https//:ForgGYLH.github.io/2019/11/09/graph2/
版权声明:本文采用 CC BY-NC-SA 3.0 CN 协议进行许可