基础图论 局域网(net)+还是畅通工程+建设电力系统

kruskal 贪心板子

（1） 将全部边按照权值由小到大排序。 （2） 按顺序（边权由小到大的顺序）考虑每条边，只要这条边和我们已经选择的边不构成圈，就保留这条边，否则放弃这条边。

//先定义一个结构体 //边的含义是从u到v权重为c struct EDGE{ int u,v,c; }; //sort重载cmp方法 bool cmp(EDGE a,EDGE b){ return；//根据要求写 } //用并查集直接把连起来的边看作一个整体 void init(){ for(int i = 0 ;i <= 500 ;i++) pre[i]=i; } int fin(int x){ return pre[x]==x?x:pre[x]=fin(pre[x]); } //然后根据要求遍历边就行了

---

局域网(net)

时间限制: 1 Sec 内存限制: 128 MB 提交: 100 解决: 21

题目描述

某个局域网内有n(n≤100)台计算机，由于搭建局域网时工作人员的疏忽，现在局域网内的连接形成了回路，我们知道如果局域网形成回路那么数据将不停的在回路内传输，造成网络卡的现象。因为连接计算机的网线本身不同，所以有一些连线不是很畅通，我们用f(i,j)表示i,j之间连接的畅通程度(f(i,j)≤1000)，f(i,j)值越小表示i,j之间连接越通畅，f(i,j)为0表示i,j之间无网线连接。现在我们需要解决回路问题，我们将除去一些连线，使得网络中没有回路，并且被除去网线的Σf(i,j)最大，请求出这个最大值。

输入

第一行两个正整数n k

接下来的k行每行三个正整数i j m表示i,j两台计算机之间有网线联通，通畅程度为m。

输出

一个正整数，Σf(i,j)的最大值。

样例输入

5 5 1 2 8 1 3 1 1 5 3 2 4 5 3 4 2

样例输出

8

大声BB

求的是Σf(i,j)的最大值，换言之就是全部的权重和减去最小生成树的和，所以—完

#include <stdio.h> #include <iostream> #include <string.h> #include <algorithm> using namespace std; #define ll long long const int INF=1<<30; const int N=1000002; int pre[105]; struct EDGE{ int u,v,c; }; struct EDGE edge[100005],anse[105]; bool cmp1(EDGE a,EDGE b){ return a.c<b.c; } bool cmp2(EDGE a,EDGE b){ if(a.u == b.u) return a.v<b.v; return a.u<b.u; } void init(){ for(int i = 0 ;i <= 100 ;i++) pre[i]=i; } int fin(int x){ return pre[x]==x?x:pre[x]=fin(pre[x]); } int main() { int n,e; scanf("%d %d",&n,&e); int sum = 0; for(int i = 0 ;i < e; i++){ scanf("%d %d %d",&edge[i].u,&edge[i].v,&edge[i].c); sum+=edge[i].c; } init(); sort(edge,edge+e,cmp1); int cnt = 0; int ans = 0; for(int i = 0 ;i < e ;i++){ int a = fin(edge[i].u); int b = fin(edge[i].v); if(a!=b){ pre[a] = b; ans+=edge[i].c; cnt++; } } printf("%d\n",sum-ans); return 0; }

---

还是畅通工程

时间限制: 1 Sec 内存限制: 128 MB 提交: 231 解决: 175

题目描述

浙江大学研究生复试题：某省调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可），并要求铺设的公路总长度为最小。请计算最小的公路总长度。

输入

测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( < 100 )；随后的N(N-1)/2行对应村庄间的距离，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间的距离。为简单起见，村庄从1到N编号。 当N为0时，输入结束，该用例不被处理。

输出

对每个测试用例，在1行里输出最小的公路总长度。

样例输入

3 1 2 1 1 3 2 2 3 4 4 1 2 1 1 3 4 1 4 1 2 3 3 2 4 2 3 4 5 0

样例输出

