0%

Barrett reduction 取模优化

计算 \(ab\bmod m(0\le a,b<m<2^{31})\)

如果 \(m\) 在编译时已知,那么编译器就会帮你完成这个优化(准确地说是下面的变种),否则你可以自己实现。

原生算法

首先,设 \(m^{-1}\) 表示浮点数形式的 \(\frac 1m\)\[ ab\bmod m=ab-\lfloor ab\cdot m^{-1}\rfloor m \] 即使预处理了 \(m^{-1}\),由于浮点数乘法比整数除法快不了多少,考虑进一步优化,取 \(\frac {m'}{2^k}\approx m^{-1}\),然后 \[ \lfloor ab\cdot m^{-1}\rfloor \approx \lfloor \frac{abm'}{2^k}\rfloor \] 计算右边就快多了,因为只有整数乘法和右移,如何合理选取 \(m'\)\(k\)

\(k=2\lceil \log_2 m\rceil,m'=\lceil \frac{2^k}m\rceil\),下面分析误差:

  • \(m'm=2^k+r(0\le r<m)\)
  • \(ab=cm+d(0\le c,d<m)\)
  • \(abm'=(cm+d)m'=cm'm+dm'=c2^k+cr+dm'\)
  • \(cr+dm'<(m-1)^2+m'm<(m-1)^2+2^k+(m-1)=2^k+m(m-1)<2^k\cdot 2\)
  • \(\lfloor \frac{abm'}{2^k}\rfloor=c\ \text{or}\ c+1\)

设真实答案为 \(ans\),那么 \(ab-\lfloor \frac{abm'}{2^k}\rfloor m=ans\ \text{or}\ ans-m\)

更一般的结论是只要 \(c \ge \max(a, b^2)\)\(\lfloor \frac{a\lfloor \frac cb\rfloor}c\rfloor=\lfloor \frac ab\rfloor\ \text{or}\ \lfloor \frac ab\rfloor+1\) 成立。

实践中可以令 \(k=64\),可以用 ~0ull / m + 1 来计算 \(m'\)

阅读全文 »

题目链接

给定一张 \(n\) 个点 \(m\) 条边的带权有向图。

\(q\) 次询问,每次给定 \(v,s,t\),问是否存在一条起点终点都为 \(v\) 的路径满足 \(t | (s+l)\),其中 \(l\) 是路径的总长。

\(n, m,q \le 2 \cdot 10^5,s<t\le 10^9\),边权均不超过 \(10^9\)

首先这条路径只能在 \(v\) 所在强连通分量的内部。

以下所有的路径长度都是在模 \(t\) 意义下的。

引理:在同一个强连通分量,如果 \(u\rightarrow v\) 存在一条长度为 \(l\) 的路径,那么 \(v\rightarrow u\) 存在一条长度为 \(-l\) 的路径。

构造:假设 \(v\rightarrow u\) 存在一条长度为 \(w\) 的路径,先走 \(v\rightarrow u\),长度为 \(w\),再走 \(t-1\)\(u\rightarrow v\rightarrow u\),长度为 \((t-1)(l+w)\),总长度 \(-w\)

在强连通分量的内部,对于一个长度为 \(w\) 的环,从环上一个点 \(u\) 出发绕若干圈再回到 \(u\),所有可能的路径长度为 \(\gcd(w,t)\) 的倍数。根据引理,\(v\rightarrow u\) 有一条长度为 \(w\) 的路径,\(u\rightarrow v\) 有一条长度为 \(-w\) 的路径,先走 \(v\rightarrow u\),再绕若干圈,最后走 \(u\rightarrow v\),就可以凑出所有长度为 \(\gcd(w,t)\) 倍数的环。

\(r\) 为根建出 DFS 树,设 \(\phi(u)\) 表示从 \(r\) 沿着树边走到 \(u\) 的路径长度,对于每条非树边 \((u,v,w)\),意味着存在一个长度为 \(\phi(u)+w-\phi(v)\) 的环。设 \(x=\gcd_{(u,v,w)}\phi(u)+w-\phi(v)\),那么所有的可能环长分别为 \(0,x,2x,3x,\cdots\)。这些环长显然能取到,也可以归纳证明对于任何 \(r\rightarrow u\) 的路径,都有长度 \(\equiv \phi(u)\pmod x\)。结论:存在合法路径当且仅当 \(x|s\)

复杂度 \(O(n+m)\)

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
#define rep(i, l, r) for(int i = (l); i <= (r); i++)
#define per(i, r, l) for(int i = (r); i >= (l); i--)
#define mem(a, b) memset(a, b, sizeof a)
#define For(i, l, r) for(int i = (l), i##e = (r); i < i##e; i++)
#define pb push_back
#define upd(a, b) (a = min(a, b))

using namespace std;

typedef long long ll;
const int N = 2e5 + 5;

int n, m, q;
vector<pair<int, int>> G[N];
int idx, dfn[N], scc[N], stk[N], tp, sid;
ll g[N], d[N], gg[N];

int dfs(int u) {
int low = dfn[u] = ++idx; stk[++tp] = u;
for(auto [v, w] : G[u]) if(!dfn[v]) d[v] = d[u] + w, upd(low, dfs(v));
else if(!scc[v]) upd(low, dfn[v]), g[u] = gcd(g[u], d[u] - d[v] + w);
if(low == dfn[u]) for(int v = (sid++, 0); v ^ u;)
v = stk[tp--], scc[v] = sid, gg[sid] = gcd(gg[sid], g[v]);
return low;
}
int main() {
cin >> n >> m;
int u, v, w;
rep(i, 1, m) scanf("%d%d%d", &u, &v, &w), G[u].emplace_back(v, w);
rep(i, 1, n) if(!dfn[i]) dfs(i);
for(cin >> q; q--; puts(v % gcd(gg[scc[u]], (ll)w) ? "NO" : "YES"))
scanf("%d%d%d", &u, &v, &w);
}
阅读全文 »

题目链接

给定 \(n,k\),求 \(\sum\limits_{i=1}^n\sum\limits_{j=1}^n\text{sgcd}(i,j)^k\)

其中 \(\text{sgcd}(i,j)\) 表示 \(i,j\) 的次大公约数。特别地,如果 \(\text{gcd}(i,j)=1\),则 \(\text{sgcd}(i,j)=0\)

答案对 \(2^{32}\) 取模。

\(n \le 10^9,k \le 50\)

\(p_i\) 表示第 \(i\) 个质数,\(d_i\) 表示 \(i\) 的最小质因子。

\(\text{sgcd}(i,j)=\dfrac{\gcd(i,j)}{d_{\gcd(i,j)}}\)

考虑枚举 \(\gcd\)\[ \begin{aligned} &\sum_{i=1}^n\sum_{j=1}^n\text{sgcd}(i,j)^k\\ &=\sum_{c=2}^n(\frac c{d_c})^k\sum_{i=1}^{\lfloor\frac nc\rfloor}\sum_{j=1}^{\lfloor\frac nc\rfloor}[gcd(i,j)=1]\\ &=\sum_{c=2}^n(\frac c{d_c})^k(2\sum_{i=1}^{\lfloor\frac nc\rfloor}\varphi(i)-1) \end{aligned} \] 现在的问题是算 \((\frac x{d_x})^k\)\(\varphi(x)\)\(\lfloor \frac nc \rfloor\) 处的前缀和,后者直接杜教筛即可。

对于前者,由于涉及到 \(d_x\) 考虑 Min-25 筛

\[ g(n,i) = \sum_{j=2}^n [j \in P \lor d_j > p_i]j^k\\ f(n,i) = \sum_{j=2}^n [j \not\in P \land d_j \le p_i](\frac j{d_j})^k\\ h(h,i) = \sum_{j=2}^n [j \in P \lor d_j > p_i] \] 有递推 \[ g(n, i) = g(n, i - 1) - p_i^k(g(\lfloor\frac n {p_i} \rfloor, i - 1) - g(p_i-1,i))\\ f(n,i) = f(n,i-1)+g(\lfloor\frac n {p_i} \rfloor,i-1) - g(p_i-1,i)\\ h(n,i)=h(n,i-1)-h(\lfloor\frac n {p_i} \rfloor, i - 1) + h(p_i-1,i) \] 初始化 \[ g(n,0)=\sum_{i=2}^ni^k\\ f(n,0)=0\\ h(n,0)=n-1 \] 这里需要求自然数等幂和

\(n < p_i^2\) 时都不需要转移,因此这是一个标准的 Min-25 筛。

复杂度 \(O(\frac {n^{\frac 34}}{\log n}+n^{\frac 23})\)

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <bits/stdc++.h>
#define rep(i, l, r) for(int i = (l); i <= (r); i++)
#define per(i, r, l) for(int i = (r); i >= (l); i--)
#define mem(a, b) memset(a, b, sizeof a)
#define For(i, l, r) for(int i = (l), i##e = (r); i < i##e; i++)
#define pb push_back

using namespace std;
typedef unsigned int U;

int n, K;
namespace Sum {
U S[55][55];
void pre() {
S[0][0] = 1;
rep(i, 1, K) rep(j, 1, i) S[i][j] = S[i - 1][j - 1] + (U)j * S[i - 1][j];
}
U qry(int n, U re = 0) {
rep(i, 1, K) {
U t = 1;
rep(j, n + 1 - i, n + 1) if(j % (i + 1)) t *= j;
else t *= j / (i + 1);
re += t * S[K][i];
}
return re - 1u;
}
};
namespace Du {
int m, pid, prm[100000];
U phi[1000005], S[1005];
void pre() {
m = pow(n, 2. / 3);
phi[1] = 1;
rep(i, 2, m) {
if(!phi[i]) phi[i] = i - 1, prm[++pid] = i;
for(int j = 1; i * prm[j] <= m; j++)
if(i % prm[j]) phi[i * prm[j]] = phi[i] * phi[prm[j]];
else { phi[i * prm[j]] = phi[i] * prm[j]; break; }
}
rep(i, 1, m) phi[i] += phi[i - 1];
}
U qry(int i) {
if(i <= m) return phi[i];
if(S[n / i]) return S[n / i];
U res = i * (i + 1ll) / 2;
for(int l = 2, r; l <= i; l = r + 1) {
r = i / (i / l);
res -= qry(i / l) * (r - l + 1);
}
return S[n / i] = res;
}
};
namespace M25 {
constexpr int N = sqrt(1e9) + 5;
int m;
U g1[N], g2[N], f1[N], f2[N], h1[N], h2[N];
void pre() {
m = sqrt(n);
rep(i, 1, m) {
g1[i] = Sum::qry(i), g2[i] = Sum::qry(n / i);
h1[i] = i - 1, h2[i] = n / i - 1;
}
rep(p, 2, m) if(h1[p] ^ h1[p - 1]) {
int w1 = m / p, w3 = p * p, w2 = min(m, n / w3);
int j, d = n / p;
U x = 1, gx = g1[p - 1], hx = h1[p - 1];
rep(i, 1, K) x *= p;
rep(i, 1, w1) {
j = i * p, h2[i] -= h2[j] - hx;
f2[i] += g2[j] - gx, g2[i] -= x * (g2[j] - gx);
}
rep(i, w1 + 1, w2) {
j = d / i, h2[i] -= h1[j] - hx;
f2[i] += g1[j] - gx, g2[i] -= x * (g1[j] - gx);
}
per(i, m, w3) {
j = i / p, h1[i] -= h1[j] - hx;
f1[i] += g1[j] - gx, g1[i] -= x * (g1[j] - gx);
}
}
}
U qry(int i) {return i <= m ? f1[i] + h1[i] : f2[n / i] + h2[n / i]; }
};
int main() {
cin >> n >> K;
Sum::pre(), Du::pre(), M25::pre();
U as = 0;
for(int l = 2, r; l <= n; l = r + 1) {
r = n / (n / l);
as += (2u * Du::qry(n / l) - 1u) * (M25::qry(r) - M25::qry(l - 1));
}
cout << as;
return 0;
}
阅读全文 »

题目链接

给定一张 \(n\) 个点 \(m\) 条边的无向连通图和正整数 \(x\),点有非负权值 \(a_i\)

如果一条边 \((u,v)\) 满足 \(a_u+a_v \ge x\),可以将 \(u,v\) 缩起来,新点的点权为 \(a_u+a_v-x\)

判断这张图是否可以缩成一个点并给出方案。

\(n,m \le 3 \cdot 10^5,x,a_i \le 10^9\)

首先将每个点的点权减去 \(x\),则合并条件变为 \(a_u + a_v \ge -x\),每次合并后新点的点权为 \(a_u + a_v\)

结论:这张图可以缩成一个点的充要条件是点权和大于等于 \(-x\)

必要性显然,充分性可以考虑这个构造:每次选择点权最大的点 \(u\) 的任意一条边。

构造的正确性可以考虑反证法,设这条边为 \((u,v)\),假设这条边不行,即 \(a_u+a_v<-x\)

进一步 \(\because a_v \ge -x,\therefore a_u < 0\)

由于 \(a_u\) 是最大值,因此所有点的点权都是负数,那么 \(a_u+a_v \ge \sum a_i \ge -x\),推出矛盾!

至此,已经得到一个做法。

但还有更简单的做法,根据上面结论,任意求一棵生成树都有可行方案。

先从叶子向根依次考虑每个结点,如果这个结点权值非负,则选择它和它父亲的连边,再从根向叶子依次考虑每个结点,如果它和它父亲的连边还没选,则选择这条边。

阅读全文 »

坐标轴上有 \(N\) 场展览会,每场展览会有一个举行时间 \(T_i\) ,举行地点 \(L_i\) 和获利 \(M_i\)

坐标向大移动 \(1\) 的代价是 \(D\),向小移动 \(1\) 的代价是 \(U\),速度为任意大。

每场展览会只能参加一次,问从 \(S\) 出发最后再回到 \(S\) 的最大获利。

\(N,T_i \le 5 \cdot 10^5,L_i \le 5 \cdot 10^5+1\)

先考虑一个弱化版的问题:\(T_i\) 互不相同。

\(f_i\)表示刚参加第 \(i\) 场展览会后的最大获利。

有转移方程 \(f_i = \max\limits_{T_j < T_i}f_j-cost(j,i)\)

其中 \[ cost(i,j)=\begin{cases} D(L_j-L_i) &(L_i<L_j)\\ U(L_i-L_j) &(L_i>L_j) \end{cases} \] 两种情况分别用树状数组维护前缀(后缀)最大值即可实现 \(O(\log n)\) 转移。

再考虑同一天的多场展览会怎么处理。

\(f_{i,0/1}\) 表示从左/右到达第 \(i\) 场展览会后的最大获利。

然后正反两遍 DP,每次用临时变量存由同一天的展览会转移来最优解,和树状数组中的最优解取个较优,计算出 DP 值后再把这一天所有展览会插入树状数组。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <bits/stdc++.h>
#define rep(i, l, r) for(int i = (l); i <= (r); i++)
#define per(i, r, l) for(int i = (r); i >= (l); i--)
#define mem(a, b) memset(a, b, sizeof a)
#define upd(a, b) (a = max(a, b))
#define pb push_back

using namespace std;
const int N = 5e5 + 5;
int read() {
int c = getchar(), r = 0;
while(c < 48) c = getchar();
while(c > 47) r = r * 10 + c - 48, c = getchar();
return r;
}
int n, U, D, s, L[N], M[N], f[N][2];
vector <int> id[N];
struct BIT {
int c[N];
BIT() { rep(i, 1, N - 4) c[i] = INT_MIN; }
void ins(int i, int v) { for(; i <= N - 4; i += i & -i) upd(c[i], v); }
int qry(int i, int r = INT_MIN) { for(; i; i &= i - 1) upd(r, c[i]); return r; }
} Td, Tu;
void ins(int i, int v) {
Td.ins(i, v - (N - i) * D), Tu.ins(N - 3 - i, v - i * U);
}
int qry(int i) {
return max(Td.qry(i) + (N - i) * D, Tu.qry(N - 3 - i) + i * U);
}
int main() {
cin >> n >> U >> D >> s;
rep(i, 1, n) id[read()].pb(i), L[i] = read(), M[i] = read();
ins(s, 0);
rep(i, 1, N - 5) {
sort(id[i].begin(), id[i].end(), [](int a, int b) { return L[a] < L[b]; });
int pre = INT_MIN, suf = INT_MIN;
for(int j : id[i])
upd(pre, (f[j][0] = max(qry(L[j]), pre + (N - L[j]) * D) + M[j]) - (N - L[j]) * D);
for(auto j = id[i].rbegin(); j != id[i].rend(); j++)
upd(suf, (f[*j][1] = max(qry(L[*j]), suf + L[*j] * U) + M[*j]) - L[*j] * U);
for(int j : id[i]) ins(L[j], max(f[j][0], f[j][1]));
}
cout << qry(s);
return 0;
}
阅读全文 »

题目链接

给定 \(n,k\),对于每个 \(i \in [1,k]\),你需要求出有多少个长度为 \(n\) 的排列能通过恰好 \(i\) 次交换操作变成 \(\{1,2,\cdots,n\}\)

答案对 \(10^9+7\) 取模。

\(n \le 10^9,k \le 200\)

先考虑这样一个问题:给定一个排列 \(P\),最少交换几次才能变成 \(\{1,2,\cdots,n\}\)

把排列 \(P\) 理解成一个置换,并分解成循环,不难发现 \(i\) 个元素的循环需要交换 \(i-1\) 次。

这样,如果 \(P\) 的循环节为 \(x\),则总的交换次数为 \(n-x\)

涉及到点数和循环数不难想到第一类斯特林数

\(i\) 的答案即 \({n \brack n-i}+{n \brack n-i+2}+{n \brack n-i+4} + \cdots\)

问题是 \(n\) 太大了,不能递推求出第一类斯特林数。

由于 \(i\) 次交换最多影响 \(2i\) 个元素,一个合法的排列 \(P\) 至多有 \(2i\) 个位置 \(j\) 满足 \(j \ne P_j\)

可以枚举有多少个 \(j\) 满足 \(j \ne P_j\),如果有 \(x\) 个,对答案的贡献为 \(\binom nxf_{x,x-i}\)

其中 \(f_{i,j}\) 表示有多少个长度为 \(i\)错排循环节为 \(j\),它可以通过第一类斯特林数容斥得到: \[ f_{i,j}={i \brack j}-\sum_{k=1}^j\binom ikf_{i-k,j-k} \] 复杂度 \(O(k^3)\)

阅读全文 »

题目链接

给定平面上的 \(n\) 个点 \((\frac {a_i}{b_i},\frac {c_i}{d_i})\),定义一个点 \((x,y)\)派生点为点 \((x+1,y)\) 和点 \((x,y+1)\)

两个点 \(A,B\) 能够匹配当且仅当 \(A\) 的一个派生点和 \(B\) 的一个派生点在同一条过原点的直线上。

求出最大匹配的大小和任意一种方案。

\(n \le 2 \cdot 10^5,1 \le a_i,b_i,c_i,d_i \le 10^9\)

两个第一象限的点在同一条过原点的直线上等价于两个点的横纵坐标之比相等。

定义一个点 \((x,y)\)派生值\(\frac {x+1}y\)\(\frac x{y+1}\)

两个点 \(A,B\) 能够匹配即拥有同一个派生值。

把所有的派生值抽象成点,给定的点抽象成边,匹配条件进一步转化为两条边拥有公共顶点

引理:一个连通无向图能够给每条边定向使得每个点入度为偶数当且仅当边数为偶数。

证明:边数为奇数显然不行,下面给出边数为偶数时的构造:

先建树 DFS 树,所有反向边都向上,如果两个端点都在点 \(u\) 子树内的边的数量为偶数,则 \(u\) 与其父亲的连边(如果存在)向上,否则向下。

通过引理不难推出一个边数为 \(m\) 的连通图的答案为 \(\lfloor \frac m2 \rfloor\),求方案可以先给每条边定向,再把每个点的所有入边两两配对。

只需要对每个连通块做一遍即可。

最后一个问题:派生值是分子分母都是 \(10^{18}\) 级别的分数,离散化时需要排序,但如何比较。

一种方法是转 __int128 交叉相乘比较大小。其实不一定要按分数值排序,双关键字排序同样能实现离散化,先约分,再以分子、分母为两关键字比较则是另一种更快的方法。

阅读全文 »

题目链接

给定一个长度为 \(n\) 的序列和数 \(k\),求有多少长度大于 \(1\) 的区间满足和减最大值是 \(k\) 的倍数。

\(n \le 3 \cdot 10^5,k \le 10^6,a_i \le 10^9\)

先求出前缀和数组 \(pre\)

则条件可以写成 \(pre_r \equiv pre_{l-1} + \max \pmod k\)

\(i\) 插入 \(\text{vector}[pre_i \bmod k]\),通过二分可以快速查询区间中有多少前缀和模 \(k\)\(x\)

求出整个序列的最大值的位置为 \(x\)

然后枚举 \(x\) 左边的前缀和,查询 \(x\) 右边有多少个前缀和与之配对。

因为 \(x\) 的位置不确定,所以这样是 \(O(n^2\log n)\)

但如果每次枚举左右中较短的一段,则复杂度可降为 \(O(n \log^2 n)\)

其实不用真的分治,只需要单调栈求出每个位置作为最大值的极大区间即可。

代码:

阅读全文 »

给定一个 \(n\) 次多项式 \(A\) 和一个 \(m\) 次多项式 \(B\),计算 \(A \times B\),系数对 \(p\) 取模。

\(n,m \le 10^5\)

常见的有两种做法:

  • 先做三模数 NTT 再用中国剩余定理合并。
阅读全文 »

题目链接

有一张 \(n\) 个点的无向完全图,其中 \(m\) 条边的边权已给定。

你需要给剩下的边确定边权,使得所有边的权值异或和为 \(0\)

求出所有方案中最小生成树权值的最小值。

\(n \le 2 \cdot 10^5,m \le \min\{2 \cdot 10^5,\binom n2-1\}\)

下面原图指给定的 \(m\) 条边构成的图,补图指剩下的边构成的图,MST 指最小生成树。

引理:最优解中补图至多有一条权值非 \(0\) 的边。

证明:考虑两条补图边 \(e_1,e_2\),它们的权值 \(w_1,w_2\) 都大于 \(0\)

  • 如果它们都不在 MST 上,把 \(e_1\) 权值变为 \(0\)\(e_2\) 权值异或上 \(e_1\) 权值,新的 MST 不会变劣。
  • 如果它们都在 MST 上,把 \(e_1\) 权值变为 \(0\)\(e_2\) 权值异或上 \(e_1\) 权值,因为 \(w_1 \oplus w_2 \le w_1 + w_2\),所以新的 MST 不会变劣。
  • 如果它们中的一条在 MST 上,一条不在,不妨设 \(e_1\)MST 上,把 \(e_1\) 权值变为 \(0\)\(e_2\) 权值异或上 \(e_1\) 权值,新的 MST 不会变劣。

综上,如果存在两条权值大于 \(0\) 的边,把其中一条的权值变为 \(0\),新的 MST 不会变劣。

所以补图中有一条特殊边的权值恰好为给定的 \(m\) 条边的权值异或和,其余边的权值均为 \(0\)

容易想到枚举一下特殊边在不在 MST 上。

先用 DFS 求出补图的生成森林,用 set 优化枚举未访问的点可以做到 \(O(m\log n)\) 的复杂度。

如果补图中存在环,那么补图中一定有边不在 MST 上,故特殊边一定不在 MST 上。把求出的生成森林加入原图后,答案即为该图的最小生成树,复杂度 \(O(m\log m)\)

如果不存在环,那么 \(n\) 就是 \(O(\sqrt m)\) 级别的,如果特殊边在 MST 上,直接用同样的做法;如果不在 MST 上,就需要枚举特殊边是哪一条,每次删去它再沿用以上做法,复杂度 \(O(m \log m + nm\alpha(n))\)。一个优化:用原图的最小生成树替代原图,复杂度降为 \(O(m\log m + n^2\alpha(n))=O(m\log m)\)

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <bits/stdc++.h>
#define rep(i, l, r) for(int i = (l); i <= (r); i++)
#define per(i, r, l) for(int i = (r); i >= (l); i--)
#define mem(a, b) memset(a, b, sizeof a)
#define For(i, l, r) for(int i = (l), i##e = (r); i < i##e; i++)
#define pb push_back

using namespace std;
const int N = 2e5 + 5;
typedef long long ll;
int n, m, fa[N], xorsu, eid, tid;
int find(int x) { return x ^ fa[x] ? fa[x] = find(fa[x]) : x; }
int mrg(int u, int v) {
if((u = find(u)) ^ (v = find(v))) return fa[u] = v;
return 0;
}
vector <int> G[N];
struct edge {
int u, v, w;
bool operator <(const edge& b)const {
return w < b.w;
}
} e[N], t[N];
set <int> s;
void dfs(int u) {
s.erase(u);
For(i, 0, G[u].size() - 1) {
int v = G[u][i], nxt = G[u][i + 1];
while(!s.empty() && *s.rbegin() > v) {
int vv = *s.upper_bound(v);
if(vv >= nxt) break;
t[++tid] = {u, vv}, dfs(vv);
}
}
}
int main() {
cin >> n >> m;
rep(i, 1, m) {
scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w), xorsu ^= e[i].w;
G[e[i].u].pb(e[i].v), G[e[i].v].pb(e[i].u);
}
rep(i, 1, n) G[i].pb(0), G[i].pb(n + 1), sort(G[i].begin(), G[i].end()), s.insert(i);
while(!s.empty()) dfs(*s.begin());
sort(e + 1, e + m + 1);
rep(i, 1, n) fa[i] = i;
rep(i, 1, m) if(mrg(e[i].u, e[i].v)) e[++eid] = e[i];
if(tid < n * (n - 1ll) / 2 - m) {
rep(i, 1, n) fa[i] = i;
rep(i, 1, tid) mrg(t[i].u, t[i].v);
ll as = 0;
rep(i, 1, eid) if(mrg(e[i].u, e[i].v)) as += e[i].w;
cout << as;
} else {
ll as = 1e18;
rep(i, 0, tid) {
rep(j, 1, n) fa[j] = j;
rep(j, 1, tid) if(j ^ i) mrg(t[j].u, t[j].v);
ll su = i ? 0 : xorsu;
rep(j, 1, eid) if(mrg(e[j].u, e[j].v)) su += e[j].w;
as = min(as, su);
}
cout << as;
}
return 0;
}
阅读全文 »