CF1423N BubbleSquare Tokens
有一个很经典的思路。发现直接不好做，因为改边会影响一对点，所以考虑钦定操作顺序，按编号从小到大做，使得已经操作过的点的 token 不会改变。这样做最大的好处在于每次只用仅仅考虑当前操作点的 token 是否与相邻已操作的点的 token 一致。
那么现在将改点权和改边权结合，有两种操作满足上述条件：
- 点权减一，边权加一，这会使得当前操作点的 token 加一
- 点权加一，边权减一，这会使得当前操作点的 token 减一
考虑如何最好地利用这两种操作，首先有边权的限制，但是注意到边权只有加一减一操作，并且每条边至多被操作一次，这启发我们初始钦定每条边边权为 \(1\)，这样就不用考虑边权的限制了。
这样，我们将相邻的已钦定 token 的点按照当前点权分为两类，不妨设点权为 \(0\) 的点的个数为 \(c_0\)，反之为 \(c_1\)。假设当前操作点的原始 token 为 \(s\)，那么通过上面两种操作，可以将 token 调整至 \([s - c_0, s + c_1]\) 中任意一个整数。
由鸽巢原理得知必定有解。
总结：这类修改影响多个点的构造题可以钦定操作顺序，然后保证每次操作后之前的总和不变。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
namespace IO {
#define isdigit(x) (x >= '0' && x <= '9')
template<typename T>
inline void read(T &x) {
x = 0; char ch = getchar(); int f = 0;
for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = 1;
for(; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
if(f) x = -x;
}
template<typename T>
inline void write(T x) {
if(x < 0) putchar('-'), x = -x;
if(x > 9) write(x / 10);
putchar(x % 10 + '0');
}
#undef isdigit
}
using namespace IO;
const int N = 12500 + 10;
const int M = 1e6 + 10;
int n, m;
int x[M], y[M];
int s[N], v[N], ans[M];
int vis[M << 2];
vector<int> G[N];
inline void rev(int p, int t) {
if(v[p] == 0) {
v[p] = 1, ++s[p];
--ans[t], --s[x[t]], --s[y[t]];
}
else {
v[p] = 0, --s[p];
++ans[t], ++s[x[t]], ++s[y[t]];
}
}
int main() {
read(n), read(m);
for(int i = 1, a, b; i <= m; ++i) {
read(a), read(b);
if(a < b) swap(a, b);
G[a].emplace_back(i);
x[i] = a, y[i] = b;
++s[a], ++s[b];
ans[i] = 1;
}
for(int i = 1; i <= n; ++i) {
int c0 = 0, c1 = 0;
for(int e : G[i]) {
int j = y[e];
if(v[j] == 0) ++c0;
else ++c1;
vis[s[j]] = 1;
}
int delta = 0;
for(int j = -c0; j <= c1; ++j)
if(!vis[s[i] + j])
delta = j;
for(int e : G[i])
vis[s[y[e]]] = 0;
for(int e : G[i]) {
int j = y[e];
if(v[j] == 0 && delta < 0)
++delta, rev(j, e);
else if(v[j] == 1 && delta > 0)
--delta, rev(j, e);
}
}
vector<int> vec;
for(int i = 1; i <= n; ++i)
if(v[i] == 1) vec.emplace_back(i);
printf("%d\n",(int)vec.size());
for(int x : vec)
printf("%d ",x);
puts("");
for(int i = 1; i <= m; ++i)
printf("%d %d %d\n",x[i],y[i],ans[i]);
return 0;
}