3 5

大声BB

模板题 直接套就行了

#include <stdio.h> #include <iostream> #include <string.h> #include <algorithm> using namespace std; #define ll long long const int INF=1<<30; const int N=1000002; int pre[105]; struct EDGE{ int u,v,c; }; struct EDGE edge[100005],anse[105]; bool cmp1(EDGE a,EDGE b){ return a.c<b.c; } bool cmp2(EDGE a,EDGE b){ if(a.u == b.u) return a.v<b.v; return a.u<b.u; } void init(){ for(int i = 0 ;i <= 100 ;i++) pre[i]=i; } int fin(int x){ return pre[x]==x?x:pre[x]=fin(pre[x]); } int main() { int n,e; while(scanf("%d",&n)!=EOF && n!=0){ e = n*(n-1)/2; for(int i = 0 ;i < e; i++){ scanf("%d %d %d",&edge[i].u,&edge[i].v,&edge[i].c); } init(); sort(edge,edge+e,cmp1); int cnt = 0; int ans = 0; for(int i = 0 ;i < e ;i++){ int a = fin(edge[i].u); int b = fin(edge[i].v); if(a!=b){ pre[a] = b; ans+=edge[i].c; cnt++; } } printf("%d\n",ans); return 0; }

---

建设电力系统

时间限制: 1 Sec 内存限制: 32 MB 提交: 52 解决: 30

题目描述

小明所在的城市由于下暴雪的原因，电力系统严重受损。许多电力线路被破坏，因此许多村庄与主电网失去了联系。政府想尽快重建电力系统，所以，身为程序员的你被赋予了一项任务，就是编程计算重建电力系统的最少花费，重建的电力系统必须保证任意两个村庄之间至少存在一条通路。

输入

输入的第一行为一个整数T（1<=T<=50），表示有T组测试数据。 每组输入第一行是两个正整数N，E（2<=N<=500，N<=E<=N*(N-1)/2），分别表示村庄的个数和原有电力线路的个数。 接下来的E行，每行包含三个整数A，B，K（0<=A,B<N，0<=K<1000）。A和B分别表示电力线路的起始村庄代号。如果K=0，表示这条线路仍然正常。如果K是一个正整数，表示这条线路需要花费K的代价来重建。 题目保证输入中没有重边，也没有起始村庄相同的边。

输出

对于每组输入，输出重建电力系统所需的最小花费，以此来保证任意两个村庄之间至少存在一条通路。

样例输入

1 3 3 0 1 5 0 2 0 1 2 9

样例输出

5

大声BB

和上面那个题一样，需要注意一下n的取值范围，不然会运行错误，就是数组开小了， 初始化那里也要注意，因为我用的是常数所以要改过来

#include <stdio.h> #include <iostream> #include <string.h> #include <algorithm> using namespace std; #define ll long long const int INF=1<<30; const int N=1000002; int pre[505]; struct EDGE{ int u,v,c; }; struct EDGE edge[1000005],anse[505]; bool cmp1(EDGE a,EDGE b){ return a.c<b.c; } bool cmp2(EDGE a,EDGE b){ if(a.u == b.u) return a.v<b.v; return a.u<b.u; } void init(){ for(int i = 0 ;i <= 500 ;i++) pre[i]=i; } int fin(int x){ return pre[x]==x?x:pre[x]=fin(pre[x]); } int main() { int T,n,e; scanf("%d",&T); while(T--){ scanf("%d %d",&n,&e); for(int i = 0 ;i < e; i++){ scanf("%d %d %d",&edge[i].u,&edge[i].v,&edge[i].c); } init(); sort(edge,edge+e,cmp1); int cnt = 0; int ans = 0; for(int i = 0 ;i < e ;i++){ int a = fin(edge[i].u); int b = fin(edge[i].v); if(a!=b){ pre[a] = b; ans += edge[i].c; cnt++; } } printf("%d\n",ans); } return 0; }