Codeforces 892D
题意:给出一个$n$个点$m$条边的无向联通图,有$q$个询问每个询问询问一个边集$E_i$,回答这些边能否在同一个最小生成树中
本题又加强我对最小生成树定理的理解……
首先同一个图最小生成树所有相同边权数量都是一样的,并且在 Kruskal 加边时不同边互相之间独立。也就是说我们可以将每个边权分开来加,并且每种边权都可以被一条不产生环的。关于更多最小生成树的定理,请看Bzoj 1016
其实这题和Bzoj 1016有类似的地方。
我们将询问离线。按照边权大小从小到大加边。枚举当前边权大小为$w$, 如果在某个询问中有$w$大的边,那么就将这些$w$大的边权加到并查集里看会不会产生环,如果产生环则无解,当然这些边要撤销,用能撤销的并查集。然后每次循环完以后,将当前边权的所有边加入并查集不撤销,继续做。
1、最小生成树的定理要掌握:1切割性质、2回路性质、3相同边权数量相等,4不同边权加入时互相独立,5不产生环的同权值边可以替换边
2、调试大代码要用分块调试和输出调试,并且要运用解释数组方法来检查
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<stack>
#include<set>
#include<queue>
#include<climits>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
const int MAXN = 500000 + 5;
struct edge {
int u, v, w;
bool operator < (const edge &b) const {return w < b.w;}
} ed[MAXN], ed2[MAXN];
struct whw {int id, fr, t;}; // id:是哪个询问的。fr,t:在输入边排序后(que)的index范围
struct ask {
int id; // 输入边编号
bool operator < (const ask &b) const {return ed[id].w < ed[b.id].w;}
};
int n, m, q, ans[MAXN], maxw = 0, f[MAXN], sz[MAXN];
vector<whw > a[MAXN]; // a[权值][index] = 询问中边权为 权值 的边(whw类型)
vector<ask > que[MAXN]; // que[输入边index][index] = 输入边排序后边编号(ask类型)
stack<pair<int, int > > s;
int find(int x) {return x == f[x] ? x : find(f[x]);} //no compress
void mg(int a, int b) {
int x = a, y = b;
if (sz[x] > sz[y]) swap(x, y);
f[x] = y, sz[y] += sz[x], s.push(mp(x, y));
}
void cc(int tms) {
while (tms-- && !s.empty()) {
pair<int, int > p = s.top(); s.pop();
int x = p.fir, y = p.sec;
f[x] = x, sz[y] -= sz[x];
}
}
void clean() {
ms(ans, 0);
}
int solve() {
cin >> n >> m;
clean();
for (int i = 1; i <= m; ++i) scanf("%d%d%d", &ed[i].u, &ed[i].v, &ed[i].w), maxw = max(maxw, ed[i].w), ed2[i] = ed[i];
sort(ed2 + 1, ed2 + 1 + m);
cin >> q;
for (int i = 1; i <= q; ++i) {
int Ki; scanf("%d", &Ki);
for (int x, j = 1; j <= Ki; ++j) scanf("%d", &x), que[i].push_back((ask){x});
sort(que[i].begin(), que[i].end());
int lst = 0;
for (int j = 1; j < (int)que[i].size(); ++j) {
int id = que[i][j].id, lid = que[i][j - 1].id;
if (ed[id].w != ed[lid].w) {
a[ed[lid].w].push_back((whw){i, lst, j - 1});
lst = j;
}
}
a[ ed[ que[i][ (int)que[i].size() - 1 ].id ].w ].push_back((whw){i, lst, (int)que[i].size() - 1});
}
for (int i = 0; i <= n; ++i) f[i] = i, sz[i] = 1;
int now = 1;
for (int i = 1; i <= maxw; ++i) {
for (int j = 0; j < (int)a[i].size(); ++j) {
int fl = 0, tms = 0;
whw &ct = a[i][j];
for (int k = ct.fr; k <= ct.t; ++k) {
edge &e = ed[que[ct.id][k].id];
int x = find(e.u), y = find(e.v);
if (x == y) {fl = 1; break;} else mg(x, y), ++tms;
}
if (fl) ans[ct.id] = 1; //no
cc(tms);
}
while (ed2[now].w == i) {
int x = find(ed2[now].u), y = find(ed2[now].v);
if (x != y) mg(x, y);
++now;
}
}
for (int i = 1; i <= q; ++i) printf("%s", ans[i] == 1 ? "NO\n" : "YES\n");
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}