4 条题解

  • 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
        @ 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;
        }
        
        • 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
          标签
          递交数
          41
          已通过
          25
          上传者