codeforces 487E Tourists

如果不是uoj上有的话（听说这是China Round），我有可能就错过这道题目了（这是我有史以来为oi写的最长的代码，用了我一天TAT！）。

题目

传送门。

一个连通无向图，点上有权，支持两种操作：

修改某点的权值
询问点\(x\)到\(y\)的经过的最小的点（同一个点不能重复经过）

算法

这题想起来是不难的：

容易想到做一个强连通分量，每个分量里的点可以互相到达。

这时会有一个猜想：在一个分量里，是不是任意指定三点\(a,b,c\)，都有一条合法路径从\(a\)到\(b\)途中经过\(c\)呢。我当时想了想，也没严谨证明，觉得是对的，现在做完了觉得有必要证明一下，然后我就在解答里找到了这个：

Consider a biconnected graph with at least 3 vertices. If we remove any vertex or any edge, the graph is still connected.

We build a network on the graph. Let's use (u,v,w) to describe a directed edge from u to v with capacity w. For each edge (u,v) of the original graph, we build (u,v,1) and (v,u,1). Build (S,c,2), (a,T,1) and (b,T,1). For each vertex other than S,T,c, we should give a capacity of 1 to the vertex.

In order to give capacity to vertex u, we build two vertices u1,u2 instead of u. For each (v,u,w), build (v,u1,w). For each (u,v,w), build(u2,v,w). Finally build (u1,u2,1).

Hence, if the maximal flow from S to T is 2, there is a simple path from a to b going through c.

Now we consider the minimal cut of the network. It is easy to find that minimal cut <= 2, so let's prove minimal cut > 1, which means, no matter which edge of capacity 1 we cut, there is still a path from S to T.

If we cut an edge like (u1,u2,1), it is equivalent to set the capacity of the vertex to 0, and equivalent to remove the vertex from the original graph. The graph is still connected, so there is still a path in the network.

If we cut other edges, it is equivalent to remove an edge from the original graph. It is still connected, too.

Now we have minimal cut > 1, which means maximal flow = minimal cut = 2. So there is always a simple path from a to b going through c.

这个证明不走寻常路，通过最小割来证明，服了！

这样子我们就可以将每个分量看作一个点生成一棵树，询问只需要做一个LCA，修改就用一个堆维护。因为有修改操作，所以就把LCA改为树链剖分。

问题在于，一点可能在许多个分量里，那么修改时需要修改很多堆，于是，可以把每个割点的值仅仅维护在它的父亲分量（这是相对于深度优先搜索树而言），不过这样询问时要记得特殊处理LCA的值，就是说它们的LCA有一个割点的信息在它们LCA的父亲上。构图类似下面的。

注：右边的每个点都是一个分量，并且里面的信息用堆维护。这里的连线是对应的点。点的颜色表示，左边某色的所有点的信息储存在右边相同颜色的点上。

也许你已经注意到了，有一个特殊地方，如果\(a\)和\(b\)相连，那么这里可以就把它们当作一个分量。并且为了写程序方便，故意在根结点的顶部多加了一个点。

代码

有两个很坑的地方（对于我来说）：

不要用set而是multiset
dfs子结点\(u\)后，不要漏了这一句（太久没写tarjan了）：low[v] = min(low[v], low[u])。

5.4k（已经过滤掉了0.8k的调试信息）

#include <cstdio>

#include <iostream>

#include <algorithm>

#include <cstring>

#include <stack>

#include <set>

using namespace std;

template <class t>

void tension(t &a, const t &b) {

	if (b < a) {

		a = b;

	}

}

template <class t>

void relax(t &a, const t &b) {

	if (b > a) {

		a = b;

	}

}

const int INF = 0x3f3f3f3f;

const int MAXN = (int) 1e5 + 3;

const int MAXM = (int) 1e5 + 3;

const int MAXSIZE = 1 << 19;

int n, m, Q, A[MAXN];

struct Edge {

	int to;

	Edge *next;

};

struct BCC {

	multiset<int> s;

	void insert(int);

	int maxval;

	BCC() {

		maxval = INF;

	}

	void change(int a, int b) {

		s.erase(s.find(a));

		s.insert(b);

		maxval = *s.begin();

	}

};

int cntBcc;

BCC bcc[MAXN * 2];

int idxNew[MAXN];

void BCC::insert(int x) {

	s.insert(A[x]);

	maxval = *s.begin();

}

namespace zkwSegmentTree {

	int depth;

	int A[MAXSIZE + 1];

	void init(int size) {

		while ((1 << depth) - 2 < size) {

			depth ++;

		}

	}

	void initModify(int x, int v) {

		A[(1 << depth) + x] = v;

	}

	void upgrade() {

		for (int i = (1 << depth) - 1; i; i --)

			A[i] = min(A[i << 1], A[i << 1 ^ 1]);

	}

	int query(int a, int b) {

		a = (1 << depth) + a - 1;

		b = (1 << depth) + b + 1;

		int ans = INF;

		for (; a ^ b ^ 1; a >>= 1, b >>= 1) {

			if (~a & 1) tension(ans, A[a ^ 1]);

			if ( b & 1) tension(ans, A[b ^ 1]);

		}

		return ans;

	}

	void modify(int a, int v)

	{

		a = (1 << depth) + a;

		A[a] = v;

		for (a >>= 1; a; a >>= 1)

			A[a] = min(A[a << 1], A[a << 1 ^ 1]);

	}

}

namespace newGraph {

	const int MAXNODE = MAXN * 2;

	int root;

	Edge *info[MAXNODE], mem[MAXNODE], *cur_mem = mem;

	int fa[MAXNODE];

