首页 > 代码库 > bzoj3498: PA2009 Cakes
bzoj3498: PA2009 Cakes
Description
N个点m条边，每个点有一个点权a。
对于任意一个三元环(j，j，k)（i<j<k），它的贡献
为max(ai，aj，ak)
求所有三元环的贡献和。
N<100000，，m<250000。
对度数大的点w，枚举w相邻的每个点u1,u2,u3...，遍历u[a]相邻的点的统计w,u[a],u[b](b<a)构成三元环的情况
对度数小的点w，枚举w相邻的每个点，在另外存边的散列表中 判断它们两两之间是否有边
每个三元环恰好统计三次，两种策略时间复杂度在判断标准为$\sqrt{m}$时达到平衡
#include<cstdio>#include<vector>const int RN=1e5;char buf[RN+7],*ptr=buf+RN;int G(){ if(ptr==buf+RN)fread(ptr=buf,1,RN,stdin); return *ptr++;}int _(){ int x=0; if(ptr<buf+RN-50){ while(*ptr<48)++ptr; while(*ptr>47)x=x*10+*ptr++-48; }else{ int c=G(); while(c<48)c=G(); while(c>47)x=x*10+c-48,c=G(); } return x;}const int P=1844677,N=1e5+7,D=333;int n,m,a[N],ed[N],e[N*3][2],deg[N],*lr[N][2],mem[N*5],*mp=mem;int max(int a,int b){return a>b?a:b;}long long ans=0;int h[P][2];void ins(int a,int b){ int w=(a*1399+b*2939)%P; while(h[w][0]){ if(h[w][0]==a&&h[w][1]==b)return; w=(w+21331)%P; } h[w][0]=a,h[w][1]=b;}bool find(int a,int b){ int w=(a*1399+b*2939)%P; while(h[w][0]){ if(h[w][0]==a&&h[w][1]==b)return 1; w=(w+21331)%P; } return 0;}int main(){ n=_(),m=_(); for(int i=1;i<=n;++i)a[i]=_(); for(int i=1;i<=m;++i){ ++deg[e[i][0]=_()]; ++deg[e[i][1]=_()]; } for(int i=1;i<=n;++i)lr[i][0]=lr[i][1]=mp,mp+=deg[i]; for(int i=1;i<=m;++i){ int a=e[i][0],b=e[i][1]; *lr[a][1]++=b; *lr[b][1]++=a; ins(a,b); ins(b,a); } for(int i=1;i<=n;++i)if(deg[i]>D){ for(int*j=lr[i][0];j!=lr[i][1];++j){ int w=*j,mx=max(a[i],a[w]); ed[w]=i; for(int*k=lr[w][0];k!=lr[w][1];++k)if(ed[*k]==i)ans+=max(mx,a[*k]); } }else{ for(int*j=lr[i][0];j!=lr[i][1];++j){ int w=*j,mx=max(a[i],a[w]); for(int*k=lr[i][0];k!=j;++k)if(find(w,*k))ans+=max(mx,a[*k]); } } printf("%lld\n",ans/3); return 0;}
bzoj3498: PA2009 Cakes
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。