HDU1233 还是畅通工程(最小生成树模板题，Prime,kruskal算法)

2019-11-06 07:50:49

字体：大中小

来源：转载

供稿：网友

题目：

还是畅通工程

Time Limit: 4000/2000 MS (java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 43194 Accepted Submission(s): 19689PRoblem Description某省调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可），并要求铺设的公路总长度为最小。请计算最小的公路总长度。 Input测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( < 100 )；随后的N(N-1)/2行对应村庄间的距离，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间的距离。为简单起见，村庄从1到N编号。当N为0时，输入结束，该用例不被处理。 Output对每个测试用例，在1行里输出最小的公路总长度。 Sample Input

31 2 11 3 22 3 441 2 11 3 41 4 12 3 32 4 23 4 50 Sample Output35HintHint Huge input, scanf is recommended. Source浙大计算机研究生复试上机考试-2006年 思路：
就是最小生成树的模板题，看一下前面两篇介绍的就行
代码1（kruskal）:
#include <cstdio>#include <cstring>#include <cstdlib>#include <cmath>#include <string>#include <iostream>#include <stack>#include <queue>#include <vector>#include <algorithm>#define mem(a,b) memset(a,b,sizeof(a))#define N 5000+20#define M 100000+20#define MOD 1000000000+7#define inf 0x3f3f3f3fusing namespace std;int n;struct node{    int u;    int v;    int w;} map[N];int f[N],sum,cnt;int getf(int v){    if(f[v]==v)        return v;    else    {        f[v]=getf(f[v]);        return f[v];    }}int mix(int v,int u){    int t1=getf(v);    int t2=getf(u);    if(t1!=t2)    {        f[t2]=t1;        return 1;    }    return 0;}bool cmp(node x,node y){    return x.w<y.w;}void init()//并查集初始化{    for(int i=1; i<=n; i++)        f[i]=i;}int main(){    while(~scanf("%d",&n)&&n)    {        sum=0;        cnt=0;        mem(f,0);        int m=(n*n-n)/2;        for(int i=1; i<=m; i++)            scanf("%d%d%d",&map[i].u,&map[i].v,&map[i].w);        sort(map+1,map+m+1,cmp);        init();        for(int i=1; i<=m; i++)        {            if(mix(map[i].u,map[i].v))            {                cnt++;                sum+=map[i].w;            }            if(cnt==n-1)                break;        }        printf("%d/n",sum);    }    return 0;}代码2（Prime）:
#include <cstdio>#include <cstring>#include <cstdlib>#include <cmath>#include <string>#include <iostream>#include <stack>#include <queue>#include <vector>#include <algorithm>#define mem(a,b) memset(a,b,sizeof(a))#define N 100+20#define M 100000+20#define MOD 1000000000+7#define inf 0x3f3f3f3fusing namespace std;int n,minn,m;int map[N][N],dis[N],vis[N];int cnt,sum;void Prime(){    vis[1]=1;    cnt++;    int k;    while(cnt<n)    {        minn=inf;        for(int i=1; i<=n; i++)//找到dis里面的最小的        {            if(!vis[i]&&dis[i]<minn)            {                minn=dis[i];                k=i;            }        }        vis[k]=1;        cnt++;        sum+=dis[k];        for(int j=1; j<=n; j++)        {            if(!vis[j]&&dis[j]>map[k][j])//更新生成树到非树顶点的距离                dis[j]=map[k][j];        }    }}int main(){    while(~scanf("%d",&n)&&n)    {        cnt=0;        sum=0;        mem(vis,0);        int t1,t2,t3;        m=(n*n-n)/2;        for(int i=1; i<=n; i++)            for(int j=1; j<=n; j++)                if(i==j)                    map[i][j]=0;                else                    map[i][j]=inf;//建图        for(int i=1; i<=m; i++)        {            scanf("%d%d%d",&t1,&t2,&t3);            map[t1][t2]=t3;            map[t2][t1]=t3;//存储无向图        }        for(int i=1; i<=n; i++)            dis[i]=map[1][i];        Prime();        printf("%d/n",sum);    }    return 0;}