ZISUOJ 数据结构--图及其应用

说明

        主要考察建图，图的遍历以及求最小生成树。都还是比较简单的，后面就直接上代码了。

        最小生成树采用prim还是kruskal算法要看题目怎么给出数据，如果以邻接矩阵的形式给出，采用prim算法比较合适，如果以边和边的权重的形式给出，则采用kruskal算法比较合适。例如这里的D和E题采用kruskal算法比较好，但是不代表用prim算法不能做，我这两个题给出的就是prim的解法，但是某些题用另一个算法极不方便，因此还是建议采用题目所暗示我们应使用的方法最佳。

题目列表

问题 A: 图的遍历—深度优先搜索—邻接矩阵

参考题解：

#include <iostream>
#include <functional>
 
int main(){
	std::cin.tie(nullptr)->sync_with_stdio(false);
	constexpr int MAX_N = 5e1+5;
	int g[MAX_N][MAX_N] {};
	bool vis[MAX_N] {};
	int n;std::cin >> n;
	for(int i = 0;i<n;i++){
		for(int j = 0;j<n;j++){
			std::cin >> g[i][j];
		}
	}
	using Dfs = std::function<void(int)>; 
	Dfs dfs = [&](int u) {
		std::cout << u << ' ';
		for(int i = 0;i<n;i++){
			if(g[u][i]&&!vis[i]) vis[i]=true,dfs(i);
		}
	};
	vis[0] = true;
	dfs(0);
	std::cout << '\n';
	return 0;
} 

问题 B: 图的遍历—DFS—已知边

参考题解：

#include <iostream>
#include <functional>
 
int main(){
	std::cin.tie(nullptr)->sync_with_stdio(false);
	constexpr int MAX_N = 1e1+5;
	int g[MAX_N][MAX_N] {};
	bool vis[MAX_N] {};
	int n,m;std::cin >> n >> m;
	while(m--){
		int x,y;std::cin >> x >> y;
		g[x][y]=g[y][x]=1;
	}
	using Dfs = std::function<void(int)>;
	Dfs dfs = [&](int u){
		std::cout << u << ' ';
		for(int i = 1;i<=n;i++){
			if(g[u][i]&&!vis[i]) vis[i]=true,dfs(i);
		}
	};
	vis[1] = true;
	dfs(1);
	std::cout << '\n';
	return 0;
} 

问题 C: 图的遍历—广度优先搜索

参考题解：

#include <iostream>
#include <queue>
 
int main(){
	std::cin.tie(nullptr)->sync_with_stdio(false);
	constexpr int MAX_N = 5e1+5;
	int g[MAX_N][MAX_N] {};
	bool vis[MAX_N] {};
	int n;std::cin >> n;
	for(int i = 0;i<n;i++){
		for(int j = 0;j<n;j++){
			std::cin >> g[i][j];
		}
	}
	auto bfs = [&](){
		std::queue<int> q;
		q.emplace(0);
		vis[0] = true;
		while(!q.empty()){
			auto t = q.front();
			q.pop();
			std::cout << t << ' ';
			for(int i = 0;i<n;i++){
				if(!vis[i]&&g[t][i]){
					vis[i] = true;
					q.emplace(i);
				}
			}
		}
	};
	bfs();
	std::cout << '\n';
	return 0;
} 

问题 D: 最小生成树-局域网

 

参考题解：

