天天看点
返回

HDU 3726 Graph and Queries

Description

You are given an undirected graph with N vertexes and M edges. Every vertex in this graph has an integer value assigned to it at the beginning. You're also given a sequence of operations and you need to process them as requested. Here's a list of the possible operations that you might encounter: 

1)  Deletes an edge from the graph. 

The format is [D X], where X is an integer from 1 to M, indicating the ID of the edge that you should delete. It is guaranteed that no edge will be deleted more than once. 

2)  Queries the weight of the vertex with K-th maximum value among all vertexes currently connected with vertex X (including X itself).

The format is [Q X K], where X is an integer from 1 to N, indicating the id of the vertex, and you may assume that K will always fit into a 32-bit signed integer. In case K is illegal, the value for that query will be considered as undefined, and you should return 0 as the answer to that query. 

3)  Changes the weight of a vertex. 

The format is [C X V], where X is an integer from 1 to N, and V is an integer within the range [-10 

6, 10 

6]. 

The operations end with one single character, E, which indicates that the current case has ended. 

For simplicity, you only need to output one real number - the average answer of all queries. 

Input

There are multiple test cases in the input file. Each case starts with two integers N and M (1 <= N <= 2 * 10 

4, 0 <= M <= 6 * 10 

4), the number of vertexes in the graph. The next N lines describes the initial weight of each vertex (-106 <= weight[i] <= 10 

6). The next part of each test case describes the edges in the graph at the beginning. Vertexes are numbered from 1 to N. The last part of each test case describes the operations to be performed on the graph. It is guaranteed that the number of query operations [Q X K] in each case will be in the range [1, 2 * 10 

5], and there will be no more than 2 * 10 

5 operations that change the values of the vertexes [C X V]. 

There will be a blank line between two successive cases. A case with N = 0, M = 0 indicates the end of the input file and this case should not be processed by your program. 

Output

For each test case, output one real number � the average answer of all queries, in the format as indicated in the sample output. Please note that the result is rounded to six decimal places.

Sample Input

3 3

10

20

30

1 2

2 3

1 3

D 3

Q 1 2

Q 2 1

D 2

Q 3 2

C 1 50

Q 1 1

E

3 3

10

20

20

1 2

2 3

1 3

Q 1 1

Q 1 2

Q 1 3

E

0 0

Sample Output

Case 1: 25.000000

Case 2: 16.666667

Hint

For the first sample: D 3 -- deletes the 3rd edge in the graph (the remaining edges are (1, 2) and (2, 3)) Q 1 2 -- finds the vertex with the second largest value among all vertexes connected with 1. The answer is 20. Q 2 1 -- finds the vertex with the largest value among all vertexes connected with 2. The answer is 30. D 2 -- deletes the 2nd edge in the graph (the only edge left after this operation is (1, 2)) Q 3 2 -- finds the vertex with the second largest value among all vertexes connected with 3. The answer is 0 (Undefined). C 1 50 -- changes the value of vertex 1 to 50. Q 1 1 -- finds the vertex with the largest value among all vertex connected with 1. The answer is 50. E -- This is the end of the current test case. Four queries have been evaluated, and the answer to this case is (20 + 30 + 0 + 50) / 4 = 25.000. For the second sample, caution about the vertex with same weight: Q 1 1 � the answer is 20 Q 1 2 � the answer is 20 Q 1 3 � the answer is 10

这题题意挺简单的，就是一张图，每个点有权值，然后三种操作，删边，该权值，求和x连通的第k大权值

这题第一眼看就是倒过来，然后加边维护就好了，然而要维护第k大会比较难，一开始我以为合并有什么巧妙的办法，然而后来发现都是暴力合并的，其实想想也是，暴力把少的加到多的里面，效率最多也就是多个log。然后是此题的坑点也很多，细节方面一定要注意，每个点建一个树，那么根之间的传递是必须要注意的，可以用并查集或者在删点的时候算好父节点。求的第k大，但是k还有可能是负的。。。

没用并查集的

#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<iostream>
#include<algorithm>
#include<bitset>
#include<functional>
using namespace std;
typedef long long LL;
const int maxn = 5e5 + 10;
const int mod = 1e9 + 7;
int n, m, sz, x, tot, cas = 0;
int v[maxn], ft[maxn], nt[maxn], root[maxn];
char s[5];

void add(int x, int y)
{
	v[sz] = y;	nt[sz] = ft[x];	 ft[x] = sz++;
}

