首页 > 代码库 > HDU 6016 - Count the Sheep
HDU 6016 - Count the Sheep
题意:
男羊和女羊之间有朋友关系，找出关系满足A->B->C->D,且A,B,C,D都不同的关系的个数（排列）
分析：
枚举B，对于每一个B枚举C
每一个B->C的贡献 = (B.size - 1) * (C.size - 1)
1 #include <bits/stdc++.h> 2 using namespace std; 3 #define LL long long 4 const int MAXN = 100005; 5 int t, n, m, k; 6 int C[MAXN];//女羊的朋友 7 vector<int> G[MAXN]; //男羊->女羊 8 int main() 9 {10 scanf("%d", &t);11 while (t--)12 {13 memset(C, 0, sizeof(C));14 scanf("%d%d%d", &n, &m, &k);15 for (int i = 1; i <= n; i++) G[i].clear();16 memset(C, 0, sizeof(C));17 for (int i = 1; i <= k; i++)18 {19 int x, y; scanf("%d%d", &x, &y);20 C[y]++;21 G[x].push_back(y);22 }23 LL ans = 0;24 for (int x = 1; x <= n; x++)25 {26 LL A = G[x].size()-1;27 for (int j = 0; j < G[x].size(); j++)28 ans += A*(C[G[x][j]]-1);29 }30 printf("%lld\n", 2*ans);31 }32 }
HDU 6016 - Count the Sheep
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。