酒店网站开发协议,青海省建筑信息平台,app开发需要的技术,申请163 com免费邮箱正题
题目链接:https://loj.ac/p/3130 题目大意
给出nnn个点mmm条边的一张有权无向图#xff0c;你每次可以选择一个边集异或上一个值#xff0c;要求最少次数使得所有简单环异或和都为000。 1≤n,m≤1051\leq n,m\leq 10^51≤n,m≤105 解题思路
先找一棵生成树#xff0…正题
题目链接:https://loj.ac/p/3130 题目大意
给出nnn个点mmm条边的一张有权无向图你每次可以选择一个边集异或上一个值要求最少次数使得所有简单环异或和都为000。
1≤n,m≤1051\leq n,m\leq 10^51≤n,m≤105 解题思路
先找一棵生成树然后每条非树边都会产生一个简单环显然这些简单环合法了其他的也一定合法。
而肯定存在一种最优的方案是只改非树边因为如果该树边首先我们可以一次改一个集合所有必须改一条树边会对多个简单环产生不同的影响而如果我们异或的是valvalval那么我们能做到的只是让某个简单环异或上valvalval奇数条树边操作或者不异或上valvalval偶数条树边操作所以是和我们操作非树边能做到的是相同的。
那么问题就变为已知一些数要异或多少求最少操作次数了我们用线性基求出最小的线性空间就好了。
时间复杂度O(nmlogm)O(nm\log m)O(nmlogm) code
#includecstdio
#includecstring
#includealgorithm
#includevector
#define mp(x,y) make_pair(x,y)
using namespace std;
const int N1e510;
struct node{int to,next,w;
}a[N1];
int n,m,tot,k,w[N],d[N],ls[N],v[N];
bool vis[N];
void addl(int x,int y,int w){a[tot].toy;a[tot].nextls[x];ls[x]tot;a[tot].ww;return;
}
void dfs(int x,int fa){vis[x]1;for(int ils[x];i;ia[i].next){int ya[i].to;if(yfa)continue;if(vis[y]){if(i1)v[(i1)/2]w[x]^w[y]^a[i].w;}else{w[y]w[x]^a[i].w;dfs(y,x);}}return;
}
void ins(int x){for(int i29;i0;i--)if((xi)1){if(d[i])x^d[i];else {d[i]x;k(x!0);break;}}return;
}
int main()
{scanf(%d%d,n,m);for(int i1,x,y,w;im;i){scanf(%d%d%d,x,y,w);addl(x,y,w);addl(y,x,w);}dfs(1,0);for(int i1;im;i)ins(v[i]);printf(%d\n,k);for(int i0;i29;i)if(d[i]){int cnt0;for(int j1;jm;j)cnt((v[j]i)1);printf(%d %d ,d[i],cnt);for(int j1;jm;j)if((v[j]i)1)printf(%d ,j);putchar(\n);}return 0;
}
