CF875F Royal Questions

似乎可以按边权排序后二分图匹配

这里给一个复杂度稳定的算法

把一个公主能匹配的两个点连边,然后依次加边,每当加到一个大小为\(n\)的连通块中有\(n\)条边之后,这时形成了基环树,将这些边定向,可以使得每个点入度均为1,也就是每个点都有合法匹配(对于一棵树,有\(n-1\)条边,它们所代表的匹配也是合法的)

于是可以把所有边按边权降序排序,每次加一条边,如果使得两个不相连的连通块连通,并且连通后不超过一个环,或者是使一个无环连通块出现环,答案就可以加上这条边的边权.注意如果连通块有环要在根处打标记

#include<bits/stdc++.h>

#define il inline

#define re register

#define LL long long

#define db double

#define ldb long double

#define eps (1e-7)

using namespace std;

const int N=200000+10,mod=20021101;

il LL rd()

{

    LL x=0,w=1;char ch=0;

    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}

    while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}

    return x*w;

}

struct edge

{

  int x,y,z;

  bool operator < (const edge &bb) const {return z>bb.z;}

}e[N];

int n,m,fa[N],a[N];

il int findf(int x){return fa[x]==x?x:fa[x]=findf(fa[x]);}

il bool merg(int x,int y)

{

  int xx=findf(x),yy=findf(y);

  if(a[xx]&&a[yy]) return false;

  if(xx==yy) a[xx]=1;

  else fa[yy]=xx,a[xx]|=a[yy];

  return true;

}

int main()

{

  m=rd(),n=rd();

  for(int i=1;i<=n;i++)

    {

      int x=rd(),y=rd(),z=rd();

      e[i]=(edge){x,y,z};

    }

  sort(e+1,e+n+1);

  int ans=0;

  for(int i=1;i<=m;i++) fa[i]=i;

  for(int i=1;i<=n;i++)

    {

      int x=e[i].x,y=e[i].y,z=e[i].z;

      if(merg(x,y)) ans+=z;

    }

  printf("%d\n",ans);

  return 0;

}

巴特西

CF875F Royal Questions

最新文章

热门文章