[CF Round #278] Tourists

给定一个n个点m条边的无向图，求图上的两点的所有的简单路径之间的最小边。

蓝链

$ n,m,q \leq 100000, w_i \leq 10 ^7$
Solution

考虑建立用缩点双来建立广义圆方树，然后方点的值是当前点双内最小的点，这样就直接维护树上的最小值就可以了。但如果更新的是根节点。那么他的每个方儿子都会被更新。所以特别处理一下根节点即可。记方点权值为除根节点外的点。特别处理一下即可。
Code

#include<bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for(int i = (a), i##_end_ = (b); i <= i##_end_; ++i)

#define drep(i, a, b) for(int i = (a), i##_end_ = (b); i >= i##_end_; --i)

#define clar(a, b) memset((a), (b), sizeof(a))

#define debug(...) fprintf(stderr, __VA_ARGS__)

#define Debug(s) debug("The massage in line %d, Function %s: %s\n", __LINE__, __FUNCTION__, s)

typedef long long LL;

typedef long double LD;

const int BUF_SIZE = (int)1e6 + 10;

struct fastIO {

    char buf[BUF_SIZE], buf1[BUF_SIZE];

    int cur, cur1;

    FILE *in, *out;

    fastIO() {

        cur = BUF_SIZE, in = stdin, out = stdout;

		cur1 = 0;

    }

    inline char getchar() {

        if(cur == BUF_SIZE) fread(buf, BUF_SIZE, 1, in), cur = 0;

        return *(buf + (cur++));

    }

    inline void putchar(char ch) {

        *(buf1 + (cur1++)) = ch;

        if (cur1 == BUF_SIZE) fwrite(buf1, BUF_SIZE, 1, out), cur1 = 0;

    }

    inline int flush() {

        if (cur1 > 0) fwrite(buf1, cur1, 1, out);

        return cur1 = 0;

    }

}IO;

#define getchar IO.getchar

#define putchar IO.putchar

int read() {

	char ch = getchar();

	int x = 0, flag = 1;

	for(;!isdigit(ch); ch = getchar()) if(ch == '-') flag *= -1;

	for(;isdigit(ch); ch = getchar()) x = x * 10 + ch - 48;

	return x * flag;

}

void write(int x) {

	if(x < 0) putchar('-'), x = -x;

	if(x >= 10) write(x / 10);

	putchar(x % 10 + 48);

}

void putString(char s[], char EndChar = '\n') {

	rep(i, 0, strlen(s) - 1) putchar(*(s + i));

	if(~EndChar) putchar(EndChar);

}

#define Maxn 300009

struct edge {

	int to, nxt;

}g[Maxn << 1], g1[Maxn << 1];

int n, m, head[Maxn], e, e1, head1[Maxn];

multiset<int> S[Maxn];

int val[Maxn];

int dfn[Maxn], low[Maxn], _clk, cnt_Squ;

stack <int> s;

int top[Maxn], dep[Maxn], size[Maxn], son[Maxn];

int fa[Maxn], efn[Maxn], _index;

namespace INIT {

	void add(int u, int v) {

		g[++e] = (edge){v, head[u]}, head[u] = e;

	}

	void add1(int u, int v) {

		g1[++e1] = (edge){v, head1[u]}, head1[u] = e1;

	}

	void tarjan(int u, int fa) {

		dfn[u] = low[u] = ++_clk;

		s.push(u);

		for(int i = head[u]; ~i; i = g[i].nxt) {

			int v = g[i].to;

			if(v != fa)

				if(!dfn[v]) {

					tarjan(v, u);

					low[u] = min(low[u], low[v]);

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

						add1(n + (++cnt_Squ), u), add1(u, n + cnt_Squ);

						int a;

						do {

							a = s.top(); s.pop();

							add1(n + cnt_Squ, a), add1(a, n + cnt_Squ);

						}while(a != v);

					}

				}else low[u] = min(low[u], dfn[v]);

		}

	}

	void dfs_init(int u, int f) {

		size[u] = 1;

		dep[u] = dep[f] + 1, fa[u] = f;

		for(int i = head1[u]; ~i; i = g1[i].nxt) {

			int v = g1[i].to;

			if(v != f) {

				dfs_init(v, u);

				size[u] += size[v];

				if(son[u] == -1 || size[son[u]] < size[v]) v = son[u];

			}

		}

	}

	void dfs_link(int u, int _top) {

		top[u] = _top;

		dfn[u] = ++_index, efn[_index] = u;

		if(~son[u]) dfs_link(son[u], _top);

		for(int i = head1[u]; ~i; i = g1[i].nxt) {

			int v = g1[i].to;

			if(v ^ fa[u] && v ^ son[u]) dfs_link(v, v);

		}

	}

	void Main() {

		clar(head, -1);

		clar(head1, -1);

		n = read(), m = read();

		rep(i, 1, n) val[i] = read();

		rep(i, 1, m) {

			int u = read(), v = read();

			add(u, v), add(v, u);

		}

		tarjan(1, 0);

		clar(dfn, 0), _clk = 0;

		clar(son, -1);

		dfs_init(1, 0);

		dfs_link(1, 1);

		rep(i, 2, n) S[fa[i] - n].insert(val[i]);

	}

}