#include <iostream>
#include <cstring>
#include <type_traits>
template<typename T1,typename T2>
typename std::common_type<T1,T2>::type min(T1 num1,T2 num2){
	return num1>num2?num2:num1;
}
int main(){
	std::cin.tie(nullptr)->sync_with_stdio(false);
	constexpr int MAX_N = 1e2+5,INF = 0x3f3f3f3f;
	int g[MAX_N][MAX_N];
	int dist[MAX_N];
	memset(g,0x3f,sizeof g);
	bool vis[MAX_N] = {false};
	int n,m;std::cin >> n >> m;
	int ans = 0;
	while(m--){
		int x,y,w;std::cin >> x >> y >> w;
		g[x][y]=g[y][x]=min(g[y][x],w);
		ans+=w;
	}
	auto prim = [&]()->int{
		memset(dist,0x3f,sizeof dist);
		dist[1] = 0;
		int ans = 0;
		for(int i = 0;i<n;++i){
			int t = -1;
			for(int j = 1;j<=n;++j){
				if(!vis[j]&&(t==-1||dist[t]>dist[j])) t = j;
			}
			if(dist[t]==INF) return INF;
			ans+=dist[t];
			vis[t] = true;
			for(int j = 1;j<=n;++j) dist[j] = min(dist[j],g[t][j]);
		}
		return ans;
	};
	ans-=prim();
	std::cout << ans << '\n';
	return 0;
} 

问题 E: 最小生成树-繁忙的都市

 

参考题解：

#include <iostream>
#include <cstring>
#include <type_traits>
template<typename T1,typename T2>
typename std::common_type<T1,T2>::type max(T1 num1,T2 num2){
	return num1<num2?num2:num1;
}
template<typename T1,typename T2>
typename std::common_type<T1,T2>::type min(T1 num1,T2 num2){
	return num1>num2?num2:num1;
}
int main(){
	std::cin.tie(nullptr)->sync_with_stdio(false);
	constexpr int MAX_N = 1e2+5,INF = 0x3f3f3f3f;
	int g[MAX_N][MAX_N];
	int dist[MAX_N];
	memset(g,0x3f,sizeof g);
	bool vis[MAX_N] = {false};
	int n,m;std::cin >> n >> m;
	while(m--){
		int x,y,w;std::cin >> x >> y >> w;
		g[x][y]=g[y][x]=min(g[y][x],w);
	}
	auto prim = [&]()->int{
		memset(dist,0x3f,sizeof dist);
		dist[1] = 0;
		int ans = 0;
		for(int i = 0;i<n;++i){
			int t = -1;
			for(int j = 1;j<=n;++j){
				if(!vis[j]&&(t==-1||dist[t]>dist[j])) t = j;
			}
			if(dist[t]==INF) return INF;
			ans = max(ans,dist[t]);
			vis[t] = true;
			for(int j = 1;j<=n;++j) dist[j]=min(dist[j],g[t][j]);
		}
		return ans;
	};
	std::cout << n-1 << ' ' << prim() << '\n';
	return 0;
} 

问题 F: 最小生成树-联络员

 

参考题解：

#include <iostream>
#include <vector>
#include <functional>
#include <algorithm>
 
constexpr int MAX_N = 2e3+5,MAX_M = 1e4+5,INF = 0x3f3f3f3f;
 
struct edge{
	int x,y,w;
	bool operator < (const edge& W){
		return w<W.w;
	}
	edge(int _x,int _y,int _w):x(_x),y(_y),w(_w){}
};
std::vector<edge> edges;
int fa[MAX_N];
int main(){
	std::cin.tie(nullptr)->sync_with_stdio(false);
	int n,m;std::cin >> n >> m;
	for(int i = 1;i<=n;++i) fa[i] = i;
	using Find = std::function<int(int)>;
	Find find = [&](int x){
		if(x!=fa[x]) fa[x] = find(fa[x]);
		return fa[x];
	};
	int ans = 0;
	while(m--){
		int t,x,y,w;std::cin >> t >> x >> y >> w;
		if(t==1){
			ans+=w;
			fa[find(x)] = find(y);
		}else{
			edges.emplace_back(x,y,w);
		}
	}
	auto kruskal = [&](){
		std::sort(edges.begin(),edges.end());
		for(int i = 0;i<edges.size();++i){
			int fx = find(edges[i].x),fy = find(edges[i].y),w = edges[i].w;
			if(fx!=fy){
				fa[fx] = fy;
				ans+=w;
			}
		}
	};
	kruskal();
	std::cout << ans << '\n';
	return 0;
}

问题 G: 最小生成树-连接格点

 

参考题解：

#include <iostream>
#include <functional>
 
