自动搬运

查看原文

来自洛谷，原作者为

	larsr loser

搬运于2025-08-24 22:28:43，当前版本为作者最后更新于2024-06-11 19:34:03，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

很好的一道题，但我没做出来。

先假设我们已经决定好边权值的最终值了，此时要用最少次数，很容易想到要用线性基。

那怎么决定最终值呢？首先选择在图上随便选一个生成树，如果一条非树边和它的两个端点路径的回路满足条件的话，那么这个图一定满足条件。

为什么呢？因为一边非树边和它的两个端点路径异或值相等，可以把非树边换成这条路径，那么任何一个回路，都会经过同一条边两次或不经过。

这是只改非树边是最优的，为什么呢？一个回路上更改的值的异或值是一定的，如果只更改非树边，变化量只有一个，线性基的结果也是最小的。那么求出每个非树边要更改的值即可。

时间复杂度 $O(n\log V)$。

#include<cstdio>
#include<vector>
#include<cstring>
#define N 100010
using namespace std;
int n, m, vis[N], d[N];
struct edge
{
	int to, w, id;
};
vector<edge>e[N];
int vid[N];
int xe[N], xid[N], tot = 0;
int bit[100];
vector<int>ans[100];
void dfs(int now)
{
	vis[now] = 1;
	for(int i = 0; i < e[now].size(); i++)
		if(!vis[e[now][i].to])
		{
			d[e[now][i].to] = d[now] ^ e[now][i].w;
			dfs(e[now][i].to);
		}
}
void dfs1(int now, int fa)
{
	vis[now] = 1;
	for(int i = 0; i < e[now].size(); i++)
	{
		int to = e[now][i].to;
		if(!vis[to])
		{
			dfs1(to, now);
		}
		else if(to != fa && !vid[e[now][i].id])
		{
			tot++;
			vid[e[now][i].id] = 1;
			xe[tot] = d[now] ^ d[to] ^ e[now][i].w;
			xid[tot] = e[now][i].id;
		}
	}
}
int main()
{
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= m; i++)
	{
		int a, b, p;
		scanf("%d%d%d", &a, &b, &p);
		e[a].push_back((edge){b, p, i});
		e[b].push_back((edge){a, p, i});
	}
	dfs(1);
	memset(vis, 0, sizeof vis);
	dfs1(1, 0);
	for(int i = 1; i <= tot; i++)
	{
		int now = xe[i];
		for(int j = 30; j >= 0; j--)
			if(now & (1 << j))
			{
				if(bit[j])now ^= bit[j];
				else
				{
					bit[j] = now;
					break;
				}
			}
	}
	for(int i = 1; i <= tot; i++)
	{
		int now = xe[i];
		for(int j = 30; j >= 0; j--)
			if(now & (1 << j))
			{
				ans[j].push_back(xid[i]);
				now ^= bit[j];
			}
	}
	int sum = 0;
	for(int i = 30; i >= 0; i--)
		if(bit[i])
			sum++;
	printf("%d\n", sum);
	for(int i = 30; i >= 0; i--)
	if(bit[i])
	{
		printf("%d %d ", bit[i], ans[i].size());
		for(int j = 0; j < ans[i].size(); j++)printf("%d ", ans[i][j]);
		printf("\n");
	}
	return 0;
}