毛豆

用户名：liuyt

访问量：16842

签　名：

等　　级
排　　名	1025
经　　验	3310
参赛次数	3
文章发表	34
年　　龄	22
在职情况	学生
学　　校	燕山大学
专　　业	计算机

　　自我简介：

TA的其他文章

肺炎大作战-题解(C++代码)
浏览：186

你可能喜欢

C语言程序设计教程（第三版）课后习题11.5 （C语言代码）

ysu情报问题解析

　　作者: 毛豆　　　　发表时间：2019-10-05 13:10:14 浏览：342　|　评论：0　

Brotherhood在燕大建立了分部，但由于燕大人杰地灵，不是什么人都能够任意进出的，于是现在一个棘手的问题摆在了Ezio面前：情报的传递。

已知燕大内的Brotherhood一共有n个团体，有些团体之间有一些关系，你可以把它们看作一条边，每条边连接了两个不同的团体，现在一共有m条边。

现在前辈Jumbo要求Ezio将一个情报传递给燕大内的所有团体。已知Ezio亲自去向团体i告知情报的代价为val[i]。Ezio当然不想一个一个去找啦，他还有很多任务要完成，于是他发现他可以利用团体之间的关系，让某一个已经被传达过情报的团体去告知另一与之有关系团体。

但是团体内部的人懒癌发作，自然不想白白地去帮Ezio跑腿。具体来说，针对关系(u,v)，如果Ezio想要利用它，应该付出的代价为cost(u,v)。

现在Ezio想要花费最少的代价，你能帮帮他吗？

输入格式:
注意：输入包括多组测试用例。

第一行一个整数t，表示测试用例组数。

对于每组测试用例：

第一行两个用空格隔开的整数n和m，分别表示团体个数和关系数量。

接下来一行n个用空格隔开的数，第i个数表示val[i]。

接下来m行，每行三个用空格隔开的整数u,v和cost(u,v)。

输出格式:
对于每组测试用例，你的程序需要输出一行一个整数表示询问的答案。

输入样例:
在这里给出一组输入。例如：

2
5 8
2 8 5 1 10
1 2 5
1 3 9
3 4 5
2 5 6
3 2 2
1 3 8
5 3 4
4 1 8
5 8
7 2 9 10 3
1 2 8
1 3 6
1 4 4
2 5 3
4 5 2
2 4 9
3 5 3
5 4 2
输出样例:
在这里给出相应的输出。例如：

14
14
样例说明
第一组测试用例中，Ezio可以直接将情报传递给1,4号团体，花费分别为2,1。

然后利用关系(4,3),(3,5),(3,2)，花费分别为5,4,2。

/*本题可以ac    经验结论，利用并查集求最小生成树的时候最好弄个有向图   不仅节省空间 还和无向图结果一样
    */
    #include<bits/stdc++.h>
    using namespace std;
    const int N=2e5+100;
    struct edge{
    	int u,v,w;
    }edge[N]; 
    int f[N];
    int t,n,m;
    int find(int x)
    {
    	if(x!=f[x])
    	{
    		f[x]=find(f[x]);
    	}
    	return f[x];
    }
    bool cmp(struct edge x,struct edge y)
    {
    	return x.w<y.w;
    }
    int main()
    {
    	cin>>t;
    	while(t--)
    	{
    		long long res=0;
    		cin>>n>>m;
    		for(int i=1;i<=n+1;i++)
    		{
    			f[i]=i;
    		}
    		int k=0;
    		for(int i=1;i<=n;i++)
    		{
    			int a;
    			cin>>a;
    			edge[k].u=i;
    			edge[k].v=n+1;
    			edge[k].w=a;
    			k++;
    			/*
    			edge[k].u=n+1;
    			edge[k].v=i;
    			edge[k].w=a;
    			k++;
    			*/
    			
    		}
    		
    		for(int i=0;i<m;i++)
    		{
    			int a,b,c;
    			cin>>a>>b>>c;
    			edge[k].u=a,edge[k].v=b,edge[k].w=c;
    			k++;
    		/*	edge[k].u=b,edge[k].v=a,edge[k].w=c;
    			k++;
    			*/
    			//
    		    /*a=find[a];
    		    b=find[b];
    		    if(a!=b)
    		    {
    		    	f[a]=b;
    			}
    			*/
    		}
    		sort(edge,edge+k,cmp);
    		for(int i=0;i<k;i++)
    		{
    			int a=edge[i].u;
    			int b=edge[i].v;
    			a=find(a);
    			b=find(b);
    			if(a!=b)
    			{
    				f[a]=b;
    				res+=edge[i].w;
    			}
    		}
    		cout<<res<<endl;
    	}
    }

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

毛豆

TA的其他文章

你可能喜欢

校门外的树（C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题11.5 （C语言代码）

字符串的输入输出处理（C语言代码）

C语言程序设计教程（第三版）课后习题6.7 （C语言代码）

ysu情报问题解析

评论区

精彩推荐

点我有惊喜！你懂得！

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

数组输出（C语言代码）--此题的题目描述有问题

C语言程序设计教程（第三版）课后习题5.6 （C语言代码）

WU-C语言程序设计教程（第三版）课后习题11.12 （C++代码）（想学链表的小伙伴可以看看）

用筛法求之N内的素数。（C语言代码）

1014题解

企业奖金发放（C语言代码）

1196题解

WU-C语言程序设计教程（第三版）课后习题5.5 （C语言代码）

毛豆

TA的其他文章

你可能喜欢

校门外的树 （C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题11.5 （C语言代码）

字符串的输入输出处理 （C语言代码）

C语言程序设计教程（第三版）课后习题6.7 （C语言代码）

ysu情报问题解析

评论区

精彩推荐

点我有惊喜！你懂得！

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

数组输出 （C语言代码）--此题的题目描述有问题

C语言程序设计教程（第三版）课后习题5.6 （C语言代码）

WU-C语言程序设计教程（第三版）课后习题11.12 （C++代码）（想学链表的小伙伴可以看看）

用筛法求之N内的素数。 （C语言代码）

1014题解

企业奖金发放 （C语言代码）

1196题解

WU-C语言程序设计教程（第三版）课后习题5.5 （C语言代码）

校门外的树（C语言代码）

字符串的输入输出处理（C语言代码）

　　评论区

数组输出（C语言代码）--此题的题目描述有问题

用筛法求之N内的素数。（C语言代码）

企业奖金发放（C语言代码）