NOIP2013 Day1 T3(最大生成树+树链剖分/最大生成树+倍增)

一看题目就想树剖,但是这里是图,怎么办?用最小生成树。我们只需要用最大的那几条边来连接这些点成为一棵树,其他的边是没有用的。求完最大树以后,再树链剖分或者倍增思想,这里没有做倍增只做了树剖,注意树剖的时候边权转点权,边权放到深度深的那个点上,然后处理每一个路径$(u,v)$,对于$LCA(u,v)$是不用加的!刚开始正解和暴力全部写挂这里直接10分。改了之后发现暴力还比正解快500ms。。下面给出树剖代码和暴力代码,以及数据生成器,有用的可以拿去。

树剖:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
using namespace std;
const int MAXN = 10000 + 5, MAXM = 50000 + 5, INF = 1000000000;
struct data1 {
int u, v, wi;
bool operator < (const data1 &x) const {
return wi > x.wi;
}
}e1[MAXM];//原图
struct data2 {
int v, wi;
}e2[MAXM*2];//最大树
int n, m, Q, en, f[MAXN];//最大树边数,并查集
int dwi[MAXN], dep[MAXN], fa[MAXN], top[MAXN], p[MAXN], siz[MAXN], son[MAXN], pre;//树剖
int minv[MAXN*4];//线段树
vector<int> G[MAXN];//最大树
#define lc (o<<1)
#define rc (o<<1|1)
#define M ((l+r)>>1)
void pushup(int o) {//线段树
minv[o] = min(minv[lc], minv[rc]);
}
void update(int o, int l, int r, int p, int v) {//线段树
if (l==r) {
minv[o] = v;
return ;
}
if (p<=M) update(lc, l, M, p, v);
else if (M<p) update(rc, M+1, r, p, v);
pushup(o);
}
int query(int o, int l, int r, int x, int y) {//线段树
int ret = INF;
if (x<=l&&r<=y) {
return minv[o];
}
if (x<=M) ret = min(ret, query(lc, l, M, x, y));
if (M<y) ret = min(ret, query(rc, M+1, r, x, y));
return ret;
}
int find(int x) {return x==f[x] ? x : f[x] = find(f[x]);}//并查集find
void dfs1(int u, int pa) {//树剖
dep[u] = dep[pa] + 1, fa[u] = pa, siz[u] = 1;
for (int i=0;i<G[u].size();i++) {
data2 d2 = e2[G[u][i]];
int v = d2.v, wi = d2.wi;
if (v!=pa) {
dfs1(v, u);
dwi[v] = wi;
siz[u] += siz[v];
if (son[u]==-1||siz[v]>siz[son[u]]) son[u] = v;
}
}
}
void dfs2(int u, int cha) {//树剖
top[u] = cha, p[u] = ++pre;
if (son[u]!=-1) {
dfs2(son[u], cha);
for (int i=0;i<G[u].size();i++) {
data2 d2 = e2[G[u][i]];
int v = d2.v;
if (v!=fa[u]&&v!=son[u]) {
dfs2(v, v);
}
}
}
}
int findMax(int u, int v) {//树剖
int ret = INF, f1 = top[u], f2 = top[v];
while (f1!=f2) {
if (dep[f1]<dep[f2]) swap(f1, f2), swap(u, v);
ret = min(ret, query(1,1,n,p[f1],p[u]));
u = fa[f1];
f1 = top[u];
}
if (dep[u]<dep[v]) swap(u, v);
return min(ret, query(1,1,n,p[v]+1,p[u]));
}
void MST() {//Kruskal
sort(e1+1, e1+1+m);
for (int i=1;i<=m;i++) {
int a1 = find(e1[i].u), b1 = find(e1[i].v);
if (a1==b1) continue;
f[a1] = b1;
en++, e2[en].v = e1[i].v, e2[en].wi = e1[i].wi, G[e1[i].u].push_back(en);
en++, e2[en].v = e1[i].u, e2[en].wi = e1[i].wi, G[e1[i].v].push_back(en);
}
}
void clean() {
pre = en = 0;
for (int i=0;i<=n;i++) {
dep[i] = fa[i] = top[i] = p[i] = siz[i] = 0;
son[i] = -1;
f[i] = i;
G[i].clear();
}
for (int i=0;i<=4*n;i++) minv[i] = INF;
}
void init() {
clean();
for (int i=1;i<=m;i++) {
scanf("%d%d%d", &e1[i].u, &e1[i].v, &e1[i].wi);
}
}
void solve() {
MST();
for (int i=1;i<=n;i++) if (!dep[i]) dfs1(i, 0);
for (int i=1;i<=n;i++) if (!p[i]) dfs2(i, i);
for (int i=1;i<=n;i++) if (fa[i]!=0) update(1,1,n,p[i],dwi[i]);
scanf("%d", &Q);
for (int i=1;i<=Q;i++) {
int u, v;
scanf("%d%d", &u, &v);
int a1 = find(u), b1 = find(v);
if (a1!=b1) {printf("-1\n"); continue;}
printf("%d\n", findMax(u, v));
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);freopen("1.out", "w", stdout);
#endif
while (scanf("%d%d", &n, &m)==2) init(), solve();
return 0;
}

