并查集
struct dsu {
private:
// number of nodes
int n;
// root node: -1 * component size
// otherwise: parent
std::vector<int> pa;
public:
dsu(int n_ = 0) : n(n_), pa(n_, -1) {}
// find node x's parent
int find(int x) {
return pa[x] < 0 ? x : pa[x] = find(pa[x]);
}
// merge node x and node y
// if x and y had already in the same component, return false, otherwise return true
// Implement (union by size) + (path compression)
bool unite(int x, int y) {
int xr = find(x), yr = find(y);
if (xr != yr) {
if (-pa[xr] < -pa[yr]) std::swap(xr, yr);
pa[xr] += pa[yr];
pa[yr] = xr; // y -> x
return true;
}
return false;
}
// size of the connected component that contains the vertex x
int size(int x) {
return -pa[find(x)];
}
};
最短路
namespace Dijkstra {
#define ll long long
static constexpr ll INF = 1e18;
int n, m; // 点数 边数
struct edge {
int to; // 点
ll val; // 边权
edge(int to_ = 0, ll val_ = 0) :to(to_), val(val_) {}
bool operator < (const edge& k) const { return val > k.val; }
};
vector<vector<edge>> g;
void init() { // 建图操作需要根据题意修改
cin >> n >> m;
g.resize(n);
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
--u, --v;
g[u].push_back(edge(v, w));
}
}
ll dijkstra(int s, int t) { // 最短路
vector<ll> dis(n, INF);
vector<bool> vis(n, false);
dis[s] = 0;
priority_queue<edge> pq;
pq.push(edge(s, 0));
while (!pq.empty()) {
auto top = pq.top();
pq.pop();
if (!vis[top.to]) {
vis[top.to] = true;
for (auto nxt : g[top.to]) {
if (!vis[nxt.to] && dis[nxt.to] > nxt.val + dis[top.to]) {
dis[nxt.to] = nxt.val + dis[top.to];
pq.push(edge(nxt.to, dis[nxt.to]));
}
}
}
}
return dis[t];
}
#undef ll
}
最小生成树
struct edge {
int u, v;
int w;
edge(int u_ = 0, int v_ = 0, int w_ = 0) :u(u_), v(v_), w(w_) {}
bool operator< (const edge& k) const {
return w < k.w;
}
};
long long kruskal() { // kruskal算法 需要并查集
int n, m;
cin >> n >> m;
dsu u(n);
vector<edge> g(m);
for (auto& i : g) {
cin >> i.u >> i.v >> i.w;
--i.u, --i.v;
}
sort(g.begin(), g.end());
long long res = 0;
for (auto i : g) {
if (u.unite(i.u, i.v)) {
res += i.w;
}
}
return res;
}
最小树形图
namespace ZL {
// a 尽量开大, 之后的边都塞在这个里面
const int N = 100010, M = 100010, inf = 1e9;
struct edge {
int u, v, w, use, id;
edge(int u_ = 0, int v_ = 0, int w_ = 0, int use_ = 0, int id_ = 0)
: u(u_), v(v_), w(w_), use(use_), id(id_) {}
}b[M], a[2000100];
int n, m, ans, pre[N], id[N], vis[N], root, In[N], h[N], len, way[M];
// 从root 出发能到达每一个点的最小树形图
// 先调用init 然后把边add 进去, 需要方案就getway, way[i] 为1 表示使用
// 最小值保存在ans
void init(int _n, int _root) { // 点数 根节点
n = _n; m = 0; b[0].w = inf; root = _root;
}
void add(int u, int v, int w) {
m++;
b[m] = edge(u, v, w, 0, m);
a[m] = b[m];
}
int work() {
len = m;
for (;;) {
for (int i = 1; i <= n; i++) { pre[i] = 0; In[i] = inf; id[i] = 0; vis[i] = 0; h[i] = 0; }
for (int i = 1; i <= m; i++) {
if (b[i].u != b[i].v && b[i].w < In[b[i].v]) {
pre[b[i].v] = b[i].u; In[b[i].v] = b[i].w; h[b[i].v] = b[i].id;
}
}
for (int i = 1; i <= n; i++) if (pre[i] == 0 && i != root) return 0;
int cnt = 0; In[root] = 0;
for (int i = 1; i <= n; i++) {
if (i != root) a[h[i]].use++; int now = i; ans += In[i];
while (vis[now] == 0 && now != root) { vis[now] = i; now = pre[now]; }
if (now != root && vis[now] == i) {
cnt++; int kk = now;
while (1) {
id[now] = cnt; now = pre[now];
if (now == kk) break;
}
}
}
if (cnt == 0) return 1;
for (int i = 1; i <= n; i++) if (id[i] == 0) id[i] = ++cnt;
// 缩环, 每一条接入的边都会茶包原来接入的那条边, 所以要调整边权
// 新加的边是u, 茶包的边是v
for (int i = 1; i <= m; i++) {
int k1 = In[b[i].v], k2 = b[i].v;
b[i].u = id[b[i].u];
b[i].v = id[b[i].v];
if (b[i].u != b[i].v) {
b[i].w -= k1; a[++len].u = b[i].id; a[len].v = h[k2]; b[i].id = len;
}
}
n = cnt; root = id[root];
}
return 1;
}
void getway() {
for (int i = 1; i <= m; i++) way[i] = 0;
for (int i = len; i > m; i--) { a[a[i].u].use += a[i].use; a[a[i].v].use -= a[i].use; }
for (int i = 1; i <= m; i++) way[i] = a[i].use;
}
}
constexpr int SIZE = 200010;
constexpr int DEPTH = 21; // 最大深度 2^DEPTH - 1
int pa[SIZE][DEPTH], dep[SIZE];
vector<int> g[SIZE]; //邻接表
void dfs(int rt, int fin) { //预处理深度和祖先
pa[rt][0] = fin;
dep[rt] = dep[pa[rt][0]] + 1; //深度
for (int i = 1; i < DEPTH; ++i) { // rt 的 2^i 祖先等价于 rt 的 2^(i-1) 祖先 的 2^(i-1) 祖先
pa[rt][i] = pa[pa[rt][i - 1]][i - 1];
}
int sz = g[rt].size();
for (int i = 0; i < sz; ++i) {
if (g[rt][i] == fin) continue;
dfs(g[rt][i], rt);
}
}
int LCA(int x, int y) {
if (dep[x] > dep[y]) swap(x, y);
int dif = dep[y] - dep[x];
for (int j = 0; dif; ++j, dif >>= 1) {
if (dif & 1) {
y = pa[y][j]; //先跳到同一高度
}
}
if (y == x) return x;
for (int j = DEPTH - 1; j >= 0 && y != x; --j) { //从底往上跳
if (pa[x][j] != pa[y][j]) { //如果当前祖先不相等 我们就需要更新
x = pa[x][j];
y = pa[y][j];
}
}
return pa[x][0];
}
namespace KM {
typedef long long ll;
const int maxn = 510;
const int inf = 1e9;
int vx[maxn], vy[maxn], lx[maxn], ly[maxn], slack[maxn];
int w[maxn][maxn]; // 以上为权值类型
int pre[maxn], left[maxn], right[maxn], NL, NR, N;
void match(int& u) {
for (; u; std::swap(u, right[pre[u]]))
left[u] = pre[u];
}
void bfs(int u) {
static int q[maxn], front, rear;
front = 0; vx[q[rear = 1] = u] = true;
while (true) {
while (front < rear) {
int u = q[++front];
for (int v = 1; v <= N; ++v) {
int tmp;
if (vy[v] || (tmp = lx[u] + ly[v] - w[u][v]) > slack[v])
continue;
pre[v] = u;
if (!tmp) {
if (!left[v]) return match(v);
vy[v] = vx[q[++rear] = left[v]] = true;
} else slack[v] = tmp;
}
}
int a = inf;
for (int i = 1; i <= N; ++i)
if (!vy[i] && a > slack[i]) a = slack[u = i];
for (int i = 1; i <= N; ++i) {
if (vx[i]) lx[i] -= a;
if (vy[i]) ly[i] += a;
else slack[i] -= a;
}
if (!left[u]) return match(u);
vy[u] = vx[q[++rear] = left[u]] = true;
}
}
void exec() {
for (int i = 1; i <= N; ++i) {
for (int j = 1; j <= N; ++j) {
slack[j] = inf;
vx[j] = vy[j] = false;
}
bfs(i);
}
}
ll work(int nl, int nr) { // NL , NR 为左右点数, 返回最大权匹配的权值和
NL = nl; NR = nr;
N = std::max(NL, NR);
for (int u = 1; u <= N; ++u)
for (int v = 1; v <= N; ++v)
lx[u] = std::max(lx[u], w[u][v]);
exec();
ll ans = 0;
for (int i = 1; i <= N; ++i)
ans += lx[i] + ly[i];
return ans;
}
void output() { // 输出左边点与右边哪个点匹配, 没有匹配输出0
for (int i = 1; i <= NL; ++i)
printf("%d ", (w[i][right[i]] ? right[i] : 0));
printf("\n");
}
}
/*
* 2-sat
* n 表示限制个数, i 为取(真), i+n 为不取(假)
* 先初始化再建图
* 建图时 若输入两组或关系 ((x = a) || (y = b))则有:
if (a && b) {
Twosat::add(x + n, y), Twosat::add(y + n, x);
} else if (!a && b) {
Twosat::add(x, y), Twosat::add(y + n, x + n);
} else if (a && !b) {
Twosat::add(x + n, y + n), Twosat::add(y, x);
} else {
Twosat::add(x, y + n), Twosat::add(y, x + n);
}
* 表示若条件1/2不成立 则条件2/1必定成立
* 构造结果保存在 ans 数组 若ans[i] = 0则取i 否则取i+n
* */
namespace Twosat {
const int M = 4000010, N = 1000010;
struct edge {
int next, point;
edge(int n_ = 0, int p_ = 0) :next(n_), point(p_) {}
} e[M];
int n, len, now, sign, head, sign2;
int p[N << 1], dfs[N << 1], low[N << 1], where[N << 1];
int s[N << 1], in[N << 1], ans[N], out[N << 1];
void add(int k1, int k2) {
e[++len] = edge(p[k1], k2);
p[k1] = len;
}
void init(int _n) {
n = _n;
for (int i = 0; i <= n * 2 + 1; i++) {
p[i] = where[i] = dfs[i] = low[i] = s[i] = in[i] = out[i] = 0;
}
len = now = sign = head = sign2 = 0;
}
void tarjan(int k1) {
s[++head] = k1; in[k1] = 1; dfs[k1] = ++sign; low[k1] = sign;
for (int i = p[k1]; i; i = e[i].next) {
int j = e[i].point;
if (dfs[j] == 0) {
tarjan(j);
low[k1] = min(low[k1], low[j]);
} else if (in[j]) {
low[k1] = min(low[k1], dfs[j]);
}
}
if (dfs[k1] == low[k1]) {
now++;
while (1) {
where[s[head]] = now;
in[s[head]] = 0;
out[s[head]] = ++sign2;
head--;
if (s[head + 1] == k1) {
break;
}
}
}
}
int solve() { // ans[i] = 0 表示取i, 否则表示取i+n
for (int i = 1; i <= n * 2; i++) {
if (dfs[i] == 0) {
tarjan(i);
}
}
for (int i = 1; i <= n; i++) {
if (where[i] == where[i + n]) {
return 0;
}
}
for (int i = 1; i <= n; i++) {
if (out[i] < out[i + n]) {
ans[i] = 0;
} else {
ans[i] = 1;
}
}
return 1;
}
}
/*
* 最大团 Bron-Kerbosch algorithm
* 最劣复杂度 O(3^(n/3))
* 采用位运算形式实现
* */
namespace Max_clique {
#define ll long long
#define TWOL(x) (1ll<<(x))
const int N = 60;
int n, m; // 点数 边数
int r = 0; // 最大团大小
ll G[N]; // 以二进制形式存图
ll clique = 0; // 最大团 以二进制形式存储
void BronK(int S, ll P, ll X, ll R) { // 调用时参数这样设置: 0, TWOL(n)-1, 0, 0
if (P == 0 && X == 0) {
if (r < S) {
r = S;
clique = R;
}
}
if (P == 0) return;
int u = __builtin_ctzll(P | X);
ll c = P & ~G[u];
while (c) {
int v = __builtin_ctzll(c);
ll pv = TWOL(v);
BronK(S + 1, P & G[v], X & G[v], R | pv);
P ^= pv; X |= pv; c ^= pv;
}
}
void init() {
cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
--u, --v;
G[u] |= TWOL(v);
G[v] |= TWOL(u);
}
BronK(0, TWOL(n)-1, 0, 0);
cout << r << ' ' << clique << '\n';
}
}