struct point
{
	int x, y, z;
	void read(){ scanf("%d%d", &x, &y); }
}p[maxn], q[maxn];

struct Splays
{
	const static int maxn = 5e5 + 10;			//节点个数
	const static int INF = 0x7FFFFFFF;			//int最大值
	int ch[maxn][2], F[maxn], sz;				//左右儿子，父亲节点和节点总个数
	int A[maxn], C[maxn], S[maxn], now;
	int Node(int f, int a, int s) { S[sz] = C[sz] = s; A[sz] = a; ch[sz][0] = ch[sz][1] = 0; F[sz] = f; return sz++; }//申请一个新节点
	void clear(){ sz = 1; ch[0][0] = ch[0][1] = F[0] = 0; S[0] = C[0] = 0; }//清空操作
	void rotate(int x, int k)
	{
		int y = F[x]; ch[y][!k] = ch[x][k]; F[ch[x][k]] = y;
		if (F[y]) ch[F[y]][y == ch[F[y]][1]] = x;
		F[x] = F[y];    F[y] = x;	ch[x][k] = y;
		C[x] = C[y];	C[y] = C[ch[y][0]] + C[ch[y][1]] + S[y];
	}
	void Splay(int x, int r)
	{
		while (F[x] != r)
		{
			if (F[F[x]] == r) { rotate(x, x == ch[F[x]][0]); return; }
			int y = x == ch[F[x]][0], z = F[x] == ch[F[F[x]]][0];
			y^z ? (rotate(x, y), rotate(x, z)) : (rotate(F[x], z), rotate(x, y));
		}
	}
	int build(int v){ return Node(0, v, 1); }
	int find(int x,int k)
	{
		int fx = root[x];
		while (F[fx]) fx = F[fx];
		if (C[fx] < k||k<=0) return 0;
		k = C[fx] + 1 - k;
		for (int i = fx; i;)
		{
			if (C[ch[i][0]] >= k) { i = ch[i][0]; continue; }
			if (C[ch[i][0]] + S[i] >= k) return A[i];
			k -= C[ch[i][0]] + S[i];	i = ch[i][1];
		}
	}
	void insert(int x)
	{
		ch[x][0] = ch[x][1] = 0;  F[x] = now;	C[x] = S[x];
		for (int i = now; i; i = ch[i][A[x] > A[i]])
		{
			C[i] += S[x];
			if (A[x] == A[i]) { S[i] += S[x]; Splay(i, 0); now = i; return; }
			if (!ch[i][A[x] > A[i]]){ ch[i][A[x] > A[i]] = x; F[x] = i; Splay(x, 0); now = x; return; }
		}
	}
	void dfs(int x)
	{
		if (!x) return;
		dfs(ch[x][0]);
		dfs(ch[x][1]);
		insert(x);
	}
	void merge(int x, int y)
	{
		int fx = root[x], fy = root[y];
		while (F[fx]) fx = F[fx];
		while (F[fy]) fy = F[fy];
		if (fx == fy) return;
		if (C[fx] > C[fy]) swap(fx, fy);
		now = fy; dfs(fx);	root[x] = root[y] = now;
	}
	void change(int x, int y, int z)
	{
		int fx = root[x], zz = Node(0, z, 1);
		while (F[fx]) fx = F[fx];
		now = fx;	insert(zz);
		for (int i = now; i; i = ch[i][y > A[i]]) if (A[i] == y) { Splay(i, 0); now = i; break; }
		if (S[now] > 1) { S[now]--, C[now]--; return; }
		if (!ch[now][0] || !ch[now][1]){ F[now] = ch[now][0] + ch[now][1]; now = F[now]; F[now] = 0; root[x] = now; return; }
		for (int i = ch[now][0]; i; i = ch[i][1]) if (!ch[i][1]) { Splay(i, 0); now = i; break; }
		int temp = ch[now][1];	ch[now][1] = ch[temp][1];	F[ch[now][1]] = now;	C[now]--;	root[x] = now;
	}
}solve;