namespace SGMT_tree {

	int tree[Maxn << 2];

#define lc(x) ((x) << 1)

#define rc(x) ((x) << 1 | 1)

#define ls rt << 1, l, mid

#define rs rt << 1 | 1, mid + 1, r

	void pushup(int root) {

		tree[root] = min(tree[lc(root)], tree[rc(root)]);

	}

	void build(int rt, int l, int r) {

		if(l == r) {

			tree[rt] = (efn[l] <= n) ? (val[efn[l]]) : (*S[efn[l] - n].begin());

			return ;

		}

		int mid = (l + r) >> 1;

		build(ls), build(rs);

		pushup(rt);

	}

	void modify(int rt, int l, int r, int pos) {

		if(l == r) {

			tree[rt] = (efn[l] <= n) ? (val[efn[l]]) : (*S[efn[l] - n].begin());

			return;

		}

		int mid = (l + r) >> 1;

		(pos <= mid) ? modify(ls, pos) : modify(rs, pos);

		pushup(rt);

	}

	int query(int rt, int l, int r, int x, int y) {

		if(x <= l && r <= y) return tree[rt];

		int mid = (l + r) >> 1;

		if(mid >= y) return query(ls, x, y);

		if(mid + 1 <= x) return query(rs, x, y);

		return min(query(ls, x, y), query(rs, x, y));

	}

#undef lc

#undef rc

#undef ls

#undef rs

}

namespace SOLVE {

	void Main() {

		int amt = cnt_Squ + n;

		SGMT_tree :: build(1, 1, amt);

		rep(i, 1, read()) {

			char s = getchar();

			int x = read(), y = read();

			if(s == 'C') {

				if(x > 1) {

					S[fa[x] - n].erase(S[fa[x] - n].lower_bound(val[x]));

					S[fa[x] - n].insert(y);

					SGMT_tree :: modify(1, 1, amt, dfn[fa[x]]);

				}

				val[x] = y;

				SGMT_tree :: modify(1, 1, amt, dfn[x]);

			}

			if(s == 'Q') {

				int Tmp = x, res = INT_MAX;

				while(top[x] != top[y]) {

					if(dep[top[x]] < dep[top[y]]) swap(x, y);

					res = min(res, SGMT_tree :: query(1, 1, amt, dfn[top[x]], dfn[x]));

					x = fa[top[x]];

				}

				if(dep[x] < dep[y]) swap(x, y);

				res = min(res, SGMT_tree :: query(1, 1, amt, dfn[x], dfn[y]));

				if(x > n) res = min(res, val[fa[x]]);

				assert(res != INT_MAX);

				write(val[Tmp] - res), putchar('\n');

			}

		}

	}

}

int main() {

	INIT :: Main();

	SOLVE :: Main();

#ifdef Qrsikno

	debug("\nRunning time: %.3lf(s)\n", clock() * 1.0 / CLOCKS_PER_SEC);

#endif

	return IO.flush();

}
巴特西

[CF Round #278] Tourists

Solution

Code

最新文章

热门文章
