hdu 2419 离线逆序操作+并查集

此题关键在于维护点的连通性以及连通块的信息，容易想到并查集，但是并查集却不支持删边操作，于是考虑逆序处理，这样删边就变成了加边操作，每一个连通块的信息可以用stl中的multiset来维护，注意集合合并的时候要启发式合并（这里是按照集合的大小来合并，每次小的集合合并到大的集合里），不然会超时。

  1 #include <iostream>
  2 #include <cstring>
  3 #include <cstdio>
  4 #include <set>
  5 using namespace std;
  6 
  7 const int N = 20001;
  8 const int M = 300001;
  9 int f[N];
 10 int v[N];
 11 multiset<int> s[N];
 12 multiset<int> edge[N];
 13 int n, m, q;
 14 
 15 struct Op
 16 {
 17     char cmd[2];
 18     int x, y;
 19 } op[M];
 20 
 21 int findf( int x )
 22 {
 23     if ( f[x] != x ) f[x] = findf( f[x] );
 24     return f[x];
 25 }
 26 
 27 void union_set( int x, int y )
 28 {
 29     x = findf(x), y = findf(y);
 30     if ( x != y )
 31     {
 32         if ( s[x].size() > s[y].size() ) swap( x, y );
 33         f[x] = y;
 34         for ( multiset<int>::iterator it = s[x].begin(); it != s[x].end(); it++ )
 35         {
 36             s[y].insert( *it );
 37         }
 38         s[x].clear();
 39     }
 40 }
 41 
 42 int main ()
 43 {
 44     int _case = 1;
 45     while ( scanf("%d%d%d", &n, &m, &q) != EOF )
 46     {
 47         for ( int i = 1; i <= n; i++ )
 48         {
 49             scanf("%d", &v[i]);
 50             edge[i].clear();
 51         }
 52         for ( int i = 1; i <= m; i++ )
 53         {
 54             int u, v;
 55             scanf("%d%d", &u, &v);
 56             if ( u > v ) swap( u, v );
 57             edge[u].insert(v);
 58         }
 59         for ( int i = 1; i <= q; i++ )
 60         {
 61             scanf("%s%d%d", &op[i].cmd, &op[i].x, &op[i].y);
 62             if ( op[i].cmd[0] == 'U' )
 63             {
 64                 int tn = op[i].y;
 65                 op[i].y = v[op[i].x];
 66                 v[op[i].x] = tn;
 67             }
 68             else if ( op[i].cmd[0] == 'E' )
 69             {
 70                 if ( op[i].x > op[i].y ) swap( op[i].x, op[i].y );
 71                 edge[op[i].x].erase( edge[op[i].x].find(op[i].y) );
 72             }
 73         }
 74         for ( int i = 1; i <= n; i++ )
 75         {
 76             f[i] = i;
 77             s[i].clear();
 78             s[i].insert(v[i]);
 79         }
 80         for ( int i = 1; i <= n; i++ )
 81         {
 82             for ( multiset<int>::iterator it = edge[i].begin(); it != edge[i].end(); it++ )
 83             {
 84                 union_set( i, (*it) );
 85             }
 86         }
 87         int cnt = 0, sum = 0;
 88         for ( int i = q; i >= 1; i-- )
 89         {
 90             if ( op[i].cmd[0] == 'F' )
 91             {
 92                 cnt++;
 93                 int x = op[i].x, y = op[i].y;
 94                 x = findf(x);
 95                 multiset<int>::iterator it = s[x].lower_bound(y);
 96                 if ( it != s[x].end() )
 97                 {
 98                     sum += (*it);
 99                 }
100             }
101             else if ( op[i].cmd[0] == 'U' )
102             {
103                 int x = op[i].x, y = op[i].y;
104                 int fx = findf(x);
105                 multiset<int>::iterator it = s[fx].find(v[x]);
106                 s[fx].erase(it);
107                 s[fx].insert(y);
108                 v[x] = y;
109             }
110             else
111             {
112                 union_set( op[i].x, op[i].y );
113             }
114         }
115         double avg = ( sum * 1.0 ) / ( cnt * 1.0 );
116         printf("Case %d: %.3f
", _case++, avg);
117     }
118     return 0;
119 }