int main()
{
	while (scanf("%d%d", &n, &m) != EOF, n + m)
	{
		sz = 0;	solve.clear();
		for (int i = 1; i <= n; i++) scanf("%d", &x), ft[i] = -1, add(i, x);
		for (int i = 1; i <= m; i++) p[i].read(), p[i].z = 1;
		for (tot = 0; scanf("%s", s), s[0] != 'E'; tot++)
		{
			q[tot].z = s[0] == 'D' ? 0 : s[0] == 'Q' ? 1 : 2;
			if (!q[tot].z)
			{
				scanf("%d", &q[tot].x);
				p[q[tot].x].z = 0;
			}
			else
			{
				q[tot].read();
				if (q[tot].z == 2) add(q[tot].x, q[tot].y);
			}
		}
		for (int i = 1; i <= n; i++) root[i] = solve.build(v[ft[i]]);
		for (int i = 1; i <= m; i++) if (p[i].z) solve.merge(p[i].x, p[i].y);
		LL ans = 0, div = 0;
		for (int i = tot - 1; i >= 0; i--)
		{
			if (!q[i].z) solve.merge(p[q[i].x].x, p[q[i].x].y);
			else
			{
				if (q[i].z == 1) ans += solve.find(q[i].x, q[i].y), div++;
				else
				{
					ft[q[i].x] = nt[ft[q[i].x]];
					solve.change(q[i].x, q[i].y, v[ft[q[i].x]]);
				}
			}
		}
		printf("Case %d: %.6lf\n", ++cas, 1.0*ans / div);
	}
	return 0;
}

用并查集的

#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<iostream>
#include<algorithm>
#include<bitset>
#include<functional>
using namespace std;
typedef long long LL;
const int maxn = 5e5 + 10;
const int mod = 1e9 + 7;
int n, m, sz, x, tot, cas = 0;
int v[maxn], ft[maxn], nt[maxn], root[maxn], fa[maxn];
char s[10];

void add(int x, int y)
{
	v[sz] = y;	nt[sz] = ft[x];	 ft[x] = sz++;
}

int get(int x)
{
	return x == fa[x] ? x : fa[x] = get(fa[x]);
}

struct point
{
	int x, y, z;
	void read(){ scanf("%d%d", &x, &y); }
}p[maxn], q[maxn];

struct Splays
{
	const static int maxn = 5e5 + 10;			//节点个数
	const static int INF = 0x7FFFFFFF;			//int最大值
	int ch[maxn][2], F[maxn], sz;				//左右儿子，父亲节点和节点总个数
	int A[maxn], C[maxn], S[maxn], now;
	int Node(int f, int a, int s) { S[sz] = C[sz] = s; A[sz] = a; ch[sz][0] = ch[sz][1] = 0; F[sz] = f; return sz++; }//申请一个新节点
	void clear(){ sz = 1; ch[0][0] = ch[0][1] = F[0] = 0; S[0] = C[0] = 0; }//清空操作
	void rotate(int x, int k)
	{
		int y = F[x]; ch[y][!k] = ch[x][k]; F[ch[x][k]] = y;
		if (F[y]) ch[F[y]][y == ch[F[y]][1]] = x;
		F[x] = F[y];    F[y] = x;	ch[x][k] = y;
		C[x] = C[y];	C[y] = C[ch[y][0]] + C[ch[y][1]] + S[y];
	}
	void Splay(int x, int r)
	{
		while (F[x] != r)
		{
			if (F[F[x]] == r) { rotate(x, x == ch[F[x]][0]); return; }
			int y = x == ch[F[x]][0], z = F[x] == ch[F[F[x]]][0];
			y^z ? (rotate(x, y), rotate(x, z)) : (rotate(F[x], z), rotate(x, y));
		}
	}
	int build(int v){ return Node(0, v, 1); }
	int find(int x,int k)
	{
		int fx = get(x), rx = root[fx];
		Splay(rx, 0);
		if (C[rx] < k || k <= 0) return 0;
		k = C[rx] + 1 - k;
		for (int i = rx; i;)
		{
			if (C[ch[i][0]] >= k) { i = ch[i][0]; continue; }
			if (C[ch[i][0]] + S[i] >= k) return A[i];
			k -= C[ch[i][0]] + S[i];	i = ch[i][1];
		}
	}
	void insert(int x)
	{
		F[x] = ch[x][0] = ch[x][1] = 0; C[x] = S[x];
		for (int i = now; i; i = ch[i][A[x] > A[i]])
		{
			C[i] += S[x];
			if (A[x] == A[i]) { S[i] += S[x]; Splay(i, 0); now = i; return; }
			if (!ch[i][A[x] > A[i]]){ ch[i][A[x] > A[i]] = x; F[x] = i; Splay(x, 0); now = x; return; }
		}
	}
	void dfs(int x)
	{
		if (!x) return;
		dfs(ch[x][0]);
		dfs(ch[x][1]);
		insert(x);
	}
	void merge(int x, int y)
	{
		int fx = get(x), fy = get(y);
		if (fx == fy) return;
		int rx = root[fx], ry = root[fy];
		Splay(rx, 0);	Splay(ry, 0);
		if (C[rx] > C[ry]) swap(rx, ry), swap(fx, fy);
		fa[fx] = fy; now = ry; dfs(rx);	root[fy] = now;
	}
	void change(int x, int y, int z)
	{
		int fx = get(x), rx = root[fx], zz = Node(0, z, 1);
		Splay(rx, 0);   now = rx;	insert(zz);
		for (int i = now; i; i = ch[i][y > A[i]]) if (A[i] == y) { Splay(i, 0); now = i; break; }
		if (S[now] > 1) { S[now]--, C[now]--; return; }
		if (!ch[now][0] || !ch[now][1]){ now = ch[now][0] + ch[now][1]; F[now] = 0; root[fx] = now; return; }
		for (int i = ch[now][0]; i; i = ch[i][1]) if (!ch[i][1]) { Splay(i, 0); now = i; break; }
		int temp = ch[now][1];	ch[now][1] = ch[temp][1];	F[ch[now][1]] = now;	C[now]--;	root[fx] = now;
	}
}solve;

