题目背景
「Cx的故事」众所周知,Cx是一个宇宙大犇。由于Cx在空中花园失足摔下,导致他那蕴含着无穷智慧的大脑受到了严重的损伤,许多的脑神经断裂。于是,Cx的wife(有么?)决定请巴比伦最好的医师治疗。但是,Cx的wife是个十分吝啬的人,虽然她想将Cx治好,但是她又不肯出过多的钱,而脑神经的重新连接需要大量的花费。所以,当她知道来自未来的你时,她恳求你去帮她计算一下如何才能将Cx的神经元全部重新连接起来,而花费最小。
题目描述
神经网络就是一张无向图,图中的节点称为神经元,神经元已经按照1~N的顺序排好号,而且两个神经元之间至多有一条脑神经连接。
现有N个神经元,M条仍然完好的脑神经,连接神经元Ai与Bi。
医生给出能够连接的t条脑神经,分别连接神经元Aj与Bj,并给出连接所需的花费Ci。
请编写程序计算将所有神经元连通的最小花费w。
输入输出格式
输入格式:
第一行为两个整数N,M (1<=N<=10000,1<=M<=100000) 表示一共有N个神经元,有M条依旧完好的脑神经。
接下来M行每行有两个整数Ai,Bi (1<=Ai,Bi<=10000) 表示神经元Ai,Bi已经连在一起。
接下来一行有一个整数t (1<=t<=10000)表示医生能连接的神经个数。
接下来t 行有三个整数 Aj ,Bj ,Cj (1<=Ai,Bi,Cj<=10000) 表示神经元Aj,Bj能通过Cj的花费将其连在一起。
输出格式:
仅一行,为一个整数,表示将Cx的神经元连通起来的最小花费w。若不能将其全部连通,请输出-1。
输入输出样例
10 51 52 63 73 83 9102 4 103 6 152 4 92 6 345 7 642 8 263 7 165 2 73 9 138 5 12
-1
10 51 52 63 73 83 9108 10 103 6 152 4 92 6 345 7 642 8 263 7 165 2 73 9 138 5 12
38
说明
1<=N<=10000,0<=M<=100000;
1<=Ai,Bi,Aj,Bj<=10000;
1<=Cj<=100000;
1<=t<=100000;
最小生成树
#include#include #include #define N 100005using namespace std;void read(int &x){ x=0; char ch=getchar(); while(!isdigit(ch)) ch=getchar(); while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}}int fa[N<<1],cnt,t,m,n,dis[N<<1];struct node{ int x,y,z; bool operator<(node a)const { return z