201412-4 最优灌溉

Posted on | In |

问题描述

雷雷承包了很多片麦田，为了灌溉这些麦田，雷雷在第一个麦田挖了一口很深的水井，所有的麦田都从这口井来引水灌溉。
　　为了灌溉，雷雷需要建立一些水渠，以连接水井和麦田，雷雷也可以利用部分麦田作为“中转站”，利用水渠连接不同的麦田，这样只要一片麦田能被灌溉，则与其连接的麦田也能被灌溉。

现在雷雷知道哪些麦田之间可以建设水渠和建设每个水渠所需要的费用（注意不是所有麦田之间都可以建立水渠）。请问灌溉所有麦田最少需要多少费用来修建水渠。

输入格式

输入的第一行包含两个正整数n, m，分别表示麦田的片数和雷雷可以建立的水渠的数量。麦田使用1, 2, 3, ……依次标号。

接下来m行，每行包含三个整数ai, bi, ci，表示第ai片麦田与第bi片麦田之间可以建立一条水渠，所需要的费用为ci。

输出格式

输出一行，包含一个整数，表示灌溉所有麦田所需要的最小费用。

样例输入

4 4

1 2 1

2 3 4

2 4 2

3 4 3

样例输出

6

样例说明

建立以下三条水渠：麦田1与麦田2、麦田2与麦田4、麦田4与麦田3。

评测用例规模与约定
　
前20%的评测用例满足：n≤5。
　
前40%的评测用例满足：n≤20。
　
前60%的评测用例满足：n≤100。
　　
所有评测用例都满足：1≤n≤1000，1≤m≤100,000，1≤ci≤10,000。

思路

最小生成树 优先队列 并查集思想

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include<iostream>
#include<vector>
#include<queue>
#include<set> 
#include<cstring>
#define INF 1e8
using namespace std; 
struct node{
	int num;
	int cost;
	node(int nn,int cc):num(nn),cost(cc){
		
	}
	bool operator < (const node &p)const{
	return cost>p.cost;
	} 
};
class unionset{
public:
    vector<int> parent;
    vector<int> rank;
	
    unionset(int n){
    parent=vector<int>(n+1,0);
    rank=vector<int>(n+1,0);
        for(int i=1;i<=n;i++)
	parent[i]=i;
	}
	
	bool Union(int u1,int u2){
		int p1=find(u1);
		int p2=find(u2);
		if(p1==p2) return false;
		if(rank[p1]>rank[p2]){
			parent[p2]=p1;
		}
        else if(rank[p2]>rank[p1]){
            parent[p1]=p2;
        }
        else {
            parent[p2]=p1;
            rank[p1]++;
        }
        return true;
		
	}
    int find(int num){
        if(num!=parent[num]){
            parent[num]=find(parent[num]);//find(num)一直自己调用自己 错的 find(parent[num]) 往上回溯
        }
        return parent[num];
    }
	
};

vector<vector<node> > g=vector<vector<node> >(1000+1);
int vis[1000+1];
int cost[1000+1];
int main(){
	int m,n,a,b,c;
	cin>>n>>m;
	unionset u(n);
	for(int i=0;i<m;i++){
		cin>>a>>b>>c;
		u.Union(a,b);
		g[a].push_back(node(b,c));
		g[b].push_back(node(a,c));
	}
	set<int> s; 
	for(int i=1;i<=n;i++){
	s.insert(u.find(i));
	cost[i]=INF;
	}
	
	
	long ans=0;
	for(set<int>::iterator it=s.begin();it!=s.end();it++){
		cost[*it]=0;
		memset(vis,0,sizeof(vis));
		priority_queue<node> q;
		q.push(node(*it,0));
		while(!q.empty()){
			node t=q.top();
			q.pop();
			if(vis[t.num]) continue;
			vis[t.num]=1;
			for(int i=0;i<g[t.num].size();i++){
				node nn=g[t.num][i];
				if(vis[nn.num]) continue; 
				if(nn.cost<cost[nn.num]) 
				{
				
				cost[nn.num]=nn.cost;
				q.push(node(nn.num,cost[nn.num]));
					
				}
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		ans+=cost[i];
	} 
	cout<<ans<<endl;
}

复习了一遍 发现并查集中没有用rank来合并优化的时候 超时了(只有80分)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include<bits/stdc++.h>
#define MAX 1000+2
#define INF 1e8
using namespace std;
int m,n;
struct node{
	int num;
	int cost;
	node(int nn,int cc):num(nn),cost(cc){
	}
	node(){
		
	}
	bool operator < (const node p)const{
		return cost>p.cost;
	} 
};
class UF{
public:
    vector<int> parent;
    vector<int> rank;
    UF(int n){
    parent=vector<int>(n+1,0);
    rank=vector<int>(n+1,0);
        for(int i=1;i<=n;i++)
	parent[i]=i;
	}
	
	bool Union(int u1,int u2){
		int p1=find(u1);
		int p2=find(u2);
		if(p1==p2) return false;
		
		if(rank[p1]>rank[p2]){
			parent[p2]=p1;
		}
        else if(rank[p2]>rank[p1]){
            parent[p1]=p2;
        }
        else {
            parent[p1]=p2;
            rank[p2]++;
        }
        return true;
		
	}
    int find(int num){
        if(num!=parent[num]){
            parent[num]=find(parent[num]);//find(num)一直自己调用自己 错的 find(parent[num]) 往上回溯
        }
        return parent[num];
    }
	
};
int cost[MAX];
int vis[MAX];
vector<vector<node> >g;
int main(){
//	freopen("12-13.txt","r",stdin);
	cin>>n>>m;
	g=vector<vector<node> >(n+1);
	UF u(n);

	int w,f,v;
	for(int j=0;j<m;j++){
		
		cin>>w>>f>>v;
		g[w].push_back(node(f,v));
		//!!
		g[f].push_back(node(w,v)); 
		u.Union(w,f);	
	}
	set<int> s;
	
	
	
	for(int i=1;i<=n;i++){
		int r=u.find(i);
		s.insert(r);
		cost[i]=INF;
	}

	
	for(set<int>::iterator it=s.begin();it!=s.end();it++){
			memset(vis,0,sizeof(vis));
				priority_queue<node> pq;
		pq.push(node(*it,0));
		cost[*it]=0;
	while(!pq.empty()){
		node t=pq.top();
		pq.pop();
		vis[t.num]=1;
		for(int i=0;i<g[t.num].size();i++){
			node p=g[t.num][i];
			if(vis[p.num]) continue;
			if(p.cost<cost[p.num]) {
				cost[p.num]=p.cost;
				pq.push(node(p.num,cost[p.num]));
			}
 		}
		
		}
	} 
	long ans=0;
	for(int j=1;j<=n;j++){
	//	cout<<cost[j]<<" ";
		ans+=cost[j];
	}
	cout<<ans<<endl;
}