1.P8605 [蓝桥杯 2013 国 AC] 网络寻路
题目链接:P8605 [蓝桥杯 2013 国 AC] 网络寻路 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
分析:我们的做法是记录所有点的度,然后枚举一个点所有相连接的点,他们之间的合法路径的总条数为:
(d[i]-1)*(d[j]-1),减1是因为减掉了两个点之间相连的边。
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int N=1e4+10; 4 const int M=2e5+10; 5 int e[M],ne[M],h[N],idx; 6 int n,m,d[N],ans; 7 void add(int a,int b) 8 { 9 e[idx]=b,ne[idx]=h[a],h[a]=idx++; 10 } 11 int dfs(int u) 12 { 13 int res=0; 14 for(int i=h[u];i!=-1;i=ne[i]) 15 { 16 int j=e[i]; 17 if(j>u)//防止重复来回搜索,必须要确定一个大小关系 18 { 19 res+=(d[u]-1)*(d[j]-1); 20 } 21 } 22 return res; 23 } 24 signed main() 25 { 26 ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); 27 memset(h,-1,sizeof h); 28 cin>>n>>m; 29 int a,b; 30 for(int i=0;i<m;i++) 31 { 32 cin>>a>>b; 33 d[a]++,d[b]++; 34 add(a,b),add(b,a); 35 } 36 for(int i=1;i<=n;i++) 37 { 38 ans+=dfs(i); 39 } 40 ans=ans*2; 41 cout<<ans<<endl; 42 return 0; 43 }
标签:10,idx,int,res,ACM,预备队,++,add,集训 From: https://www.cnblogs.com/Zac-saodiseng/p/17220415.html