	void insert(int f, int s) {

		cur_mem->to = s;

		cur_mem->next = info[f];

		info[f] = cur_mem ++;

	}

	int cntPath;

	int top[MAXNODE], heavySon[MAXNODE];

	int dep[MAXNODE], size[MAXNODE], belong[MAXNODE];

	int idxMap[MAXNODE];

	int cutVertex[MAXNODE];

	void cutLightHeavy() {

		static int que[MAXNODE];

		int low = 0, high = 0;

		que[high ++] = root;

		fa[root] = -1;

		while (low < high) {

			int v = que[low ++];

			for (Edge *pt = info[v]; pt; pt = pt->next) {

				int u = pt->to;

				que[high ++] = u;

				dep[u] = dep[v] + 1;

				fa[u] = v;

			}

		}

		for (int i = high - 1; i >= 0; i --) {

			int v = que[i];

			size[v] = 1;

			heavySon[v] = -1;

			for (Edge *pt = info[v]; pt; pt = pt->next) {

				int u = pt->to;

				size[v] += size[u];

				if (heavySon[v] == -1 || size[u] > size[heavySon[v]]) {

					heavySon[v] = u;

				}

			}

		}

		zkwSegmentTree::init(cntBcc);

		int cntIdx = 1;

		for (int i = 0; i < high; i ++) {

			int v = que[i];

			if (idxMap[v] == 0) {

				top[cntPath] = v;

				for (; v != -1; v = heavySon[v]) {

					idxMap[v] = cntIdx ++;

					zkwSegmentTree::initModify(idxMap[v], bcc[v].maxval);

					belong[v] = cntPath;

				}

				cntPath ++;

			}

		}

		zkwSegmentTree::upgrade();

	}

	int query(int a, int b) {

		int ret = INF;

		a = idxNew[a], b = idxNew[b];

		while (belong[a] != belong[b]) {

			if (dep[top[belong[a]]] < dep[top[belong[b]]]) {

				swap(a, b);

			}

			tension(ret, zkwSegmentTree::query(idxMap[top[belong[a]]], idxMap[a]));

			a = fa[top[belong[a]]];

		}

		if (dep[a] < dep[b]) swap(a, b);

		tension(ret, zkwSegmentTree::query(idxMap[b], idxMap[a]));

		tension(ret, A[cutVertex[b]]);

		return ret;

	}

}

namespace srcGraph {

	Edge *info[MAXN], mem[MAXM * 2], *cur_mem = mem;

	void insert2(int a, int b) {

		cur_mem->to = b;

		cur_mem->next = info[a];

		info[a] = cur_mem ++;

		cur_mem->to = a;

		cur_mem->next = info[b];

		info[b] = cur_mem ++;

	}

	void init() {

		for (int i = 0; i < m; i ++) {

			int a, b;

			scanf("%d%d\n", &a, &b);

			insert2(a, b);

		}

	}

	int dfn[MAXN], low[MAXN], bccFa[MAXN];

	void make() {

		stack< pair<int, Edge*> > stk;

		stk.push(make_pair(1, (Edge*) NULL) );

		stack<int> contain;

		memset(dfn, -1, sizeof(dfn));

		memset(low, -1, sizeof(low));

		memset(bccFa, -1, sizeof(bccFa));

		int cntDfn = 0;

		while (! stk.empty()) {

			int v = stk.top().first;

			Edge *&pt = stk.top().second;

			if (! pt) {

				dfn[v] = low[v] = cntDfn ++;

				pt = info[v];

				contain.push(v);

			}

			else {

				int u = pt->to;

				tension(low[v], low[u]);

				if (low[u] == dfn[v]) {

					int newBcc = cntBcc ++;

					while (true) {

						int t = contain.top();

						if (bccFa[t]) {

							newGraph::insert(newBcc, bccFa[t]);

						}

						bcc[newBcc].insert(t);

						if (bccFa[t] == -1) idxNew[t] = newBcc;

						contain.pop();

						if (t == u) break;

					}

					if (bccFa[v] == -1) {

						idxNew[v] = cntBcc;

						bccFa[v] = cntBcc ++;

						newGraph::cutVertex[bccFa[v]] = v;

					}

					newGraph::cutVertex[newBcc] = v;

					newGraph::insert(bccFa[v], newBcc);

				}

			}

			for (; pt; pt = pt->next) {

				int u = pt->to;

				if (dfn[u] != -1) tension(low[v], dfn[u]);

				else {

					stk.push(make_pair(u, (Edge*) NULL));

					break;

				}

			}

			if (! pt) stk.pop();

		}

		newGraph::root = bccFa[1];

		idxNew[1] = bccFa[1];

	}

}

int main() {

	scanf("%d%d%d\n", &n, &m, &Q);

	for (int i = 1; i <= n; i ++) {

		scanf("%d\n", A + i);

	}

	srcGraph::init();

	srcGraph::make();

	newGraph::cutLightHeavy();

	for (int i = 0; i < Q; i ++) {

		char opt;

		int a, b;

		scanf("%c%d%d\n", &opt, &a, &b);

		if (opt == 'A') {

			int ans = a == b ? A[a] : newGraph::query(a, b);

			printf("%d\n", ans);

		}

		else {

			int t = idxNew[a];

			if (t == newGraph::root) {

				A[a] = b;

				continue;

			}

			if (srcGraph::bccFa[a] != -1) {

				t = newGraph::fa[t];

			}

			bcc[t].change(A[a], b);

			A[a] = b;

			zkwSegmentTree::modify(newGraph::idxMap[t], bcc[t].maxval);

		}

	}

	return 0;

}

巴特西

codeforces 487E Tourists

题目

算法

代码

最新文章

热门文章