[洛谷 1525][NOIP2010]关押罪犯

题目链接

https://www.luogu.org/problem/P1525

题解

Part 1 并查集解法

我们将所有边按边权降序排列。

将每个节点 \(i\) 拆成两个点 \(i,i+n\)。

对于一条边连接的两个点 \(u,v\)，如果他们之前已经处于同一连通分量中，就势必要发生冲突。这个事件也就是我们要输出的事件。

如果它们不在一个集合中，我们就在 \(u,v+n\)，\(v,u+n\) 间连一条边。

#include <cstdio>
#include <algorithm>
using namespace std;
struct node
{
 int a,b,c;
}a[200005];
int fa[50005];
bool cmp(const node&a,const node&b)
{
 return a.c>b.c;
}
int find(int a)
{
 return fa[a]==a?a:fa[a]=find(fa[a]);
}
void unionn(int x,int y)
{
 x=find(x);
 y=find(y);
 fa[y]=x;
}
int main()
{
 int n,m;
 scanf("%d%d",&n,&m);
 for(int i=1;i<=2*n;i++)
  fa[i]=i;
 for(int i=1;i<=m;i++)
  scanf("%d%d%d",&a[i].a,&a[i].b,&a[i].c);
 sort(a+1,a+m+1,cmp);
 for(int i=1;i<=m;i++)
 {
  if(find(a[i].a)==find(a[i].b))
  {
   printf("%d",a[i].c);
   return 0;
  }
  unionn(a[i].a,a[i].b+n);
  unionn(a[i].b,a[i].a+n);
 }
 printf("0");
 return 0;
}

Part 2 二分+二分图判定解法

因为答案具有单调性（如果答案是 \(x\)，那么一切满足 \(y>x\) 的 \(y\) 都可以成为合法答案），我们可以二分答案 \(ans\)。

如何判定这个答案是否合法（即会产生冲突）呢？

我们每次只将边权大于 \(ans\) 的边加入图中，然后跑一遍二染色。注意到如果没有冲突产生，那么这个图就是个二分图（即可以将图上的点划分为两个集合，且集合内的任意两个点没有冲突（即没连边））。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct edge
{
 int v,w,next;
}e[200005];
int head[20005],w[100005],col[20005],n,m,cnt;
void addedge(int u,int v,int w)
{
 e[++cnt].v=v;
 e[cnt].w=w;
 e[cnt].next=head[u];
 head[u]=cnt;
}
bool dfs(int u,int w,int c)
{
 col[u]=c;
 for(int i=head[u];i;i=e[i].next)
  if(e[i].w>w)
  {
   if(col[e[i].v]==-1)
   {
    if(!dfs(e[i].v,w,!c))return false;
   }
   else if(col[u]==col[e[i].v])return false;
  }
 return true;
}
bool check(int w)
{
 bool flag=true;
 memset(col,-1,sizeof(col));
 for(int i=1;i<=n;i++)
  if(col[i]==-1)flag&=dfs(i,w,0);
 return flag;
}
int main()
{
 scanf("%d%d",&n,&m);
 for(int i=1;i<=m;i++)
 {
  int u,v;
  scanf("%d%d%d",&u,&v,&w[i]);
  addedge(u,v,w[i]);
  addedge(v,u,w[i]);
 }
 sort(w+1,w+m+1);
 int l=0,r=w[m];
 while(l<r)
 {
  int mid=(l+r)>>1;
  if(check(mid))r=mid;
  else l=mid+1;
 }
 printf("%d\n",l);
 return 0;
}