首页 > 代码库 > hdu 6016

hdu 6016

2024-10-02 00:34:39   215人阅读

题意：n个公羊，m个母羊，k个朋友关系，现在你可以以任意一只羊为起点，顺着朋友关系数下去。如果能够连续数4只各不相同的羊，就能入睡，问有多少种方案入睡。

思路：k个关系，前面是公的，后面是母的，然后我们存他们的朋友关系，母羊的话就+n,然后我们从某只公羊出发，朋友有x个，那么其中一只母羊和他组成的4个则为(x-1)*(母羊的朋友个数-1)。最后结果*2

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 vector<int >a[200005];
 5 
 6 int main()
 7 {
 8     int t;
 9     int n,m,k;
10     scanf("%d",&t);
11     while(t--){
12             int x,y;
13         scanf("%d%d%d",&n,&m,&k);
14     for(int i=1;i<=n+m;i++)
15         a[i].clear();
16         for(int i=1;i<=k;i++){
17             scanf("%d%d",&x,&y);
18             a[x].push_back(y+n);
19             a[y+n].push_back(x);
20         }
21         long long sum=0;
22         for(int i=1;i<=n;i++){
23             x=a[i].size()-1;
24             for(int j=0;j<a[i].size();j++){
25                 sum+=(a[a[i][j]].size()-1)*x;
26             }
27         }
28         printf("%I64d\n",sum*2);
29     }
30     return 0;
31 }

 

hdu 6016


联系
我们