2 条题解
-
1huangchengfu LV 7 @ 2022-10-23 16:18:39
#include<iostream> #include<fstream> #include<iomanip> #include<stdio.h> #include<cstdio> #include<math.h> #include<cmath> #include<algorithm> #include<string> #include<cstring> #include<string.h> #include<vector> #include<stack> #include<queue> #include<map> #include<set> #include<cstdlib> #include<stdlib.h> #include<ctime> #include<time.h> using namespace std; #define LL long long const int N=1e5+5; const LL INF=0x3f3f3fff3f3f3f; struct node{ LL x,y,z; }p[N],t[N]; LL fa[N],len,n,m; void init(){ for(int i=0;i<=n;i++){ fa[i]=i; } } bool cmp(node a,node b){ if(a.z!=b.z){ return a.z<b.z; } if(a.x!=b.x){ return a.x<b.x; } return a.y<b.y; } int find(int x){ if(fa[x]==x){ return x; } fa[x]=find(fa[x]); return fa[x]; } LL kruskal1(){ LL num=0,sum=0; for(int i=0;i<m;i++){ int x=p[i].x; int y=p[i].y; x=find(x); y=find(y); if(x!=y){ fa[x]=y; num++; t[len].x=p[i].x; t[len].y=p[i].y; t[len].z=p[i].z; len++; sum+=p[i].z; if(num==n-1){ return sum; } } } return INF; } LL kruskal2(LL xx,LL yy,LL zz){ LL num=0,sum=0; for(int i=0;i<m;i++){ LL x=p[i].x; LL y=p[i].y; if(xx==x&&yy==y){ continue; } x=find(x); y=find(y); if(x!=y){ fa[x]=y; num++; sum+=p[i].z; if(num==n-1){ return sum; } } } return INF; } int main(){ /* freopen(".in","r",stdin); freopen(".out","w",stdout); */ cin>>n>>m; init(); for(int i=0;i<m;i++){ cin>>p[i].x>>p[i].y>>p[i].z; if(p[i].x>p[i].y){ swap(p[i].x,p[i].y); } } sort(p,p+m,cmp); LL ans=kruskal1(); LL sum=INF; for(int i=0;i<len;i++){ init(); LL num=kruskal2(t[i].x,t[i].y,t[i].z); if(num<sum&&num>ans){ sum=num; } } cout<<sum<<endl; return 0; }
-
02022-10-23 16:17:31@
/***************************************** Note: ******************************************/ #include <queue> #include <set> #include <math.h> #include <stack> #include <stdio.h> #include <iostream> #include <vector> #include <iomanip> #include <string.h> #include <algorithm> #include <cstdio> #include <cstring> using namespace std; #define LL long long const int N = 1e6 + 10; const LL INF = 1e11+1; struct node{ LL x,y,z; }p[N],t[N]; LL fa[N],len,n,m; void init() { for(int i=0;i<=n;i++) fa[i]=i; } bool cmp(node a,node b) { if(a.z!=b.z) return a.z<b.z; if(a.x!=b.x) return a.x<b.x; return a.y<b.y; } int find(int x) { return (fa[x]==x)?x:fa[x]=find(fa[x]); } LL kruskal1() { LL num=0,sum=0; for(int i=1;i<=m;i++) { int x=find(p[i].x),y=find(p[i].y); if(x!=y) { fa[x]=y; num++; t[++len].x=p[i].x; t[len].y=p[i].y; t[len].z=p[i].z; sum+=p[i].z; if(num==n-1) return sum; } } return INF; } LL kruskal2(LL xx,LL yy,LL zz) { LL num=0,sum=0; for(int i=1;i<=m;i++) { if(xx==p[i].x&&yy==p[i].y) continue; int x=find(p[i].x),y=find(p[i].y); if(x!=y) { fa[x]=y; num++; sum+=p[i].z; if(num==n-1) return sum; } } return INF; } int main() { cin>>n>>m; init(); for(int i=1;i<=m;i++) { cin>>p[i].x>>p[i].y>>p[i].z; if(p[i].x>p[i].y) swap(p[i].x,p[i].y); } sort(p+1,p+m+1,cmp); LL ans=kruskal1(),sum=INF; for(int i=1;i<=len;i++) { init(); LL num=kruskal2(t[i].x,t[i].y,t[i].z); if(num<sum&&num>ans) sum=num; } cout<<sum<<endl; return 0; }
- 1
信息
- ID
- 407
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 7
- 标签
- 递交数
- 80
- 已通过
- 20
- 上传者