题解：P12544 [UOI 2025] Boys and Girls

· · 题解

也是在 5.20 写这题题解了（这什么东西这么花心啊）。

三元环计数板子题，但正解是 O(n) 我不管了。

首先我们将女生当成点，男生当成一条带权无向边 (a_i,b_i)，边权为 c_i。这相当于选出若干条边，使得边两两之间有交点，最大化边权和。

我们发现条件相当于不存在一条长度 \ge 3（边数）的链，且选出的边涉及的点连通，这就只有两种可能：菊花和三元环。

对于菊花，直接枚举菊花的中心就可以（女海王了属于是）。

对于三元环（真就三角恋啊），是经典的三元环计数问题，我们把贡献挂在度数最小的那个点上计算，复杂度 O(n\sqrt{n})，常数很小，可以通过。

#include<bits/stdc++.h>
#define ll long long
#define L x<<1
#define R x<<1|1
#define mid ((l+r)>>1)
#define lc L,l,mid
#define rc R,mid+1,r
#define Root 1,1,nb
#define OK Ll<=l&&r<=Rr
#define rep(x,y,z) for(int x=(y);x<=(z);x++)
#define per(x,y,z) for(int x=(y);x>=(z);x--)
#define repn(x) rep(x,1,n)
#define repm(x) rep(x,1,m)
#define pb push_back
#define e(x) for(int i=h[x],y=to[i];i;i=nxt[i],y=to[i])
#define E(x) for(auto y:p[x])
#define Pi pair<int,int>
#define ui unsigned ll
inline int read(){int s=0,w=1;char c=getchar();while(c<48||c>57) {if(c=='-') w=-1;c=getchar();}while(c>=48&&c<=57)s=(s<<1)+(s<<3)+c-48,c=getchar();return s*w;}
inline void pf(int x){if(x<0) putchar('-'),x=-x;if(x>9)pf(x/10);putchar(x%10+48);}
using namespace std;
const int N=1.4e6+5,M=1e6+5,inf=(1LL<<30)-1,mod=998244353;
const ll llf=1e18;
inline void add(int &a,int b){if(b<0)b+=mod;((a+=b)>=mod) and (a-=mod);}
inline int Add(int a,int b){return add(a,b),a;}
inline int mul(int a,int b){add(b,mod);return 1LL*a*b%mod;}
inline void Mul(int &a,int b){a=mul(a,b);}
inline void red(int &a,int b){add(a,mod-b);}
inline int Red(int a,int b){return red(a,b),a;}
inline int qp(int a,ll b){if(!b)return 1;int c=qp(a,b>>1LL);Mul(c,c);if(b&1)Mul(c,a);return c;}
inline int INV(int x){return qp(x,mod-2);}
int n,deg[N];
struct node{
  int y,w;
};
vector<node>p[N];
inline void add_(int a,int b,int c){
  p[a].pb({b,c});
}
int h[N],to[N],nxt[N],w[N],cnt;
inline void Add_(int a,int b,int c){
  to[++cnt]=b,nxt[cnt]=h[a],h[a]=cnt,w[cnt]=c;
} 
inline bool che(int x,int y){
  return deg[x]==deg[y]?x<y:deg[x]<deg[y];
}
inline bool cmp(node a,node b){
  return a.w>b.w;
}
int val[N];
inline void Main(){
  n=read();
  repn(i){
    int x=read(),y=read(),w=read();
    add_(x,y,w),add_(y,x,w);
  }
  n<<=1;
  ll ans=0;
  repn(x)sort(p[x].begin(),p[x].end(),cmp);
  repn(x){
    int sz=(int)p[x].size();
    ll sum=0;
    E(x)sum+=y.w;
    ans=max(ans,sum);
    E(x)if(che(x,y.y))Add_(x,y.y,y.w);
  }
  repn(x){
    e(x)val[y]=w[i];
    e(x){
      for(int j=h[y],z=to[j];j;j=nxt[j],z=to[j])ans=max(ans,(ll)w[j]+val[y]+val[z]);
    }
    e(x)val[y]=0;
  }
  cout <<ans<<'\n';
  repn(x)p[x].clear(),deg[x]=h[x]=0;cnt=0;
}
signed main(){
  int T=read();
  while(T--)Main();
  return 0;
}