2020-2021:teams:legal_string:jxm2001:三元环计数
| 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:jxm2001:三元环计数 [2021/03/02 15:48] jxm2001 创建 |
2020-2021:teams:legal_string:jxm2001:三元环计数 [2021/05/26 14:16] (当前版本) jxm2001 |
||
|---|---|---|---|
| 行 9: | 行 9: | ||
| === 题意 === | === 题意 === | ||
| - | 给定 $n$ 个点和 $m$ 条边的无向图。定义三元环为满足 $(u,v,w)$ 两两之间有连边的点对数，求图中的三元环数。 | + | 给定 $n$ 个点和 $m$ 条边的无向图。定义三元环为满足所有点两两之间有连边的三元组数，求图中的三元环数。 |
| === 题解 === | === 题解 === | ||
| 行 71: | 行 71: | ||
| </hidden> | </hidden> | ||
| + | ==== 例题二 ==== | ||
| + | |||
| + | [[http://acm.hdu.edu.cn/showproblem.php?pid=6184|HDU6184]] | ||
| + | |||
| + | === 题意 === | ||
| + | |||
| + | 给定 $n$ 个点和 $m$ 条边的无向图。定义好的四元组 $(A,B,C,D)$ 为满足存在连边 $AB,BC,CD,DA,AC$ 的四元组，求图中好的四元组数。 | ||
| + | |||
| + | === 题解 === | ||
| + | |||
| + | 统计每条边出现在三元组中的次数 $c_i$，最终答案为 $\sum_{i=1}^n {c_i\choose 2}$ | ||
| + | |||
| + | <hidden 查看代码> | ||
| + | <code cpp> | ||
| + | const int MAXN=1e5+5,MAXM=2e5+5; | ||
| + | struct Edge{ | ||
| + | int to,next,c; | ||
| + | }edge[MAXM]; | ||
| + | int head[MAXN],edge_cnt; | ||
| + | void Insert(int u,int v){ | ||
| + | edge[++edge_cnt]=Edge{v,head[u],0}; | ||
| + | head[u]=edge_cnt; | ||
| + | } | ||
| + | int deg[MAXN],vis[MAXN],in[MAXN]; | ||
| + | pair<int,int> E[MAXM]; | ||
| + | int main() | ||
| + | { | ||
| + | int n,m; | ||
| + | while(cin>>n>>m){ | ||
| + | _rep(i,1,n)head[i]=deg[i]=vis[i]=in[i]=0; | ||
| + | edge_cnt=0; | ||
| + | _for(i,0,m){ | ||
| + | int u=read_int(),v=read_int(); | ||
| + | deg[u]++,deg[v]++; | ||
| + | E[i]=make_pair(u,v); | ||
| + | } | ||
| + | _for(i,0,m){ | ||
| + | int u=E[i].first,v=E[i].second; | ||
| + | if(deg[u]<deg[v]||(deg[u]==deg[v]&&u<v)) | ||
| + | Insert(u,v); | ||
| + | else | ||
| + | Insert(v,u); | ||
| + | } | ||
| + | _rep(u,1,n){ | ||
| + | for(int i=head[u];i;i=edge[i].next){ | ||
| + | int w=edge[i].to; | ||
| + | vis[w]=u,in[w]=i; | ||
| + | } | ||
| + | for(int i=head[u];i;i=edge[i].next){ | ||
| + | int v=edge[i].to; | ||
| + | for(int j=head[v];j;j=edge[j].next){ | ||
| + | int w=edge[j].to; | ||
| + | if(vis[w]==u) | ||
| + | edge[i].c++,edge[j].c++,edge[in[w]].c++; | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | LL ans=0; | ||
| + | _rep(i,1,m) | ||
| + | ans+=1LL*edge[i].c*(edge[i].c-1)/2; | ||
| + | enter(ans); | ||
| + | } | ||
| + | return 0; | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
2020-2021/teams/legal_string/jxm2001/三元环计数.1614671297.txt.gz · 最后更改: 2021/03/02 15:48 由 jxm2001
