Wek6 Minimum spanning tree

问题一描述：

东东在老家农村无聊，想种田。农田有 n 块，编号从 1~n。种田要灌氵
众所周知东东是一个魔法师，他可以消耗一定的 MP 在一块田上施展魔法，使得黄河之水天上来。他也可以消耗一定的 MP 在两块田的渠上建立传送门，使得这块田引用那块有水的田的水。 (1<=n<=3e2)
黄河之水天上来的消耗是 Wi，i 是农田编号 (1<=Wi<=1e5)
建立传送门的消耗是 Pij，i、j 是农田编号 (1<= Pij <=1e5, Pij = Pji, Pii =0)
东东为所有的田灌溉的最小消耗。

Input：
第1行：一个数n
第2行到第n+1行：数wi
第n+2行到第2n+1行：矩阵即pij矩阵
Output：
东东最小消耗的MP值。

Sample Input：
4
5
4
4
3
0 2 2 2
2 0 3 3
2 3 0 4
2 3 4 0
Sample Output：
9

问题二描述：

Sample Input ：
4
5
1
1 2 3
1 3 4
1 4 5
2 3 8
3 4 2
Sample Output：
4

解题思路：

题一的目的是让所有田都有水灌溉，且消耗最小，建立一个超级源点，题目等价于对这n+1个点建立最小生成树。
题二欲使树的最大边最小，欲使瓶颈生成树的最大边最小，该边等于最小生成树的边，故等价于求最小生成树的边。
最小生成树的思想：若有n个点，将边升序排序，从小到大依次取n-1条不会产生环的边，这n-1条边就构成了最终的最小生成树，可以利用并查集求最小生成树。

实验一代码：

#include<iostream>
#include<algorithm>
using namespace std;
int root[310];			
int rnk[310]; 			
struct Edge				
{int u;			int v;int w;bool operator<(const Edge& e) const	{return w<e.w;			}
};			
Edge edge[50000];	
int cnt;			 
void unit(int n)		
{int w;Edge e;for(int i=1;i<=n;i++)		{cin>>w;edge[cnt].u=0;edge[cnt].v=i;edge[cnt].w=w;cnt++;}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){cin>>w;				if(i>j){edge[cnt].u=i;edge[cnt].v=j;edge[cnt].w=w;cnt++;}}} sort(edge,edge+cnt);			for(int i=0;i<=n;i++)root[i]=i;		
}
int find(int a)		
{if(root[a]==a)		return a;elsereturn find(root[a]);	
}bool unite(int a,int b,int w)			
{int rootA=find(a);		int rootB=find(b);		if(rootA==rootB)return false;		else{root[rootB]=rootA;					rnk[rootA]+=(rnk[rootB]+w);				return true;} 
} 
bool min_spanningtree(int n)		
{int e=0;for(int i=0;i<cnt;i++){if( unite(edge[i].u,edge[i].v,edge[i].w) )		{e++;  if(e==n)		return true;}}
}int main(void)
{int n;cin>>n;unit(n);min_spanningtree(n);cout<<rnk[ find(0) ]<<endl;return 0;} 

实验二代码：

#include<iostream>
#include<algorithm> 
using namespace std;
int n,m,r;
struct Edge
{int u;int v;int w;bool operator<(const Edge& e) const{return w<e.w;} 
};
Edge edge[100050];
int ecnt;
int root[50050];
int rnk[50050];
int find(int a)
{if(root[a]==a)		 return a;return find(root[a]);
}
bool unite(int a,int b,int w)
{int classA=find(a);int classB=find(b);if(classA==classB)		return false;if(classA<classB)			swap(classA,classB);root[classB]=classA;		rnk[classA]+=(rnk[classB]+w);		return true;
} 
void initial()
{for(int i=0;i<=n;i++)root[i]=i;			
}
int spanning_Tree()
{sort(edge,edge+ecnt);		initial();			int e=0;				for(int i=0;i<ecnt;i++){if( unite(edge[i].u,edge[i].v,edge[i].w) )		{e++;  if(e==n-1)					return edge[i].w;		 }}
} 
int main(void)
{ios::sync_with_stdio(0);cin>>n>>m>>r;int u,v,w;for(int i=0;i<m;i++){cin>>u>>v>>w;edge[ecnt].u=u;edge[ecnt].v=v;edge[ecnt].w=w;ecnt++;}cout<<spanning_Tree()<<endl;return 0;
}