暴力:(跑得比树剖还快)

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
using namespace std;
const int MAXN = 10000 + 5, MAXM = 50000 + 5, INF = 1000000000;
struct data1 {
int u, v, wi;
bool operator < (const data1 &x) const {
return wi > x.wi;
}
}e1[MAXM];//原图
struct data2 {
int v, wi;
}e2[MAXM*2];//最大树
vector<int> G[MAXN];//最大树
int dwi[MAXN], en, n, m, dep[MAXN], fa[MAXN], f[MAXN];
void dfs(int u, int pa) {
dep[u] = dep[pa] + 1, fa[u] = pa;
for (int i=0;i<G[u].size();i++) {
data2 d2 = e2[G[u][i]];
int v = d2.v;
if (v!=fa[u]) {
dfs(v, u);
dwi[v] = d2.wi;
}
}
}
int find(int x) {return x==f[x] ? x : f[x] = find(f[x]);}//并查集find
void MST() {//Kruskal
sort(e1+1, e1+1+m);
for (int i=1;i<=m;i++) {
int a1 = find(e1[i].u), b1 = find(e1[i].v);
if (a1==b1) continue;
f[a1] = b1;
en++, e2[en].v = e1[i].v, e2[en].wi = e1[i].wi, G[e1[i].u].push_back(en);
en++, e2[en].v = e1[i].u, e2[en].wi = e1[i].wi, G[e1[i].v].push_back(en);
}
}
int findMax(int u, int v) {
int ret = INF;
if (dep[u]<dep[v]) swap(u, v);
while (dep[u]>dep[v]) ret = min(ret, dwi[u]), u = fa[u];
if (u==v) return ret;
while (u!=v) ret = min(ret, min(dwi[v], dwi[u])), u = fa[u], v = fa[v];
return ret;
}
void clean() {
en = 0;
for (int i=0;i<=n;i++) {
dep[i] = fa[i] = 0;
f[i] = i;
G[i].clear();
}
}
void init() {
clean();
for (int i=1;i<=m;i++) {
scanf("%d%d%d", &e1[i].u, &e1[i].v, &e1[i].wi);
}
}
void solve() {
MST();
for (int i=1;i<=n;i++) if (!dep[i]) dfs(i, 0);
int Q;
scanf("%d", &Q);
for (int i=1;i<=Q;i++) {
int u, v;
scanf("%d%d", &u ,&v);
int a1 = find(u), b1 = find(v);
if (a1!=b1) {printf("-1\n"); continue;}
printf("%d\n", findMax(u, v));
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);freopen("2.out", "w", stdout);
#endif
while (scanf("%d%d", &n, &m)==2) init(), solve();
return 0;
}

数据生成器:

#include<cstdio>
#include<algorithm>
#include<windows.h>
#include<winbase.h>
#include<set>
using namespace std;
int n = 3, m = 5, w = 5, q = 3;
int main() {
freopen("1.in", "w", stdout);
srand(GetTickCount());
printf("%d %d\n", n, m);
for (int i=1;i<=m;i++) {
int a = rand()%n+1;
int b = rand()%n+1;
while (a==b) b = rand()%n+1;
printf("%d %d %d\n", a, b, rand()%w);
}
printf("%d\n", q);
for (int i=1;i<=q;i++) {
int a = rand()%n+1;
int b = rand()%n+1;
while (a==b) b = rand()%n+1;
printf("%d %d\n", a, b);
}
return 0;
}

------ 本文结束 ------