P1546 Agri-Net

题目背景

农民约翰被选为他们镇的镇长！他其中一个竞选承诺就是在镇上建立起互联网，并连接到所有的农场。当然，他需要你的帮助。

题目描述

约翰已经给他的农场安排了一条高速的网络线路，他想把这条线路共享给其他农场。为了用最小的消费，他想铺设最短的光纤去连接所有的农场。
你将得到一份各农场之间连接费用的列表，你必须找出能连接所有农场并所用光纤最短的方案。每两个农场间的距离不会超过100000。

输入输出格式

输入格式

第一行：农场的个数，N $(3 \leq N \leq 100)$。

第二行..结尾: 后来的行包含了一个N*N的矩阵,表示每个农场之间的距离。理论上，他们是N行，每行由N个用空格分隔的数组成，实际上，他们限制在80个字符，因此，某些行会紧接着另一些行。当然，对角线将会是0，因为不会有线路从第i个农场到它本身。

输出格式

只有一个输出，其中包含连接到每个农场的光纤的最小长度。

INPUT & OUTPUT ‘s examples

Input’s eg #1

Output’s eg #1

分析

就是一道kruskal&并查集的模板题。

简单介绍一下kruskal算法，（前置知识：并查集）。

首先，我们把无向图中相互连通的一些点称为处于同一个连通块中。

Kruskal算法将一个连通块当做一个集合。首先，将所有的边按从大到小的顺序排序（一般使用快排）。

这时，我们认为每一个点都是孤立的，分别隶属于$n$个不同的集合。

然后，我们顺序枚举每一条边，如果这两条边分别隶属于不同的集合，那么就把这条边加入最小生成树，这两个不同的集合就合并成了一个新集合，如果这条边连接的两个点隶属于同一个集合，那么跳过。

直到选了$n-1$条边为止。

算法描述

首先，我们初始化并查集：dad[x]=x;

第二步，tot=0;

第三步，将所有边按从大到小顺序排序。

第四步，计数器cnt=0;

第五步，

for(int i=1;i<=M;i++){
    if(//这是一条u,v不属于同一集合的边){
        //1、合并u,v所在的集合，相当于把u,v加入最小生成树。
        //2、tot+=W(u,v);
        //3、cnt++;
        //4、如果k==n-1，说明最小生成树已经形成，break;
    }
}
//6、结束，`tot`即为最小生成树权值之和

这道题

完全就是模板对吧。

按照kruskal的算法程序走，最后tot即为答案。

代码

/* Headers */
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cctype>
#include<algorithm>
using namespace std;
namespace FastIO{
    const int BUFSIZE=1<<20;
    char ibuf[BUFSIZE],*is=ibuf,*it=ibuf;
    char obuf[BUFSIZE],*os=obuf,*ot=obuf+BUFSIZE;
    inline char getch(){
        if(is==it)
            it=(is=ibuf)+fread(ibuf,1,BUFSIZE,stdin);
        return (is==it)?EOF:*is++;
    }
    inline int getint(){
        int res=0,neg=0,ch=getch();
        while(!(isdigit(ch)||ch=='-')&&ch!=EOF)
            ch=getch();
        if(ch=='-'){
            neg=1;ch=getch();
        }
        while(isdigit(ch)){
            res=(res<<3)+(res<<1)+(ch-'0');
            ch=getch();
        }
        return neg?-res:res;
    }
    inline void flush(){
        fwrite(obuf,1,os-obuf,stdout);
        os=obuf;
    }
    inline void putch(char ch){
        *os++=ch;
        if(os==ot)	flush();
    }
    inline void putint(int res){
        static char q[10];
        if(res==0)	putch('0');
        else if(res<0){
            putch('-');
            res=-res;
        } 
        int top=0;
        while(res){
            q[top++]=res%10+'0';
            res/=10;
        }
        while(top--)	putch(q[top]);
    }
} 
using namespace FastIO;
/* consts */
const int MAXN = 1e4+10;
/* definitions */
struct Node{
	int x,y,v;
};
Node John[MAXN];
int dad[MAXN],n,m,k,ans;
int x;
/* functions */
inline int father(int t){
	if(dad[t]!=t)dad[t]=father(dad[t]);
	return dad[t];
}
inline void unionx(int x,int y){
	if(father(x)!=father(y))dad[father(x)]=father(y);
}
inline int cmp(const Node &a,const Node &b){
	if(a.v<b.v) return 1;
	else return 0;
}
inline void init(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			scanf("%d",&x);
			if(x){
				++m;
				John[m].x=i;John[m].y=j;
				John[m].v=x;
			}
		}
	}
}
inline void kruskal(){
	init();
	for(int i=1;i<=n;i++)dad[i]=i;
	sort(John+1,John+m+1,cmp);
	for(int i=1;i<=m;i++){
		if(father(John[i].x)!=father(John[i].y)){
			unionx(John[i].x,John[i].y);
			ans+=John[i].v;
			k++;
		}
		if(k==n-1)break;
	}
	printf("%d\n",ans);
}
int main(int argc,char *argv[]){
	kruskal();
	return 0;
}

洛谷P1546题解&kruskal简述