首页 > 代码库 > hdu 6016

hdu 6016

题意: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