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;
}
上一篇: 「NOIP2017」 奶酪 - 并查集
下一篇: [NOIP模拟] Road (并查集)