首页 > 代码库 > 洛谷——U10206 Cx的治疗
洛谷——U10206 Cx的治疗
https://www.luogu.org/problem/show?pid=U10206
题目背景
「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。
输入输出样例
输入样例#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：
-1
输入样例#2：
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
输出样例#2：
38
说明
1<=N<=10000,0<=M<=100000；
1<=Ai,Bi,Aj,Bj<=10000;
1<=Cj<=100000;
1<=t<=100000;
1 #include <algorithm> 2 #include <cstdio> 3 4 #define LL long long 5 6 using namespace std; 7 8 const int N(10000+15); 9 const int M(100000+5);10 int n,m,u,v,w;11 12 int cnt;13 struct Edge14 {15 int u,v;16 LL w;17 Edge(int u=0,int v=0,LL w=0):18 u(u),v(v),w(w){}19 }edge[M<<2];20 void ins(int u,int v,int w)21 {22 edge[++cnt]=Edge(u,v,(LL)w);23 }24 25 LL ans;26 int flag,num,fa[N];27 bool cmp(Edge a,Edge b)28 {29 return a.w<b.w;30 }31 int find(int x)32 {33 return x==fa[x]?x:fa[x]=find(fa[x]);34 }35 void K()36 {37 for(int i=1;i<=n;i++) fa[i]=i;38 sort(edge+1,edge+cnt+1,cmp);39 for(int i=1;i<=cnt;i++)40 {41 int fx=find(edge[i].u),fy=find(edge[i].v);42 if(fx==fy) continue;43 num++;44 fa[fx]=fy;45 ans+=edge[i].w;46 if(num==n-1)47 {48 flag=1;49 return ;50 }51 }52 }53 54 int main()55 {56 scanf("%d%d",&n,&m);57 for(int i=1;i<=m;i++)58 {59 scanf("%d%d",&u,&v);60 ins(u,v,w);ins(v,u,w);61 }62 scanf("%d",&m);63 for(int i=1;i<=m;i++)64 {65 scanf("%d%d%d",&u,&v,&w);66 ins(u,v,w); ins(u,v,w);67 }68 K();69 if(!flag) puts("-1");70 else printf("%lld\n",ans);71 return 0;72 }
洛谷——U10206 Cx的治疗
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。