P1636 Einstein学画画
欧拉路
// luogu-judger-enable-o2
// luogu-judger-enable-o2
#include <bits/stdc++.h>
using namespace std;
int n,m,ans;
int x,y;
int a[100001];
int main () {
cin >> n >>m;
for ( int i=1;i <=m;i++){
cin >>x>>y;
a[x]++;
a[y]++;
}
for (int i=1;i<=n;i++){
if (a[i]%2==1){
ans++;
}
}
if (ans==0||ans==2){
cout << 1;
}else{
cout << ans/2;
}
return 0;
}
P3958 [NOIP2017 提高组] 奶酪
并查集
#include<bits/stdc++.h>
#define int long long
using namespace std;
int T;
const int N = 100020;
int f[N] , f2[N];
int x[N] , y[N];
long long z[N];
int f1[N];
int tot1 , tot2;
int F(int x){
return f[x] == x ? x : f[x] = F(f[x]);
}
int n , h ;
long long r;
long long pf(int x ,int x2){
return (x - x2) * (x - x2);
}
signed main () {
cin >> T;
while(T --){
tot1 = 0 ;
tot2 = 0 ;
int flag = 0;
scanf("%lld%lld%lld" , &n , &h , &r);
for(int i = 1; i <= n ; i ++){
f[i] = i;
}
for(int i = 1 ; i <= n ; i ++){
scanf( "%lld%lld%lld" , &x[i] , &y[i] , &z[i]);
if(z[i] + r >= h){
tot1 ++;
f1[tot1] = i;
}
if(z[i] - r <= 0){
tot2 ++;
f2[tot2] = i;
}
for(int j = 1 ; j <= i ; j ++){
if(pf(x[i] , x[j]) + pf(y[i] , y[j]) > 4 * r * r)continue;
if(pf(x[i] , x[j]) + pf(y[i] , y[j]) + pf(z[i] , z[j]) <= 4 * r * r){
int a = F(i);
int b = F(j);
if(a != b){
f[a] = b;
}
}
}
}
for(int i = 1; i <= tot1 ; i ++){
for(int j = 1; j <= tot2 ; j ++){
if(F(f1[i]) == F(f2[j])){
flag = 1;
break;
}
}
}
if(flag){
puts("Yes");
}else{
puts("No");
}
}
return 0;
}
P1119 灾后重建
最短路
#include<bits/stdc++.h>
using namespace std;
int f[1020][1020];
int a[100020];
int n , q;
int m;
int main () {
cin >> n >> m;
for(int i = 0 ; i < n ;i ++){
scanf("%d" ,&a[i]);
for(int j = 0 ; j < n ; j++){
f[i][j] = 0x3f3f3f3f;
f[i][i] = 0;
}
}
for(int i = 0 ; i < m ; i++){
int x, y , z;
scanf("%d%d%d" ,&x, &y ,&z);
f[x][y] = f[y][x] = z;
}
cin >> q;
int now = 0;
while(q--){
int x , y , t;
scanf("%d%d%d" ,&x , &y , &t);
if(a[x] > t || a[y] > t) {
cout << -1 << endl;
continue;
}
while(a[now] <= t && now < n){
for(int i = 0 ; i < n; i ++){
for(int j = 0 ; j < n ; j ++){
if(f[i][j] > f[i][now] + f[now][j]){
f[j][i] = f[i][j] = f[i][now] + f[now][j];
}
}
}
now++;
}
if(f[x][y] == 0x3f3f3f3f){
cout << -1 << endl;
continue;
}else{
cout << f[x][y] << endl;
}
}
}
P2504 [HAOI2006]聪明的猴子
并查集
#include<bits/stdc++.h>
using namespace std;
struct node{
int x , y;
double dis;
}a[10000000];
bool cmp(node c , node e){
return c.dis < e.dis;
}
int n , m ;
int f[10000000];
int F(int x){
return f[x] == x ? x : f[x] = F(f[x]);
}
int mo[10000000];
int tx[10000000] , ty[10000000];
int main () {
cin >> n ;
for(int i = 1 ; i <= n ; i ++){
cin >> mo[i];
}
cin >> m;
for(int i = 1; i <= m ; i ++){
cin >> tx[i] >> ty[i];
f[i] = i;
}
int cnt = 0;
for(int i = 1; i <= m ; i ++){
for(int j = 1; j <= m && j != i ; j ++){
a[++cnt].x = i;
a[cnt].y = j;
a[cnt].dis = sqrt((tx[i] - tx[j]) * (tx[i] - tx[j]) + (ty[i] - ty[j]) * (ty[i] - ty[j]));
}
}
int lxh = m ;
int ans = 0;
sort(a + 1 , a + 1 + cnt , cmp);
for(int i = 1; i <= cnt ; i ++){
if(lxh == 1)break;
int xx = F(a[i].x) , yy = F(a[i].y);
if(xx != yy){
lxh --;
f[xx] = yy ;
ans = a[i].dis;
}
}
int sum = 0;
for(int i = 1 ; i <= n ; i ++){
if(mo[i] >= ans)sum ++;
}
cout << sum << endl;
}
P8654 [蓝桥杯 2017 国 C] 合根植物
并查集
#include<bits/stdc++.h>
using namespace std;
int n , m , k;
int v[1000002];
int cnt ;
int f[1000002];
int F(int x){
return f[x] == x ? x : f[x] = F(f[x]);
}
int ans;
int main () {
cin >> n >> m >> k;
for(int i = 1 ; i <= n ; i ++){
for(int j = 1; j <= m ;j ++){
f[++cnt] = cnt ;
}
}
for(int i = 1; i <= k ; i ++){
int x , y;
cin >> x >> y ;
int xx = F(x);
int yy = F(y);
f[xx] = yy;
}
for(int i = 1; i <= cnt ;i ++){
if(f[i] == i )ans ++ ;
}
cout << ans << endl;
}