题意：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 }
原文：http://www.cnblogs.com/hhxj/p/6953515.html