期末考的题目的一些问题

常规
1 
#include <bits/stdc++.h>

using namespace std;
struct node{
	int v, w;
	bool operator < (const node &t) const{
		return w > t.w;
	}
};
vector <int> g[105];
vector <node> g2[105];
priority_queue <node> q;
int n, m;
int vis[105], tu[105][105];
int dis[1005], vis2[1005], ans;

void dfs(int u, int num) {
	vis[u] = num;
	for (int i = 0; i < g[u].size(); i++) {
		int v = g[u][i];
		
		if (!vis[v]) {
			dfs(v, num);
		}
		
		
	}
}

int main () {
	cin >> n;
	for (int i = 1; i <=n; i++) {
		
		for (int j = 1; j <= n; j++) {
			
			int x;
			scanf("%d", &x);
			if (i != j && x == 0) {
				g[i].push_back(j);
				m++;
			}
			else if(i!= j && x != 0) {
				tu[i][j] = x;
			//	g2[i].push_back({j,x});
				
			}
		}
		
	}
	m/=2;
	
	int cnt = 0;
	for (int i = 1; i <= n; i++) {
		
		if (!vis[i]) {
			cnt++;
			dfs(i, cnt);
		}
		
		
	}
	//已经找完联通子图个数 
	
	for (int i = 1; i <=n; i++) {
		
		for (int j = 1; j <= n; j++) {
			
			if(i!= j && tu[i][j] != 0) {
				
				g2[vis[i]].push_back({j, tu[i][j]});
				
			}
		}
		
	}
	
	memset(dis, 0x3f, sizeof dis);
	dis[1] = 0;
	int count = 0;
	q.push({1, 0});
	
	while (q.size()) {
		
		node t = q.top();
		q.pop();
		
		int u = t.v, dist = t.w;
		
		if (vis2[u]) continue;
		
		vis2[u] = 1;
		
		count++;
		ans += dist;
		
		for (int i = 0; i < g2[u].size(); i++) {
			
			int v = g2[u][i].v, w = g2[u][i].w;
			
			if (vis2[v] == 0 && dis[v] > w) {
				dis[v] = w;
				q.push({v, dis[v]});
			}
			
		}
		
		
	}
	
	cout << count << ' ' << ans;
	
	return 0;
}

这是电话连线题目的代码，调试过发现除了普里姆有问题其他没问题，但是不知道哪里错了
还有就是为什么朋友圈那道题可以用并查集，朋友圈不是图吗

5 个赞