BubbleSquare Tokens
神仙构造题。
首先，我们令所有点初始都没有放币，所有边上都放了一个币。则此时每个点的权值即为它的度数。
然后，我们考虑从小到大计算每个点的权值。对于每个点 \(i\)，我们枚举它所有相邻且编号比它小的点，假如该点上没有币，就把币从连接两点的边上移到另一端的点上。明显这样操作并不会改变该点的权值，只会减少当前点的权值。
这之后，上述所有点上都有了币。则我们可以选择将某些币移回边上，显然这只会单纯增加当前点的权值。假设当前点与 \(k\) 个点相邻，则它的权值可以被加上 \([0,k]\) 中任何一个数（取决于你究竟打算移回多少个币）。而这共 \(k+1\) 个值中，最多只有 \(k\) 个值被其余点占去，则当前点完全可以占住剩下那一个。直接使用一个哈希表维护有哪些值被占去即可。
时间复杂度 \(O(k \log n)\) 或 \(O(k)\)，取决于使用哪种哈希表。
#include<bits/stdc++.h>
using namespace std;
const int N=13000;
const int M=1e6+100;
struct node{
int s,t,val;
}e[M];
int n,k,cnt;
bool vis[N];
int sum[N];
vector<int>edge[N];
set<int>S;
inline int read(){
char c=getchar();int f=1,x=0;
while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
return x*f;
}
int main(){
n=read();
k=read();
for(int i=1;i<=k;i++){
e[i].s=read();e[i].t=read();
e[i].val=1;
sum[e[i].s]++;
sum[e[i].t]++;
edge[e[i].s].push_back(i);
edge[e[i].t].push_back(i);
}
for(int i=1;i<=n;i++){
for(auto j:edge[i]){
int tmp=e[j].s^e[j].t^i;
if(tmp>i) continue;
if(!vis[tmp]){
vis[tmp]=1;
e[j].val--;
sum[i]--;
}
S.insert(sum[tmp]);
}
for(auto j:edge[i]){
int tmp=e[j].s^e[j].t^i;
if(tmp>i) continue;
if(S.find(sum[i])==S.end()) break;
vis[tmp]=0;
e[j].val++;
sum[i]++;
}
S.clear();
}
for(int i=1;i<=n;i++) cnt+=vis[i];
printf("%d\n",cnt);
for(int i=1;i<=n;i++) if(vis[i]) printf("%d ",i);
if(cnt) printf("\n");
for(int i=1;i<=k;i++) printf("%d %d %d\n",e[i].s,e[i].t,e[i].val);
return 0;
}