int main()
{
	while (scanf("%d%d", &n, &m) != EOF, n + m)
	{
		sz = 0;	solve.clear();
		for (int i = 1; i <= n; i++) scanf("%d", &x), ft[i] = -1, add(i, x), fa[i] = i;
		for (int i = 1; i <= m; i++) p[i].read(), p[i].z = 1;
		for (tot = 0; scanf("%s", s), s[0] != 'E'; tot++)
		{
			q[tot].z = s[0] == 'D' ? 0 : s[0] == 'Q' ? 1 : 2;
			if (!q[tot].z)
			{
				scanf("%d", &q[tot].x);
				p[q[tot].x].z = 0;
			}
			else
			{
				q[tot].read();
				if (q[tot].z == 2) add(q[tot].x, q[tot].y);
			}
		}
		for (int i = 1; i <= n; i++) root[i] = solve.build(v[ft[i]]);
		for (int i = 1; i <= m; i++) if (p[i].z) solve.merge(p[i].x, p[i].y);
		double ans = 0; 
		int div = 0;
		for (int i = tot - 1; i >= 0; i--)
		{
			if (!q[i].z) solve.merge(p[q[i].x].x, p[q[i].x].y);
			else
			{
				if (q[i].z == 1) ans += solve.find(q[i].x, q[i].y), div++;
				else
				{
					ft[q[i].x] = nt[ft[q[i].x]];
					solve.change(q[i].x, q[i].y, v[ft[q[i].x]]);
				}
			}
		}
		printf("Case %d: %.6f\n", ++cas, ans / div);
	}
	return 0;
}

相同权值不合并版

#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<iostream>
#include<algorithm>
#include<bitset>
#include<functional>
using namespace std;
typedef long long LL;
const int maxn = 5e5 + 10;
const int mod = 1e9 + 7;
int n, m, sz, x, tot, cas = 0;
int v[maxn], ft[maxn], nt[maxn], root[maxn], fa[maxn];
char s[10];

void add(int x, int y)
{
	v[sz] = y;	nt[sz] = ft[x];	 ft[x] = sz++;
}

int get(int x)
{
	return x == fa[x] ? x : fa[x] = get(fa[x]);
}

struct point
{
	int x, y, z;
	void read(){ scanf("%d%d", &x, &y); }
}p[maxn], q[maxn];

