题目大意:求有向图中这种图的数量

从分层图来考虑,这是一个层数为3的图

枚举第一个点能到达的所有点,对他们进行BFS求第三层的点(假装它是BFS其实直接枚举效果一样)

代码:

 #include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define ll long long
#define M 100010
using namespace std;
struct point{
int to,next;
}e[M<<];
int n,m,num;
int head[M],vis[M];
ll ans;
void add(int from,int to)
{
e[++num].next=head[from];
e[num].to=to;
head[from]=num;
}
void bfs(int x)
{
memset(vis,,sizeof(vis));
queue<int>q;
for(int i=head[x];i;i=e[i].next) q.push(e[i].to);
while(!q.empty())
{
int p=q.front(); q.pop();
for(int i=head[p];i;i=e[i].next)
{
int to=e[i].to;
if(to!=x) vis[to]++;
}
}
for(int i=;i<=n;i++) ans+=(ll)(vis[i]-)*vis[i]/;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++)
{
int x,y; scanf("%d%d",&x,&y);
add(x,y);
}
for(int i=;i<=n;i++) bfs(i);
printf("%lld",ans);
return ;
}

最新文章

  1. 洛谷P1280 尼克的任务[DP]
  2. PVANET----Deep but Lightweight Neural Networks for Real-time Object Detection论文记录
  3. 8.2 辅助 xUtils 3.0
  4. MySQL: @variable vs. variable. Whats the difference?
  5. 第三十二课:JSDeferred的性能提速
  6. 初试Celery
  7. Yii cookie 的使用方法
  8. UITableView多选删除
  9. 用了OneAPM CT,宕机早知道!
  10. Java使用freemarker导出word和excel
  11. ThinkPHP - 模板使用函数
  12. LeetCode——Rotate List
  13. FZU 1063 三维扫描
  14. day50 盒子显隐2D形变
  15. git log命令常用参数集合
  16. windows安装Redis和客户端
  17. SSD垃圾回收
  18. Shell学习之Bash变量详解(二)
  19. 《Linux内核原理与分析》第二周作业
  20. USB集线器基础知识

热门文章

  1. IOS开发之 -- 线程初识
  2. PAT Advance 1014
  3. iOS-UIScrollView拉伸效果
  4. iOS-去除NavigationBar边线
  5. Adapter适配器 final int Id 导致选中的Item不在当前界面
  6. libevent(1)
  7. 【BZOJ5060】魔方国 特判
  8. Powershell Get File/Disk Size
  9. SQLServer中计算周
  10. ini_set(&#39;date.timezone&#39;,&#39;Asia/Shanghai&#39;);