kruskal、并查集
畅通工程（已知部分联通）
//#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
//#define int long long
const int N=1005;
struct edge{
int u,v,f;//起点终点是否有边，权值为1
edge(int u,int v,int f):u(u),v(v),f(f){}
bool operator<(const edge& n)const{
return f>n.f;//f=1代表u、v之间已经修路，优先选
}
};
vector<edge> e;
int n,m;
int fa[N];
int find(int x){
if(x==fa[x])return x;
return fa[x]=find(fa[x]);
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
while(cin>>n>>m){
if(n==0)break;
int u,v;
e.clear();
for(int i=1;i<=m;i++){
cin>>u>>v;
e.push_back(edge(u,v,1));
}
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
e.push_back(edge(i,j,0));
}
}
for(int i=1;i<=n;i++)fa[i]=i;
sort(e.begin(),e.end());
int cnt=0;//n个顶点要收n-1条边
int res=0;
int s=e.size();
for(int i=0;i<s;i++){
if(cnt==n-1)break;
int x=e[i].u;
int y=e[i].v;
int fx=find(x);
int fy=find(y);
if(fx!=fy){
if(!e[i].f)res+=1;
cnt++;
fa[fx]=fy;
}
}
cout<<res<<endl;
}
return 0;
}
畅通工程再续
这道题非常奇异，每个我严谨的地方都给我带来一次wa
最后一组输入后面的空行居然非输不可
double比较大小不许用EPS
//#include <bits/stdc++.h>
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <iomanip>
#include <vector>
#include <algorithm>
using namespace std;
//#define int long long
#define EPS 1e-8
const int N=105;
int fa[N];
int find(int x){
if(x==fa[x])return x;
return fa[x]=find(fa[x]);
}
struct node{
int sign,x,y;
};
int n,m;
vector<node> v;
struct edge{
int u,v;
double w;
bool operator<(const edge& a){
return w<a.w;//小于一个负数
}
};
vector<edge> e;
double fun(int x1,int y1,int x2,int y2){
return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin>>t;
int x,y;
while(t--){
v.clear();
e.clear();//多组输入用了容器要小心哪
cin>>n;
for(int i=1;i<=n;i++){
cin>>x>>y;
v.push_back({i,x,y});
fa[i]=i;
}
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
double len=fun(v[i].x,v[i].y,v[j].x,v[j].y);
if(len>=10.0&&len<=1000.0){
e.push_back({v[i].sign,v[j].sign,len});
}
}
}
sort(e.begin(),e.end());
int cnt=0;//收齐n-1条边
double res=0;
int si=e.size();
for(int i=0;i<si;i++){
if(cnt==n-1)break;
int x=e[i].u;
int y=e[i].v;
int fx=find(x);
int fy=find(y);
if(fx!=fy){
cnt++;
res+=e[i].w;
fa[fx]=fy;
}
}
if(cnt==n-1)cout<<fixed<<setprecision(1)<<res*100<<endl;
else cout<<"oh!"<<endl;
// if(t)cout<<endl;
}
return 0;
}
不知道我EPS用错在哪儿
//#include <bits/stdc++.h>
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <iomanip>
#include <vector>
#include <algorithm>
using namespace std;
//#define int long long
#define EPS 1e-8
const int N=105;
int fa[N];
int find(int x){
if(x==fa[x])return x;
return fa[x]=find(fa[x]);
}
struct node{
int sign,x,y;
};
int n,m;
vector<node> v;
struct edge{
int u,v;
double w;
bool operator<(const edge& a){
return w-a.w<-EPS;//小于一个负数
}
};
vector<edge> e;
double fun(int x1,int y1,int x2,int y2){
return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin>>t;
int x,y;
while(t--){
v.clear();
e.clear();//多组输入用了容器要小心哪
cin>>n;
for(int i=1;i<=n;i++){
cin>>x>>y;
v.push_back({i,x,y});
fa[i]=i;
}
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
double len=fun(v[i].x,v[i].y,v[j].x,v[j].y);
if(len-10.0>EPS&&len-1000.0<-EPS){
e.push_back({v[i].sign,v[j].sign,len});
}
}
}
sort(e.begin(),e.end());
int cnt=0;//收齐n-1条边
double res=0;
int si=e.size();
for(int i=0;i<si;i++){
if(cnt==n-1)break;
int x=e[i].u;
int y=e[i].v;
int fx=find(x);
int fy=find(y);
if(fx!=fy){
cnt++;
res+=e[i].w;
fa[fx]=fy;
}
}
if(cnt==n-1)cout<<fixed<<setprecision(1)<<res*100<<endl;
else cout<<"oh!"<<endl;
// if(t)cout<<endl;
}
return 0;
}
