2024河南萌新联赛第五场 C小美想收集（并查集拓展域，2-sat）

题目链接

思路：

这题是并查集拓展域板题，而且并查集拓展域其实就是2-sat，虽然做法不同，但是思想是相通的，也可以用2-sat来做。

一个回忆可以看成在好回忆或在坏回忆里，两种选择。

code：

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=2e5+5;
const int maxm=1e5+5;int n,m;struct edge{int u,v,w;edge(int u=0,int v=0,int w=0):u(u),v(v),w(w){};bool operator<(const edge x)const{return w>x.w;}
}e[maxm];int f[maxn<<1];
int findf(int x){return f[x]==x?x:f[x]=findf(f[x]);}
void merge(int x,int y){int fx=findf(x),fy=findf(y);f[fy]=fx;
}int main(){cin>>n>>m;for(int i=1;i<=m;i++)cin>>e[i].u>>e[i].v>>e[i].w;sort(e+1,e+m+1);for(int i=1;i<=(n<<1);i++)f[i]=i;for(int i=1;i<=m;i++){auto [u,v,w]=e[i];
//		printf("^^^%d %d %d\n",u,v,w);if(findf(u)!=findf(v)){//两者不在同一个集合 merge(u,v+n);merge(u+n,v);}else {printf("%d",w);break;}}return 0;
}