首页 > 代码库 > CF489_D_剪枝
CF489_D_剪枝
题目链接：http://codeforces.com/problemset/problem/489/D
题意：给你一个图 让你求里面菱形的个数，菱形如下图
思路：类似于floyd，枚举点a和点c。
注意：题目里面点的个数为3000，边的个数为30000，做一个剪枝，复杂度为O(nm+(n-√m)n)。
好吧，我还是不会算复杂度。。。明天写一下vector。。。待更新~~~
#include<cstdio>#include<iostream>#include<cstring>#include<cstdlib>#include<algorithm>using namespace std;const int maxn = 3000+10;int map[maxn][maxn];__int64 map_[maxn][maxn];int main() { //freopen("test.txt", "r", stdin); int n, m; while(scanf("%d%d", &n, &m)!=EOF) { int u, v; __int64 ans = 0; memset(map, 0, sizeof(map)); memset(map_, 0, sizeof(map_)); for(int i=1; i<=m; i++) { scanf("%d %d", &u, &v); map[u][v]++; } for(int k=1; k<=n; k++) { for(int i=1; i<=n; i++) { if(map[i][k]==0) continue; for(int j=1; j<=n; j++) { if(map[i][k] && map[k][j] && i!=j) map_[i][j]++; } } } for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) { ans += map_[i][j]*(map_[i][j]-1)/2; } } printf("%I64d\n", ans); } return 0;}
CF489_D_剪枝
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。