Codeforces Round #715 (Div. 1) C. Complete the MST 补图 + 思维 + 最小生成树题意：思路

145 阅读 0 评论 96 点赞

我是靠谱客的博主清爽小鸽子，最近开发中收集的这篇文章主要介绍Codeforces Round #715 (Div. 1) C. Complete the MST 补图 + 思维 + 最小生成树题意：思路，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

传送门

文章目录

题意：
思路

题意：

给你一张 $n$ 个点 $m$ 个边的图， $m$ 条边是给定的，要求你给未给定的边赋值一个边权，使得所有边权异或和为 $0$ ，求所有满足这种情况的图中最小生成树边权和最小的，输出最小生成树的边权和。

思路

我们先假设多余的边边权都为 $0$ ，已经有的边的异或和为 $sum_{xor}$ ，加上多余的边跑最小生成树后如果还有多余的边不在生成树中，那么答案显然为当前 $M S T$ 的权值，因为我们可以选一条不在 $M S T$ 中的边让他的权值为 $sum_{xor}$ 。否则多余的边都在生成树里，那么一个最优的情况一定是选出一条多余的边使其边权为 $sum_{xor}$ ，其他的边权为 $0$ 。
那么我们拿出来多余的边，即原图的补图，找到补图中所有的联通块，之后再用本来就有的边将联通块联通，当前的答案为 $a n s$ ，现在我们需要判断一下是否有多余的边剩下，这个可以算一下 $r e s t = n ∗ ( n − 1 ) 2 − m rest=frac{n*(n-1)}{2}-m$ ，让后每加一条边就让 $r e s t - -$ ，最后看看是否 $r e s t > 0$ 即可，如果剩下了直接输出 $a n s$ ，否则我们需要找到一条多余的边使其边权为 $sum_{xor}$ ，我们可以枚举原图的边，来判断一下能否用原图中的边替代来让答案边的更小，注意我们上面连接补图的联通块的边不能被替代。

// 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,tune=native")
//#pragma GCC optimize(2)
#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<map>
#include<cmath>
#include<cctype>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
#include<sstream>
#include<ctime>
#include<cstdlib>
#define X first
#define Y second
#define L (u<<1)
#define R (u<<1|1)
#define pb push_back
#define mk make_pair
#define Mid (tr[u].l+tr[u].r>>1)
#define Len(u) (tr[u].r-tr[u].l+1)
#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 pair<int,int> PII;

const int N=1000010,mod=1e9+7,INF=0x3f3f3f3f;
const double eps=1e-6;

int n,m;
int p[N];
LL rest,xr;
bool st[N];
set<int>v[N],all;
struct Node {
	int a,b,w,flag; 
	bool operator < (const Node &W) const {
		return w<W.w;
	}
}edge[N];

int find(int x) {
	return x==p[x]? x:p[x]=find(p[x]);
}

void get_block() {
	queue<int>q;
	vector<int>now;
	for(int i=1;i<=n;i++) {
		if(!st[i]) {
			q.push(i); st[i]=1;
			all.erase(i);
			while(q.size()) {
				int u=q.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);
		
	cin>>n>>m;
	rest=1ll*n*(n-1)/2-m;
	for(int i=1;i<=n;i++) all.insert(i),p[i]=i;
	for(int i=1;i<=m;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(edge+1,edge+1+m);
	LL ans=0;
	for(int i=1;i<=m;i++) {
		int a=edge[i].a,b=edge[i].b,w=edge[i].w;
		a=find(a); b=find(b);
		if(a==b) continue;
		p[a]=b; ans+=w; 
		edge[i].flag=1;
	}
	if(rest>0) {
		printf("%lldn",ans);
		return 0;
	}
	for(int i=1;i<=n;i++) p[i]=i;
	for(int i=1;i<=m;i++) {
		int a=edge[i].a,b=edge[i].b,w=edge[i].w;
		a=find(a); b=find(b);
		if(a==b) continue;
		p[a]=b; 
		if(!edge[i].flag) xr=min(xr,1ll*w);
	}
	printf("%lldn",ans+xr);

	return 0;
}
/*

*/