2 条题解

  • 1
    @ 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;
    }
    
    • 0
      @ 2022-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
      上传者