首先膜拜膜拜青島二中的 aKc大牛啊，我徹底給跪了！！！
差距太大，好好努力吧！！！
算法，數(shù)據(jù)結(jié)構(gòu)，C++，STL。需要去學(xué)的啊，下午開始學(xué)吧學(xué)吧
圖的操作，使用集合來維護，把操作序列倒過來看，割邊則看做兩個集合的合并。
STL 的set和multiset 很強大啊，第一用STL寫東西
wangs ,你該努力了，大牛之路，遠著呢。
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <list>
#include <stdexcept>
#include <functional>
#include <utility>
#include <ctime>
#include <cmath>
#include <climits>
using namespace std;
typedef pair<int, int> PII;
const int MAXN = 20010, MAXM = 60010, MAXQ = 300010;
int value[MAXN], query[MAXQ][3];
multiset<PII> e;
multiset<int> v[MAXN];
int pre[MAXN];
int root(int a)
{
if(pre[a] != a)
pre[a] = root(pre[a]);
return pre[a];
}
int unionSet(int a, int b)
{
multiset<int>::iterator it;
a = root(a), b = root(b);
if(a == b)
return 0;
if(v[a].size() > v[b].size())
swap(a, b);
for (it = v[a].begin(); it != v[a].end(); it++)
v[b].insert(*it);
v[a].clear();
pre[a] = b;
return 0;
}
int update(int a, int x)
{
int ta = a;
a = root(a);
v[a].erase(v[a].find(value[ta]));
v[a].insert(x);
value[ta] = x;
return 0;
}
int main()
{
int n, m, q;
int a, b;
int i,u;
int cas=0;
char ch[3];
double ct = 0, sum = 0;
multiset<PII>::iterator it;
multiset<int>::iterator tp;
while(scanf("%d%d%d",&n,&m,&q)==3)
{
e.clear();
for (i = 1; i <= n; i++)
v[i].clear();
for (i = 1; i <= n; i++)
{
scanf("%d", &value[i]);
pre[i] = i;
}
for (i = 0; i < m; i++)
{
scanf("%d%d", &a, &b);
if(a > b)
swap(a, b);
e.insert(PII(a, b));
}
for (i = 0; i < q; i++)
{
scanf("%s", &ch);
scanf("%d%d", &query[i][1], &query[i][2]);
query[i][0] = ch[0];
if(ch[0] == 'E')
{
if(query[i][1] > query[i][2])
swap(query[i][1], query[i][2]);
it = e.find(PII(query[i][1], query[i][2]));
e.erase(it);
}
else if(ch[0] == 'U')
swap(value[query[i][1]], query[i][2]);
}
for (i = 1; i <= n; i++)
v[i].insert(value[i]);
for (it = e.begin(); it != e.end(); it++)
unionSet(it->first, it->second);
// for (it = e.begin(); it != e.end(); it++)
// printf("%d %d\n",it->first, it->second);
ct=0;
sum=0;
for(int i = q - 1; i >= 0; i--)
{
if(query[i][0] == 'E')
unionSet(query[i][1], query[i][2]);
else if(query[i][0] == 'U')
update(query[i][1], query[i][2]);
else
{
ct += 1;
u = root(query[i][1]);
tp = v[u].lower_bound(query[i][2]);
if(tp != v[u].end())
sum += *tp;
// printf("%d %d\n",u,*tp);
}
}
printf("Case %d: %0.3lf\n",++cas,(double)sum/ct);
}
return 0;
}