福州免费网站建站模板,seo推广软件代理,石家庄医院网站建设,北京百度推广传送门 文章目录题意#xff1a;思路题意#xff1a;
给你一张nnn个点mmm个边的图#xff0c;mmm条边是给定的#xff0c;要求你给未给定的边赋值一个边权#xff0c;使得所有边权异或和为000#xff0c;求所有满足这种情况的图中最小生成树边权和最小的#xff0c;输出…传送门
文章目录题意思路题意
给你一张nnn个点mmm个边的图mmm条边是给定的要求你给未给定的边赋值一个边权使得所有边权异或和为000求所有满足这种情况的图中最小生成树边权和最小的输出最小生成树的边权和。
思路
我们先假设多余的边边权都为000已经有的边的异或和为sumxorsum_{xor}sumxor加上多余的边跑最小生成树后如果还有多余的边不在生成树中那么答案显然为当前MSTMSTMST的权值因为我们可以选一条不在MSTMSTMST中的边让他的权值为sumxorsum_{xor}sumxor。否则多余的边都在生成树里那么一个最优的情况一定是选出一条多余的边使其边权为sumxorsum_{xor}sumxor其他的边权为000。 那么我们拿出来多余的边即原图的补图找到补图中所有的联通块之后再用本来就有的边将联通块联通当前的答案为ansansans现在我们需要判断一下是否有多余的边剩下这个可以算一下restn∗(n−1)2−mrest\frac{n*(n-1)}{2}-mrest2n∗(n−1)−m让后每加一条边就让rest−−rest--rest−−最后看看是否rest0rest0rest0即可如果剩下了直接输出ansansans否则我们需要找到一条多余的边使其边权为sumxorsum_{xor}sumxor我们可以枚举原图的边来判断一下能否用原图中的边替代来让答案边的更小注意我们上面连接补图的联通块的边不能被替代。
// Problem: C. Complete the MST
// Contest: Codeforces - Codeforces Round #715 (Div. 1)
// URL: https://codeforces.com/problemset/problem/1508/C
// Memory Limit: 256 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)//#pragma GCC optimize(Ofast,no-stack-protector,unroll-loops,fast-math)
//#pragma GCC target(sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tunenative)
//#pragma GCC optimize(2)
#includecstdio
#includeiostream
#includestring
#includecstring
#includemap
#includecmath
#includecctype
#includevector
#includeset
#includequeue
#includealgorithm
#includesstream
#includectime
#includecstdlib
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define pb push_back
#define mk make_pair
#define Mid (tr[u].ltr[u].r1)
#define Len(u) (tr[u].r-tr[u].l1)
#define random(a,b) ((a)rand()%((b)-(a)1))
#define db puts(---)
using namespace std;//void rd_cre() { freopen(d://dp//data.txt,w,stdout); srand(time(NULL)); }
//void rd_ac() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//AC.txt,w,stdout); }
//void rd_wa() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//WA.txt,w,stdout); }typedef long long LL;
typedef unsigned long long ULL;
typedef pairint,int PII;const int N1000010,mod1e97,INF0x3f3f3f3f;
const double eps1e-6;int n,m;
int p[N];
LL rest,xr;
bool st[N];
setintv[N],all;
struct Node {int a,b,w,flag; bool operator (const Node W) const {return wW.w;}
}edge[N];int find(int x) {return xp[x]? x:p[x]find(p[x]);
}void get_block() {queueintq;vectorintnow;for(int i1;in;i) {if(!st[i]) {q.push(i); st[i]1;all.erase(i);while(q.size()) {int uq.front(); q.pop();now.clear();for(auto x:all) {if(v[u].count(x)) continue;q.push(x); now.pb(x);st[x]1; p[x]u;rest--;}for(auto x:now) all.erase(x);}}}
}int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);cinnm;rest1ll*n*(n-1)/2-m;for(int i1;in;i) all.insert(i),p[i]i;for(int i1;im;i) {int a,b,c; scanf(%d%d%d,a,b,c);edge[i]{a,b,c,0};v[a].insert(b); v[b].insert(a);xr^c;}get_block();sort(edge1,edge1m);LL ans0;for(int i1;im;i) {int aedge[i].a,bedge[i].b,wedge[i].w;afind(a); bfind(b);if(ab) continue;p[a]b; answ; edge[i].flag1;}if(rest0) {printf(%lld\n,ans);return 0;}for(int i1;in;i) p[i]i;for(int i1;im;i) {int aedge[i].a,bedge[i].b,wedge[i].w;afind(a); bfind(b);if(ab) continue;p[a]b; if(!edge[i].flag) xrmin(xr,1ll*w);}printf(%lld\n,ansxr);return 0;
}
/**/