struct Splays
{
	const static int maxn = 5e5 + 10;			//节点个数
	const static int INF = 0x7FFFFFFF;			//int最大值
	int ch[maxn][2], F[maxn], sz;				//左右儿子，父亲节点和节点总个数
	int A[maxn], C[maxn], now;
	int Node(int f, int a) { C[sz] = 1; A[sz] = a; ch[sz][0] = ch[sz][1] = 0; F[sz] = f; return sz++; }//申请一个新节点
	void clear(){ sz = 1; ch[0][0] = ch[0][1] = F[0] = 0; C[0] = 0; }//清空操作
	void rotate(int x, int k)
	{
		int y = F[x]; ch[y][!k] = ch[x][k]; F[ch[x][k]] = y;
		if (F[y]) ch[F[y]][y == ch[F[y]][1]] = x;
		F[x] = F[y];    F[y] = x;	ch[x][k] = y;
		C[x] = C[y];	C[y] = C[ch[y][0]] + C[ch[y][1]] + 1;
	}
	void Splay(int x, int r)
	{
		while (F[x] != r)
		{
			if (F[F[x]] == r) { rotate(x, x == ch[F[x]][0]); return; }
			int y = x == ch[F[x]][0], z = F[x] == ch[F[F[x]]][0];
			y^z ? (rotate(x, y), rotate(x, z)) : (rotate(F[x], z), rotate(x, y));
		}
	}
	int build(int v){ return Node(0, v); }
	int find(int x,int k)
	{
		int fx = get(x), rx = root[fx];
		Splay(rx, 0);
		if (C[rx] < k || k <= 0) return 0;
		k = C[rx] + 1 - k;
		for (int i = rx; i;)
		{
			if (C[ch[i][0]] >= k) { i = ch[i][0]; continue; }
			if (C[ch[i][0]] + 1 >= k) return A[i];
			k -= C[ch[i][0]] + 1;	i = ch[i][1];
		}
	}
	void insert(int x)
	{
		F[x] = ch[x][0] = ch[x][1] = 0; C[x] = 1;
		for (int i = now; i; i = ch[i][A[x] > A[i]])
		{
			C[i] += 1;
			if (!ch[i][A[x] > A[i]]){ ch[i][A[x] > A[i]] = x; F[x] = i; Splay(x, 0); now = x; return; }
		}
	}
	void dfs(int x)
	{
		if (!x) return;
		dfs(ch[x][0]);
		dfs(ch[x][1]);
		insert(x);
	}
	void merge(int x, int y)
	{
		int fx = get(x), fy = get(y);
		if (fx == fy) return;
		int rx = root[fx], ry = root[fy];
		Splay(rx, 0);	Splay(ry, 0);
		if (C[rx] > C[ry]) swap(rx, ry), swap(fx, fy);
		fa[fx] = fy; now = ry; dfs(rx);	root[fy] = now;
	}
	void change(int x, int y, int z)
	{
		int fx = get(x), rx = root[fx], zz = Node(0, z);
		Splay(rx, 0);   now = rx;	insert(zz);
		for (int i = now; i; i = ch[i][y > A[i]]) if (A[i] == y) { Splay(i, 0); now = i; break; }
		if (!ch[now][0] || !ch[now][1]){ now = ch[now][0] + ch[now][1]; F[now] = 0; root[fx] = now; return; }
		for (int i = ch[now][0]; i; i = ch[i][1]) if (!ch[i][1]) { Splay(i, 0); now = i; break; }
		int temp = ch[now][1];	ch[now][1] = ch[temp][1];	F[ch[now][1]] = now;	C[now]--;	root[fx] = now;
	}
}solve;

int main()
{
	while (scanf("%d%d", &n, &m) != EOF, n + m)
	{
		sz = 0;	solve.clear();
		for (int i = 1; i <= n; i++) scanf("%d", &x), ft[i] = -1, add(i, x), fa[i] = i;
		for (int i = 1; i <= m; i++) p[i].read(), p[i].z = 1;
		for (tot = 0; scanf("%s", s), s[0] != 'E'; tot++)
		{
			q[tot].z = s[0] == 'D' ? 0 : s[0] == 'Q' ? 1 : 2;
			if (!q[tot].z)
			{
				scanf("%d", &q[tot].x);
				p[q[tot].x].z = 0;
			}
			else
			{
				q[tot].read();
				if (q[tot].z == 2) add(q[tot].x, q[tot].y);
			}
		}
		for (int i = 1; i <= n; i++) root[i] = solve.build(v[ft[i]]);
		for (int i = 1; i <= m; i++) if (p[i].z) solve.merge(p[i].x, p[i].y);
		double ans = 0; 
		int div = 0;
		for (int i = tot - 1; i >= 0; i--)
		{
			if (!q[i].z) solve.merge(p[q[i].x].x, p[q[i].x].y);
			else
			{
				if (q[i].z == 1) ans += solve.find(q[i].x, q[i].y), div++;
				else
				{
					ft[q[i].x] = nt[ft[q[i].x]];
					solve.change(q[i].x, q[i].y, v[ft[q[i].x]]);
				}
			}
		}
		printf("Case %d: %.6f\n", ++cas, ans / div);
	}
	return 0;
}
HDU #include 5e i++ 其他
上一篇: python中面向对象_简述Python中的面向对象编程的概念
下一篇: python完全支持面向对象编程_一篇非常全的Python 面向对象编程

继续阅读