constexpr int MAX_N = 1e3+5;
 
int fa[MAX_N*MAX_N];
 
int main(){
	std::cin.tie(nullptr)->sync_with_stdio(false);
	using Find = std::function<int(int)>;
	Find find = [&](int x)->int{
		if(x!=fa[x]) fa[x] = find(fa[x]);
		return fa[x];
	};
	int n,m;std::cin >> n >> m;
	for(int i = 0;i<=n*m;++i) fa[i] = i;
	int x1,y1,x2,y2;
	while(std::cin >> x1 >> y1 >> x2 >> y2){
		fa[find((x1-1)*m+y1)] = find((x2-1)*m+y2);
	}
	int ans = 0;
	auto kruskal = [&]()->void{
		for(int i = 1;i<n;++i){
			for(int j = 1;j<=m;++j){
				int dx = find((i-1)*m+j),dy = find(i*m+j);
				if(dx!=dy){
					++ans;
					fa[dx] = dy;
				}
			}
		}
		for(int i = 1;i<=n;++i){
			for(int j = 1;j<m;++j){
				int dx = find((i-1)*m+j),dy = find((i-1)*m+j+1);
				if(dx!=dy){
					ans+=2;
					fa[dx] = dy;
				}
			}
		}
	};
	kruskal();
	std::cout << ans << '\n';
	return 0;
}

问题 H: 最小生成树-最短网络

 

参考题解：

#include <iostream>
#include <cstring>
#include <type_traits>
template<typename T1,typename T2>
typename std::common_type<T1,T2>::type min(T1 num1,T2 num2){
	return num1>num2?num2:num1;
}
int main(){
	std::cin.tie(nullptr)->sync_with_stdio(false);
	constexpr int MAX_N = 1e2+5,INF = 0x3f3f3f3f;
	int g[MAX_N][MAX_N];
	int dist[MAX_N];
	bool vis[MAX_N] {};
	int n;std::cin >> n;
	for(int i = 1;i<=n;++i){
		for(int j = 1;j<=n;++j){
			std::cin >> g[i][j];
		}
	}
	auto prim = [&]()->int{
		memset(dist,0x3f,sizeof dist);
		int res = 0;
		dist[1] = 0;
		for(int i = 0;i<n;++i){
			int t = -1;
			for(int j = 1;j<=n;++j){
				if(!vis[j]&&(t==-1||dist[j]<dist[t])) t = j;
			}
			if(dist[t]==INF) return INF;
			vis[t] = true;
			res+=dist[t];
			for(int j = 1;j<=n;++j) dist[j]=min(dist[j],g[t][j]);
		}
		return res;
	};
	std::cout << prim() << '\n';
	return 0;
}

问题 I: 最小生成树-最优布线问题

 

参考题解：

#include <iostream>
#include <cstring>
#include <type_traits>
template<typename T1,typename T2>
typename std::common_type<T1,T2>::type min(T1 num1,T2 num2){
	return num1>num2?num2:num1;
}
int main(){
	std::cin.tie(nullptr)->sync_with_stdio(false);
	constexpr int MAX_N = 1e2+5,INF = 0x3f3f3f3f;
	int g[MAX_N][MAX_N];
	int dist[MAX_N];
	bool vis[MAX_N] {};
	int n;std::cin >> n;
	for(int i = 1;i<=n;++i){
		for(int j = 1;j<=n;++j){
			std::cin >> g[i][j];
		}
	}
	auto prim = [&]()->int{
		memset(dist,0x3f,sizeof dist);
		int res = 0;
		dist[1] = 0;
		for(int i = 0;i<n;++i){
			int t = -1;
			for(int j = 1;j<=n;++j){
				if(!vis[j]&&(t==-1||dist[j]<dist[t])) t = j;
			}
			if(dist[t]==INF) return INF;
			vis[t] = true;
			res+=dist[t];
			for(int j = 1;j<=n;++j) dist[j]=min(dist[j],g[t][j]);
		}
		return res;
	};
	std::cout << prim() << '\n';
	return 0;
}