题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6016
题意：给定男羊和女羊的朋友关系，即给定一个图，问从任意一只羊开始连续数四只不相同的羊的方法数。
思路：一开始用了dfs没过，报的超时，以为真的会超时，最后发现，犯了个以前常犯的老问题，存边的vector开小了，，这道题需要开
(n+m)的vector。
后来又按官方题解做了一遍，官方题解，也就需要脑袋转一下。要找序列：男--女--男--女，或者 女--男--女--男；那么只需要找其中一种，即只找 女(1)--男(2)--女(3)--男(4) 的种数，答案为ans*2。枚举(2)号男羊和与(2)号男羊之间有边的一只(3)号女羊，即可确定
一类序列的种数，ans+=(sheep[i]-1)*(sheep[j]-1) i与j之间有边。
dfs：
#include<iostream> #include<cstdio> #include<cstring> #include<vector> using namespace std; #define N 100005 vector<int> sheep[2*N]; int main() { int t; scanf("%d",&t); while(t--) { int n,m,k; scanf("%d%d%d",&n,&m,&k); for(int i=1;i<=n+m;i++) sheep[i].clear(); for(int i=0;i<k;i++) { int a,b; scanf("%d%d",&a,&b); sheep[a].push_back(b+n); sheep[b+n].push_back(a); } long long ans=0; for(int i=1;i<=n;i++) { int way=sheep[i].size()-1; for(int j=0;j<sheep[i].size();j++) { ans+=(sheep[sheep[i][j]].size()-1)*way; } } printf("%I64d ",ans*2); } return 0; }
官方做法：
#include<iostream> #include<cstdio> #include<cstring> #include<vector> using namespace std; #define N 100005 vector<int> sheep[4*N]; int main() { int t; scanf("%d",&t); while(t--) { int n,m,k; scanf("%d%d%d",&n,&m,&k); for(int i=1;i<=n+m;i++) sheep[i].clear(); for(int i=0;i<k;i++) { int a,b; scanf("%d%d",&a,&b); sheep[a].push_back(b+n); sheep[b+n].push_back(a); } long long ans=0; for(int i=1;i<=n;i++) { int way=sheep[i].size()-1; for(int j=0;j<sheep[i].size();j++) { ans+=(sheep[sheep[i][j]].size()-1)*way; } } printf("%I64d ",ans*2); } return 0; }