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
          上传者
          1. 关于
          2. 联系我们
          3. 隐私
          4. 服务条款
          5. 版权申诉
          6. Language
          7. Theme
          3. Worker 0 in 19ms
          4. Powered by Hydro v3.15.13 Community