week6 C D 并查集+Kruskal

C - 掌握魔法の东东 I

题目描述

东东在老家农村无聊，想种田。农田有 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值

样例

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

思路分析

可以把田地看成每两个点都两两相邻的完全连通图，现在就是要找出最小生成树，但又因为每个点都可以从外部达到，所以我们把外部看成一个点0，使这个图变为有n+1个顶点的完全连通图。

要用到Kruskal算法，选择n条边构建最小生成树。首先将图中的边按权值升序排序，每次按顺序选择当前权值最小的边，若该边两个端点加入后不会形成回路，则加入最小生成树，将两个点并到集合中。

AC代码

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std; 
int w[310],parent[310];
int n,mp=0;
int num=0;
struct Edge
{
 int u,v,w;
 bool operator<(const Edge& p) const 
 {
  return w<p.w;   
 }
};
Edge edge[100000];
void init()
{
 for(int i=0;i<=n;i++)
 {
  parent[i]=i;//当开始的根都是自己 
 }
} 
int find(int x) 
{//函数搜索并返回包含元素x的树的根元素 
 while(parent[x]!=x)
 {
  x = parent[x];
 }
 return x;
}
void Union(int root1, int root2) 
{
 if (parent[root1]<parent[root2]) //把小的作为根 
 {    
  parent[root2]=root1;    
 }
 else
 {
  parent[root1]=root2;           
 } 
}
void Kruskal()
{
 init();
    //每次都从剩下的边中选择权最小的，且必须两个点不同时标记 
    int index=0; 
 for(int i=0;i<num;i++)//选出n 条边 
 {
  if(index==n) break;
        if(edge[i].u==edge[i].v)
         continue;
  int root1=find(edge[i].u);
  int root2=find(edge[i].v);
  //判断root1，2是否在最小生成树中 
  if(root1!=root2)//合并
  {
   //cout<<edge[i].u<<" "<<edge[i].v<<" "<<edge[i].w<<endl;
   Union(root1,root2);
        mp+=edge[i].w; 
       index++;
  }  
 }  
} 
int main()
{
 cin>>n;
 for(int i=1;i<=n;i++)
 {
  edge[num].u=0;//黄河之水天上来 
  edge[num].v=i;
  cin>>edge[num].w;
  num++;
 }
 for(int i=1;i<=n;i++)
 {
  for(int j=1;j<=n;j++)
  {
   edge[num].u=i;
   edge[num].v=j;
   cin>>edge[num].w;
   num++;
  }
 }
 sort(edge,edge+num);
 Kruskal();
 cout<<mp;
 return 0; 
}

D-数据中心

题目描述

样例

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

思路分析

其实就是要构造最小生成树，找到其中最大权值。

AC代码

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std; 
int parent[500005];
int n,m,root;
int ans=0;
struct Edge
{
 int u,v,w;
 bool operator<(const Edge& p) const 
 {
  return w<p.w;   
 }
};
Edge edge[50005];
void init()
{
 for(int i=1;i<=n;i++)
 {
  parent[i]=i;//当开始的根都是自己 
 }
} 
int find(int x) 
{//函数搜索并返回包含元素x的树的根元素 
 while(parent[x]!=x)
 {
  x = parent[x];
 }
 return x;
}
void Union(int root1, int root2) 
{
 if (parent[root1]<parent[root2]) //把小的作为根 
 {    
  parent[root2]=root1;    
 }
 else
 {
  parent[root1]=root2;           
 } 
}
void Kruskal()
{
 init();
    int index=0; 
 for(int i=0;i<m;i++) 
 {
  if(index==n-1) break;
  int root1=find(edge[i].u);
  int root2=find(edge[i].v);
  //判断root1，2是否在最小生成树中 
  if(root1!=root2)//合并
  {
   //cout<<edge[i].u<<" "<<edge[i].v<<" "<<edge[i].w<<endl;
   Union(root1,root2);
        ans=max(ans,edge[i].w);
       index++;
  } 
 }  
} 
int main()
{
 cin>>n>>m>>root;
 for(int i=0;i<m;i++)
 {
  cin>>edge[i].u>>edge[i].v>>edge[i].w;
 }
 sort(edge,edge+m);
 Kruskal();
 cout<<ans;
 return 0; 
}