Problem A: 还是畅通工程 - Codeup新家
题目描述
某省调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可），并要求铺设的公路总长度为最小。请计算最小的公路总长度。
输入
测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( < 100 )；随后的N(N-1)/2行对应村庄间的距离，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间的距离。为简单起见，村庄从1到N编号。
当N为0时，输入结束，该用例不被处理。
输出
对每个测试用例，在1行里输出最小的公路总长度。
样例输入
8
1 2 42
1 3 68
1 4 35
1 5 1
1 6 70
1 7 25
1 8 79
2 3 59
2 4 63
2 5 65
2 6 6
2 7 46
2 8 82
3 4 28
3 5 62
3 6 92
3 7 96
3 8 43
4 5 28
4 6 37
4 7 92
4 8 5
5 6 3
5 7 54
5 8 93
6 7 83
6 8 22
7 8 17
0样例输出
82分析：最小生成树的模板题。
prim算法：
#include<algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <cstdio>
#include <queue>
#include <stack>
#include <ctime>
#include <cmath>
#include <map>
#include <set>
#define INF 0x3fffffff
#define db1(x) cout<<#x<<"="<<(x)<<endl
#define db2(x,y) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<endl
#define db3(x,y,z) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<", "<<#z<<"="<<(z)<<endl
#define db4(x,y,z,r) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<", "<<#z<<"="<<(z)<<", "<<#r<<"="<<(r)<<endl
#define db5(x,y,z,r,w) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<", "<<#z<<"="<<(z)<<", "<<#r<<"="<<(r)<<", "<<#w<<"="<<(w)<<endl
using namespace std;int graph[110][110];int prim(int n,int d[])
{int ans=0;bool vis[n+5]={0};d[1]=0;for(int times=0;times<n;++times){int u=-1,mini=INF;for(int i=1;i<=n;++i){if(!vis[i]&&d[i]<mini)u=i,mini=d[i];}if(u==-1)return ans;vis[u]=1;ans+=mini;
// db3(u,mini,ans);for(int i=1;i<=n;++i){if(!vis[i]&&graph[u][i]!=INF){if(d[i]>graph[u][i])d[i]=graph[u][i];}}}return ans;
}int main(void)
{#ifdef testfreopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);clock_t start=clock();#endif //testint n;while(scanf("%d",&n),n){int len=n*(n-1)/2;for(int i=0;i<=n;++i)for(int j=0;j<=n;++j)graph[i][j]=INF;for(int i=0;i<len;++i){int a,b,c;scanf("%d%d%d",&a,&b,&c);graph[a][b]=graph[b][a]=c;}int d[n+5];for(int i=0;i<=n;++i)d[i]=INF;int ans=prim(n,d);printf("%d\n",ans);}#ifdef testclockid_t end=clock();double endtime=(double)(end-start)/CLOCKS_PER_SEC;printf("\n\n\n\n\n");cout<<"Total time:"<<endtime<<"s"<<endl; //s为单位cout<<"Total time:"<<endtime*1000<<"ms"<<endl; //ms为单位#endif //testreturn 0;
}kruskal算法：
#include<algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <cstdio>
#include <queue>
#include <stack>
#include <ctime>
#include <cmath>
#include <map>
#include <set>
#define INF 0x3fffffff
#define db1(x) cout<<#x<<"="<<(x)<<endl
#define db2(x,y) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<endl
#define db3(x,y,z) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<", "<<#z<<"="<<(z)<<endl
#define db4(x,y,z,r) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<", "<<#z<<"="<<(z)<<", "<<#r<<"="<<(r)<<endl
#define db5(x,y,z,r,w) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<", "<<#z<<"="<<(z)<<", "<<#r<<"="<<(r)<<", "<<#w<<"="<<(w)<<endl
using namespace std;typedef struct node
{int t,dis;
}node;int findFather(int a,int father[])
{int z=a;while(a!=father[a])a=father[a];while(z!=a){int temp=father[z];father[z]=a,z=temp;}return a;
}int kruskal(int n,int father[],vector<node>graph[])
{int ans=0;for(int times=0;times<n;++times){int u=-1,v=-1,mini=INF;for(int i=1;i<=n;++i){int len=graph[i].size();int fi=findFather(i,father);for(int j=0;j<len;++j){if(graph[i][j].dis<mini){int fj=findFather(graph[i][j].t,father);if(fi!=fj)u=i,v=j,mini=graph[i][j].dis;}}}if(u==-1)return ans;ans+=graph[u][v].dis;int fu=findFather(u,father);int fv=findFather(graph[u][v].t,father);father[fu]=fv;}return ans;
}int main(void)
{#ifdef testfreopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);clock_t start=clock();#endif //testint n;while(scanf("%d",&n),n){int len=n*(n-1)/2;vector<node>graph[n+5];for(int i=0;i<len;++i){int a,b,c;scanf("%d%d%d",&a,&b,&c);node n1,n2;n1.t=b,n2.t=a,n1.dis=n2.dis=c;graph[a].push_back(n1);graph[a].push_back(n2);}int d[n+5],father[n+5];for(int i=0;i<=n;++i)d[i]=INF,father[i]=i;int ans=kruskal(n,father,graph);printf("%d\n",ans);}#ifdef testclockid_t end=clock();double endtime=(double)(end-start)/CLOCKS_PER_SEC;printf("\n\n\n\n\n");cout<<"Total time:"<<endtime<<"s"<<endl; //s为单位cout<<"Total time:"<<endtime*1000<<"ms"<<endl; //ms为单位#endif //testreturn 0;
}