蒟蒻的小窝

蒟蒻的小窝

题解 P5805 【[SEERC2019]Graph and Cycles】

posted on 2020-09-26 13:58:00 | under 题解 |

贪心的小题,一个顶点出去的 $2$ 条边,再抓一条边立马就是环。

$N$ 是奇数,那么每个顶点出去偶数条边, 不管和谁构成圈,按照由小到大的顺序对每个顶点出去的边权排序,相邻两个在同一个圈里,只有这样才能导致最后最小。

Code:

#include<bits/stdc++.h>
#define LL long long
#define maxn 1005
#define maxe 1000005
using namespace std;
int N,M,cnt,lnk[maxn],nxt[maxe],w[maxe];
LL Ans;
struct ZS{
    int x,y,w;
    bool operator <(const ZS &B)const{return w<B.w;}
}A[maxe];
int read(){
    int ret=0,f=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-')f=-f;ch=getchar();}
    while (isdigit(ch)) ret=(ret<<3)+(ret<<1)+(ch&15),ch=getchar();
    return ret*f;
}
void add_e(int x,int y,int z){w[++cnt]=z;nxt[cnt]=lnk[x];lnk[x]=cnt;} 
int main(){
    freopen("cycles.in","r",stdin);
    freopen("cycles.out","w",stdout);
    N=read();M=N*(N-1)/2;
    for (int i=1;i<=M;i++) A[i].x=read(),A[i].y=read(),A[i].w=read();
    sort(A+1,A+1+M);
    for (int i=1;i<=M;i++){
        int x=A[i].x,y=A[i].y,z=A[i].w;
        add_e(x,y,z),add_e(y,x,z);
    }
    for (int i=1;i<=N;i++)
    for (int j=lnk[i];j;){
        int w_one=w[j];j=nxt[j];
        int w_two=w[j];j=nxt[j];
        Ans+=max(w_one,w_two);
    }
    printf("%lld\n",Ans);
    return 0;
}