欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Luogu 1525(并查集)(NOIP 2010)

程序员文章站 2022-05-22 13:35:57
...

传送门

NOIP 2010 T3

题解:

1.二分图匹配

2.镜像并查集

P.S.小心答案为0

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
const int MAXN=2e4+4,MAXM=1e5+4;
int n,m;
int fa[MAXN<<1];
struct EDGE {
	int u,v,w;
	friend bool operator <(const EDGE &a,const EDGE &b) {
		return a.w>b.w;
	}
}e[MAXM];
inline int read() {
	int x=0;char c=getchar();
	while (c<'0'||c>'9') c=getchar();
	while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
	return x;
}
inline int find(int x) {
	return fa[x]==x?x:fa[x]=find(fa[x]);
}
int main() {
	n=read(),m=read();
	for (register int i=1;i<(n<<1);++i) fa[i]=i;
	for (register int i=0;i<m;++i) e[i].u=read(),e[i].v=read(),e[i].w=read();
	sort(e,e+m);
	int ans=0;
	for (register int i=0;i<m;++i) {
		int a=find(e[i].u),b=find(e[i].v),c=find(e[i].u+n),d=find(e[i].v+n);
		if (a==b||c==d) {ans=e[i].w;break;}
		if (a^d||b^c) fa[a]=d,fa[b]=c;
	}
	printf("%d\n",ans);
	return 0;
}