4 条题解

  • 2
    @ 2022-3-7 20:50:34

    kruskal

    #include<iostream>
    #include<cstdio>
    #include<cmath>
    #include<cstdlib>
    #include<cstring>
    #include<algorithm>
    #include<queue>
    using namespace std;
    int n,sum,cnt,num=0;
    int fa[110];
    struct node{
        int x,y,z;
    }edg[26000];
    void init(){
    	for(int i=1;i<=n;i++)
    		fa[i] = i;
    }
    bool cmp(node a ,node b)
    {
    	return a.z < b.z;
    }
    int find(int x){
    	return x==fa[x] ? fa[x] : fa[x]=find(fa[x]);
    }
    void kruskal(){
    	sum = cnt = 0;
    	sort(edg+1,edg+1+num,cmp);
    
    	// for(int i=1;i<=num;i++){
    	// 	cout<<edg[i].x<<"  "<<edg[i].y<<"  "<<edg[i].z<<endl;
    	// }
    	for(int i = 1 ;i <= num ; i++)
    	{
    		int x =  find(edg[i].x);
    		int y =  find(edg[i].y);
    		if(x!=y)
    		{
    			sum += edg[i].z;
    			// cout<<i<<" "<<edg[i].z<<" /// "<<endl;
    			cnt++;
    			fa[x] = y;
    			if(cnt == n-1)
    				break;
    		}
    	}
        cout<<sum<<endl;
    }
    int main(){
        while(cin>>n&&n){
    		num = 0;
    		memset(edg,0,sizeof(edg));
    		char p,pp;
    		int k;
    		for(int i=1;i<n;i++){
    			cin>>p;
    			cin>>k;
    			for(int j=1;j<=k;j++){
    				cin>>pp;
    				edg[++num].x = p-'A' + 1;
    				edg[num].y = pp-'A' + 1;
    				cin>>edg[num].z;
    				num++;
    			}
    			if(k) num--;
    		}
    		
    		init();
    
    		kruskal();
    	}
        return 0;
    }
    
    • 2
      @ 2022-3-6 18:26:06
      /*
      #include<iostream>
      #include<cstring>
      #include<cmath>
      #include<vector>
      #include<queue>
      #include<deque>
      #include<cstdio>
      #include<algorithm>
      #include<string>
      #include<list>
      #define int long long
      #define itn int
      #pragma GCC optimize(3)
      #pragma GCC optimize(2)
      #pragma GCC target("avx")
      #pragma GCC optimize("Ofast")
      #pragma GCC optimize("inline")
      #pragma GCC optimize("-fgcse")
      #pragma GCC optimize("-fgcse-lm")
      #pragma GCC optimize("-fipa-sra")
      #pragma GCC optimize("-ftree-pre")
      #pragma GCC optimize("-ftree-vrp")
      #pragma GCC optimize("-fpeephole2")
      #pragma GCC optimize("-ffast-math")
      #pragma GCC optimize("-fsched-spec")
      #pragma GCC optimize("unroll-loops")
      #pragma GCC optimize("-falign-jumps")
      #pragma GCC optimize("-falign-loops")
      #pragma GCC optimize("-falign-labels")
      #pragma GCC optimize("-fdevirtualize")
      #pragma GCC optimize("-fcaller-saves")
      #pragma GCC optimize("-fcrossjumping")
      #pragma GCC optimize("-fthread-jumps")
      #pragma GCC optimize("-funroll-loops")
      #pragma GCC optimize("-fwhole-program")
      #pragma GCC optimize("-freorder-blocks")
      #pragma GCC optimize("-fschedule-insns")
      #pragma GCC optimize("inline-functions")
      #pragma GCC optimize("-ftree-tail-merge")
      #pragma GCC optimize("-fschedule-insns2")
      #pragma GCC optimize("-fstrict-aliasing")
      #pragma GCC optimize("-fstrict-overflow")
      #pragma GCC optimize("-falign-functions")
      #pragma GCC optimize("-fcse-skip-blocks")
      #pragma GCC optimize("-fcse-follow-jumps")
      #pragma GCC optimize("-fsched-interblock")
      #pragma GCC optimize("-fpartial-inlining")
      #pragma GCC optimize("no-stack-protector")
      #pragma GCC optimize("-freorder-functions")
      #pragma GCC optimize("-findirect-inlining")
      #pragma GCC optimize("-fhoist-adjacent-loads")
      #pragma GCC optimize("-frerun-cse-after-loop")
      #pragma GCC optimize("inline-small-functions")
      #pragma GCC optimize("-finline-small-functions")
      #pragma GCC optimize("-ftree-switch-conversion")
      #pragma GCC optimize("-foptimize-sibling-calls")
      #pragma GCC optimize("-fexpensive-optimizations")
      #pragma GCC optimize("-funsafe-loop-optimizations")
      #pragma GCC optimize("inline-functions-called-once")
      #pragma GCC optimize("-fdelete-null-pointer-checks")
      #pragma GCC optimize("Ofast", "inline", "-ffast-math")
      #pragma GCC target("avx,sse2,sse3,sse4,mmx")
      #pragma GCC optimize("-fgcse")
      #define DEBUG printf("Baylor AK IOI\n");
      #pragma GCC optimize("Ofast,unroll-loops,fast-math")
      #pragma GCC target("ssse3","sse3","sse2","sse","avx2","avx")
      #pragma GCC optimize("Ofast","-funroll-loops","-fdelete-null-pointer-checks")
      using namespace std;
      int n,top,f[100],sum;
      struct node {
      	int x,y,w;
      }a[100];
      void init(){
      	for(int i=1;i<=500;i++){
      		f[i]=i;
      		a[i].x=0,a[i].y=0,a[i].w=0;
      	}
      }
      int find(int x){
      	if(f[x]==x){
      		return f[x];
      	}
      	else return f[x]=find(f[x]);
      }
      int cmp(node xx,node yy){
      	return xx.w<yy.w;
      }
      signed main(){
      	while(1){
      		sum=0;
      		cin>>n;
      		init();
      		top=0;
      		if(n==0)return 0;
      		for(int i=1;i<n;i++){
      			char xx,yy;
      			int m;
      			cin>>xx;
      			int x,y,z;
      			x=xx-'A'+1;
      			cin>>m;
      			while(m--){
      				cin>>yy>>z;
      				y=yy-'A'+1;
      				a[++top]=(node){x,y,z};
      			}
      		}
      		sort(a+1,a+n+1,cmp);
      		for(int i=1;i<=top;i++){
      			int xx=find(a[i].x);
      			int yy=find(a[i].y);
      			if(xx!=yy){
      				f[xx]=yy;
      				sum+=a[i].w;
      			}
      		}
      		printf("%lld\n",sum);
      	}
      	return 0;
      }
      */
      #include<iostream>
      #include<cstring>
      #include<cmath>
      #include<vector>
      #include<queue>
      #include<deque>
      #include<cstdio>
      #include<algorithm>
      #include<string>
      #include<list>
      #define int long long
      #define itn int
      #pragma GCC optimize(3)
      #pragma GCC optimize(2)
      #pragma GCC target("avx")
      #pragma GCC optimize("Ofast")
      #pragma GCC optimize("inline")
      #pragma GCC optimize("-fgcse")
      #pragma GCC optimize("-fgcse-lm")
      #pragma GCC optimize("-fipa-sra")
      #pragma GCC optimize("-ftree-pre")
      #pragma GCC optimize("-ftree-vrp")
      #pragma GCC optimize("-fpeephole2")
      #pragma GCC optimize("-ffast-math")
      #pragma GCC optimize("-fsched-spec")
      #pragma GCC optimize("unroll-loops")
      #pragma GCC optimize("-falign-jumps")
      #pragma GCC optimize("-falign-loops")
      #pragma GCC optimize("-falign-labels")
      #pragma GCC optimize("-fdevirtualize")
      #pragma GCC optimize("-fcaller-saves")
      #pragma GCC optimize("-fcrossjumping")
      #pragma GCC optimize("-fthread-jumps")
      #pragma GCC optimize("-funroll-loops")
      #pragma GCC optimize("-fwhole-program")
      #pragma GCC optimize("-freorder-blocks")
      #pragma GCC optimize("-fschedule-insns")
      #pragma GCC optimize("inline-functions")
      #pragma GCC optimize("-ftree-tail-merge")
      #pragma GCC optimize("-fschedule-insns2")
      #pragma GCC optimize("-fstrict-aliasing")
      #pragma GCC optimize("-fstrict-overflow")
      #pragma GCC optimize("-falign-functions")
      #pragma GCC optimize("-fcse-skip-blocks")
      #pragma GCC optimize("-fcse-follow-jumps")
      #pragma GCC optimize("-fsched-interblock")
      #pragma GCC optimize("-fpartial-inlining")
      #pragma GCC optimize("no-stack-protector")
      #pragma GCC optimize("-freorder-functions")
      #pragma GCC optimize("-findirect-inlining")
      #pragma GCC optimize("-fhoist-adjacent-loads")
      #pragma GCC optimize("-frerun-cse-after-loop")
      #pragma GCC optimize("inline-small-functions")
      #pragma GCC optimize("-finline-small-functions")
      #pragma GCC optimize("-ftree-switch-conversion")
      #pragma GCC optimize("-foptimize-sibling-calls")
      #pragma GCC optimize("-fexpensive-optimizations")
      #pragma GCC optimize("-funsafe-loop-optimizations")
      #pragma GCC optimize("inline-functions-called-once")
      #pragma GCC optimize("-fdelete-null-pointer-checks")
      #pragma GCC optimize("Ofast", "inline", "-ffast-math")
      #pragma GCC target("avx,sse2,sse3,sse4,mmx")
      #pragma GCC optimize("-fgcse")
      #define DEBUG printf("Baylor AK IOI\n");
      #pragma GCC optimize("Ofast,unroll-loops,fast-math")
      #pragma GCC target("ssse3","sse3","sse2","sse","avx2","avx")
      #pragma GCC optimize("Ofast","-funroll-loops","-fdelete-null-pointer-checks")
      using namespace std;
      int top,id,minn,sum,head[100005],to[100005],ne[100005],dis[100005],vis[100005],w[1000005],n;
      void add(int x,int y,int z){
      	to[++top]=y;
      	w[top]=z;
      	ne[top]=head[x],head[x]=top;
      	return;
      } 
      inline int prim(){
      	memset(dis,0x3f,sizeof(dis));
      	dis[1]=0;
      	sum=0;
      	for(int i=1;i<=n;i++){
      		id=-1,minn=100000;
      		for(int j=1;j<=n;j++){
      			if(!vis[j]&&dis[j]<minn){
      				minn=dis[j];
      				id=j;
      			}
      		}
      		vis[id]=1;
      		sum+=minn;
      		for(int j=head[id];j;j=ne[j]){
      			if(!vis[to[j]]&&w[j]<dis[to[j]]){
      				dis[to[j]]=w[j];
      			}
      		}
      	}
      	return sum;
      }
      signed main(){
      	while(1){
      		sum=0;
      		cin>>n;
      		top=0;
      		memset(head,0, sizeof(head));
      		memset(to,0, sizeof(to));
      		memset(w,0, sizeof(w));
      		memset(ne,0, sizeof(ne));
      		memset(vis,0, sizeof(vis));
      		if(n==0)return 0;
      		for(int i=1;i<n;i++){
      			char xx,yy;
      			int m,orz;
      			cin>>xx;
      			int x=xx-'A'+1;
      			cin>>m;
      			for(int j=1;j<=m;j++){
      				cin>>yy;
      				int y=yy-'A'+1;
      				cin>>orz;
      				add(x,y,orz);
      				add(y,x,orz);
      			}
      			
      		}
      		int s=prim();
      		printf("%lld\n",s);
      	}
      	return 0;
      }
      //register
      //unsigned
      //system("pause");
      //system("cls");
      //system("color OA");   0b  fc 75
      
      • 1
        @ 2022-10-23 15:31:00

        kruskal

        /*****************************************
        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 int INF = 0x3f3f3f3f;
        int n,m,fa[N];
        struct node{
        	int a,b,dis;
        }p[N];
        void init()
        {
        	for(int i=1;i<=n;i++)
        		fa[i]=i;
        }
        int find(int x)
        {
        	return (fa[x]==x)?x:fa[x]=find(fa[x]);
        }
        bool cmp(node a,node b)
        {
        	return a.dis<b.dis;
        }
        void kruskal()
        {
        	int sum=0,cnt=0;
        	for(int i=1;i<=m;i++)
        	{
        		if(cnt==n-1) break;
        		int x=find(p[i].a),y=find(p[i].b);
        		if(x!=y)
        		{
        			cnt++;
        			sum+=p[i].dis;
        			fa[x]=y;
        		}
        	}
        	cout<<sum<<endl;
        }
        int main()
        {
        	while(cin>>n&&n)
        	{
        		init();
        		memset(p,0,sizeof p);
        		for(int i=1;i<n;i++)
        		{
        			char q,tmp;
        			int k;
        			cin>>q>>k;
        			for(int j=1;j<=k;j++){
        				cin>>tmp;
        				p[++m].a = q-'A' + 1;
        				p[m].b = tmp-'A' + 1;
        				cin>>p[m].dis;
        				m++;
        			}
        			if(k) m--;
        		}
        		sort(p+1,p+m+1,cmp);
        		kruskal();
        	}
        	return 0;
        }
        
        • 1
          @ 2021-10-10 17:13:12
          #include <math.h>
          #include <stdio.h>
          #include <iostream>
          #include <string.h>
          #include <algorithm>
          using namespace std;
          const int N = 5000;
          int n;
          int head[N],w[N],ne[N],to[N],idx = 0,dis[N], vis[N];
          void init()
          {
              memset(dis,0x3f,sizeof(dis));
              memset(vis,-1,sizeof(vis));
              memset(head , 0 , sizeof(head));
              memset(w , 0 , sizeof(w));
              memset(ne , 0 , sizeof(ne));
              memset(to, 0 , sizeof(to));
              idx = 0;
          }
          void add(int x , int y , int z)
          {
              x = x - 64;
              y = y - 64;
              w[++idx] = z;
              ne[idx] = head[x];
              to[idx] = y;
              head[x] = idx;
          }
          
          int prim()
          {
              vis[1] = 0;
              dis[1] = 0;
              for(int i = head[1] ; i  ; i = ne[i])
                  dis[to[i]] = w[i];
              int num = 0;
              int sum = 0;
              while(1)
              {
                  int minn = 0x3f3f3f3f;
                  int id = 0;
                  for(int i = 1 ;i <= n ; i++)
                  {
                      if(vis[i] && dis[i] < minn) 
                      {
                          minn = dis[i];
                          id = i;
                      }
                  }
                  if(id == 0)
                  {
                      return sum;
                  }
                  vis[id] = 0;
                  sum += minn;
                  num++;
                  for(int i = head[id] ; i ; i = ne[i])
                  {
                      if(vis[to[i]] && dis[to[i]] > w[i])
                          dis[to[i]] = w[i];
                  }
              }
              return sum;
          }
          int main()
          {
              while(scanf("%d",&n)&& n)
              {
                  
                  init();
                  for(int i = 1 ;i < n ; i++)
                  {
                      getchar();
                      char x;
                      int t;
                      cin >> x >> t;
                      while(t--)
                      {
                          char c;
                          int num;
                          cin >> c >> num;
                          add(x,c,num);
                          add(c,x,num);
                      }
                  }
                  printf("%d\n",prim());
          
              }
              return 0;
          }
          
          • 1

          信息

          ID
          1326
          时间
          1000ms
          内存
          256MiB
          难度
          3
          标签
          递交数
          40
          已通过
          24
          上传者