题目链接：https://vjudge.net/problem/POJ-1258

题目大意：有一个计算机网络的所有线路都坏了，网络中有n台计算机，现在你可以做两种操作，修理（O）和检测两台计算机是否连通（S），只有修理好的计算机才能连通。连通有个规则，两台计算机的距离不能超过给定的最大距离D（一开始会给你n台计算机的坐标）。检测的时候输出两台计算机是否能连通。

最小生成树裸题

#include<set>#include<map>#include<stack>#include<queue>#include<cmath>#include<cstdio>#include<cctype>#include<string>#include<vector>#include<climits>#include<cstring>#include<cstdlib>#include<iostream>#include<algorithm>#define endl ‘\n‘#define max(a, b) (a > b ? a : b)#define min(a, b) (a < b ? a : b)#define zero(a) memset(a, 0, sizeof(a))#define INF(a) fill(a, a+maxn, INF);#define IOS ios::sync_with_stdio(false)#define _test printf("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n")using namespace std;typedef long long ll;typedef pair<int, int> P;typedef pair<double, int> P2;const double pi = acos(-1.0);const double eps = 1e-7;const ll MOD = 1000000007LL;const int INF = 0x3f3f3f3f;const int _NAN = -0x3f3f3f3f;const double EULC = 0.5772156649015328;const int NIL = -1;template<typename T> void read(T &x){ x = 0;char ch = getchar();ll f = 1; while(!isdigit(ch)){if(ch == ‘-‘)f*=-1;ch=getchar();} while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;}const int maxn = 1e2+10;int p[maxn], vis[maxn];vector<P> dis[maxn];void prim(int n) { priority_queue<P> pq; zero(vis); int sum = 0; pq.push(make_pair(0, 0)); while(!pq.empty()) { P t = pq.top(); pq.pop(); if (vis[t.second]) continue; sum += -1*t.first; vis[t.second] = true; for (int i = 0; i<(int)dis[t.second].size(); ++i) if (!vis[dis[t.second][i].second]) pq.push(make_pair(-1*dis[t.second][i].first, dis[t.second][i].second)); } printf("%d\n", sum);} int main(void) { int n; while(~scanf("%d", &n)) { for (int i = 0; i<n; ++i) for (int j = 0, d; j<n; ++j) { scanf("%d", &d); if (i != j) dis[i].push_back(make_pair(d, j)); } prim(n); for (int i = 0; i<maxn; ++i) dis[i].clear(); } return 0;}