题意：最小生成树模板题
题解：Boruvka算法；
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+50,maxm=2e5+5;
const int MaxN = 5000 + 5, MaxM = 200000 + 5;
int N, M;
int U[MaxM], V[MaxM], W[MaxM],Best[maxn];
bool used[MaxM];
namespace DSU
{
const int maxn=1e7;
int father[maxn],rank[maxn];
void init(int n){for(int i=1;i<=n;i++) {father[i]=i;rank[i]=1;}}
int find(int x){return x==father[x]?x:father[x]=find(father[x]);}
void unionSet(int x,int y)
{
int xx=find(x),yy=find(y);
if(xx==yy) return;
if(rank[xx]>rank[yy]) swap(xx,yy);
father[xx]=yy;rank[yy]+=rank[xx];
}
}
using namespace DSU;
inline bool Better(int x, int y) {
if (y == 0) return true;
if (W[x] != W[y]) return W[x] < W[y];
return x < y;
}
void Boruvka() {
init(N);
int merged = 0, sum = 0;
bool update = true;
while (update) {
update = false;
memset(Best, 0, sizeof Best);
for (int i = 1; i <= M; ++i) {
if (used[i] == true) continue;
int p = find(U[i]), q = find(V[i]);
if (p == q) continue;
if (Better(i, Best[p]) == true) Best[p] = i;
if (Better(i, Best[q]) == true) Best[q] = i;
}
for (int i = 1; i <= N; ++i)
if (Best[i] != 0 && used[Best[i]] == false) {
update = true;
merged++; sum += W[Best[i]];
used[Best[i]] = true;
unionSet(U[Best[i]],V[Best[i]]);
}
}
if (merged == N - 1) printf("%d
", sum);
else puts("orz");
}
int main() {
scanf("%d %d", &N, &M);
for (int i = 1; i <= M; ++i)scanf("%d%d%d", &U[i], &V[i], &W[i]);
Boruvka();
system("pause");
return 0;
}
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+50;
int N, M;
int U[maxn], V[maxn], W[maxn],Best[maxn];
bool used[maxn];int imax=0;
namespace DSU
{
//const int maxn=1e7;
int father[maxn],rank[maxn];
void init(int n){for(int i=1;i<=n;i++) {father[i]=i;rank[i]=1;}}
int find(int x){return x==father[x]?x:father[x]=find(father[x]);}
void unionSet(int x,int y)
{
int xx=find(x),yy=find(y);
if(xx==yy) return;
if(rank[xx]>rank[yy]) swap(xx,yy);
father[xx]=yy;rank[yy]+=rank[xx];
}
}
using namespace DSU;
inline bool Better(int x, int y) {
if (y == 0) return true;
if (W[x] != W[y]) return W[x] < W[y];
return x < y;
}
void Boruvka() {
init(N);
int merged = 0, sum = 0;
bool update = true;
while (update) {
update = false;
memset(Best, 0, sizeof Best);
for (int i = 1; i <= M; ++i) {
if (used[i] == true) continue;
int p = find(U[i]), q = find(V[i]);
if (p == q) continue;
if (Better(i, Best[p]) == true) Best[p] = i;
if (Better(i, Best[q]) == true) Best[q] = i;
}
for (int i = 1; i <= N; ++i)
if (Best[i] != 0 && used[Best[i]] == false) {
update = true;
merged++; sum += W[Best[i]];
used[Best[i]] = true;imax=max(imax,W[Best[i]]);
unionSet(U[Best[i]],V[Best[i]]);
}
}
}
int monkey[505];
pair<int,int>tree[1005];
int main() {
int Monkeynum;scanf("%d", &Monkeynum);
for(int i=1;i<=Monkeynum;++i) scanf("%d",&monkey[i]);
scanf("%d",&N);
for(int i=1;i<=N;i++)scanf("%d%d",&tree[i].first,&tree[i].second);
for(int i=1;i<N;i++)
for(int j=i+1;j<=N;j++)
++M,U[M]=i,V[M]=j,W[M]=(tree[i].first-tree[j].first)*(tree[i].first-tree[j].first)+(tree[i].second-tree[j].second)*(tree[i].second-tree[j].second);
Boruvka();
int ans=0;
for(int i=1;i<=Monkeynum;++i) if(monkey[i]*monkey[i]>=imax)ans++;
printf("%d",ans);
//system("pause");
return 0;
}
待补：
Atcoder keyence2019 E
51nod 1496