爱笑黑裤

文章
5
资源
0
加入时间
3年2月3天

hdu5305and杭电多校集训第二题(1006题 friend)

题目大意:有n个人,m个关系,其中关系有两种,问你能找到多少种方式,使得每个人的两种关系都相等。解题思路:图的边的枚举+剪枝+回朔,n个人看做n个点,m个关系看成m条边,两种关系看做两种其他度,边的枚举(用递归来枚举,一开始我用二进制,果断TLE),剪枝的话,是每次枚举一条边,就有两个点的度数+1,统计下当前的其他度数,不能超过它本身的度数(这个就是图论里的度数)的一半,超过一半return

P1144 最短路计数P1144 最短路计数

关于dijkstraP1144 最短路计数原题链接:传送门思路:简单的dij计数,基本思想是dij中的松弛操作,这里假设d[]为距离,s[]为最短路路径数。if d[v]>d[u]+w ,则 s[v] =s[u]; 如果最短路得到更新,则用s[u]的路径更新s[v];if d[v]=d[u]+w , 则 s[v]+=s[u]; 如果同样是最短路,则s[v]的最短路数加上s[...