图

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;
}