bzoj 5407 girls

bzoj 5407 girls

​​ Description

lydsy.com/JudgeOnline/upload/5407.pdf

Input

Output

Sample Input

Sample Output

HINT

注意题面中x,y,z满足x< y < z!

Source

一道枚举三元环的题 坑了我很久

考虑说不存在的情况

那么我们不妨算出所有的方案数 - 至少包含一个敌对关系的+至少包含两对敌对关系-三对敌对关系

第一个可以考虑枚举每个人 然后算贡献 那么贡献就是 其他两个人任选的方案

至少包含一对敌对关系我们可以枚举到底是哪两个人包含了敌对关系预处理sa,sb,sc分别表示

前i号人选a,b,c的价值前缀和

至少包含两对敌对关系 我们可以考虑枚举 每个点关联的所有边 然后计算贡献

包含三对敌对关系的问题我们可以考虑 针对无向边 重新定向 从度数小的向大的连边 然后每次暴力枚举 每条边 然后再枚举他连向的那条边 再通过那条边枚举 可以保证复杂度不超过m*sqrt(m)

#include#define ll unsigned long longusing namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while(!isdigit(ch)) {if (ch=='-') f=-1;ch=gc();} while(isdigit(ch)) {x=x*10+ch-'0',ch=gc();} return x*f;}const int N=2e5+10;ll A,B,C,sa[N],sb[N],sc[N],ans;int n,d[N],m,id[N];vector eg[N];struct node{ int y,next;}data[N];int h[N],num,fr[N],to[N],vis[N];inline bool cmp(const int &a,const int &b){ return d[a]y) swap(x,y);insert1(x,y);continue; } if(d[x]>d[y]) swap(x,y); insert1(x,y); }int bl[3]; for (int i=1;i<=m;++i){ int x=fr[i],y=to[i]; for (int j=h[x];j;j=data[j].next) vis[data[j].y]=i; for (int j=h[y];j;j=data[j].next){ int to=data[j].y; if(vis[to]==i){ bl[0]=x;bl[1]=y;bl[2]=to;sort(bl,bl+3); ans-=A*(bl[0]-1)+B*(bl[1]-1)+C*(bl[2]-1); } } } printf("%llu\n",ans); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。