首页 > 其他分享 >ACM预备队-3月集训

ACM预备队-3月集训

时间:2023-03-15 22:24:01浏览次数:50  
标签:10 idx int res ACM 预备队 ++ add 集训

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

相关文章

  • 2023.3.15蓝桥杯集训·每日一题
    AcWing200.Hankson的趣味题题目描述Hanks博士是BT(Bio-Tech,生物技术)领域的知名专家,他的儿子名叫Hankson。现在,刚刚放学回家的Hankson正在思考一个有趣的问题。今天......
  • 2023武汉多校集训总结
    一共考了5场试,讲了3次课。中间时间学习了回滚莫队和带修改莫队,CDQ分治。CDQ分治是一种思想,作用是在复杂的点对关系(一般是多个参数的关系),优化一种关系。集训难度很大,主要......
  • 【题解】P6667 [清华集训2016] 如何优雅地求和
    orzfjy666orzfjy666orzfjy666神·fjy666·拉普拉斯·爱因斯坦大帝于5min内爆切了此题,膜拜!思路斯特林数。注意到\(f(k)\)是多项式而式子中含有组合数,于......
  • 2021 牛客 OI 赛前集训营-提高组(第二场)
    A.串串串【题目描述】你有两个长度分别为\(n,m\)的\(01\)串\(\text{S,T}\)。有\(\textQ\)次询问,每次询问给出\(l_1,r_1,l_2,r_2\),其中\(r_1−l_1+1......
  • 海亮省选集训游记
    title:海亮省选集训游记categories:[游记]date:2023-03-06更好的阅读体验海亮省选集训游记Day0昨天刚考完春季测试,今天就要run去海亮了。上午9:30的火车,坐......
  • UVA11613 Acme Corporation
    UVA11613AcmeCorporation题意翻译已经很清楚了。思路看到这种求限制下的最值的问题,而且数据范围还比较小,我们不难想到费用流。但是这道题要求的是最大利润,那么我们可......
  • 【补题】2022-2023 ACM-ICPC German Collegiate Programming Contest (GCPC 2022)
    题目链接https://codeforces.com/gym/104059A.AlternativeArchitecture思路简单题,但要注意细节。给的方格很干扰思考,事实上注意到顶点指的是四个角上的圆圈,我们将长......
  • 武汉集训
    Day1没什么感觉便到了武汉,这里似乎和成都也没什么不同,下榻的酒店周围非常奇妙,明明是城乡结合部却异常繁华。开摆!Day2记忆文件缺失.jpgDay3昨天晚上睡得比较晚,今天好......
  • 寒假集训——基础数论6 线性代数
    矩阵定义简单来说矩阵就是一个\(n\)行\(r\)列的阵,实在不行可以理解成一个二维数组\[%开始数学环境\left[%左括号\begin{array}{ccc}......
  • Java for ACM
    importjava.io.*;importjava.util.*;publicclassMain{staticBufferedReaderInput=newBufferedReader(newInputStreamReader(System.in));staticP......