当前位置:首页 > 算法

HDU 3639 Hawk-and-Chicken (强连通分量+树形D

题目地址:HDU3639先用强连通分量缩点,缩点之后,再重新按缩点之后的块逆序构图,每个块的值是里边缩的点的个数,那么得到选票的最大的一定是重新构图后入度为0的块,然后求出来找最大值即可。代码如下:#include...     u013013910   (2015-03-06)

Codeforces Round #177 (Div. 1) B. Polo the P

题目地址:http://codeforces.com/contest/288/problem/B首先,前面的k个与后面的n-k个是没关系的,后面的n-k个显然是(n-k)^(n-k),所以只需看前k个,而由于2-k都可以到达1,所以1放1-k都可以,所以这时只研究2-k...     u013013910   (2015-03-07)

POJ 3177 Redundant Paths (双连通)

题目地址:POJ3177找出各个双连通分量度数为1的点,然后作为叶子节点,那么ans=(叶子结点数+1)/2。需要注意的是有重边。代码如下:#include #include #include #include #include #include #include #include #inc...     u013013910   (2015-03-11)

HDU 2242 考研路茫茫——空调教室 (双连通分量+

题目地址:HDU2242先用双连通分量缩点,然后形成一棵树,然后在树上做树形DP,求出每个点的子树和。然后找最小值即可。需要注意一下重边的问题,第一次返回父节点时可以忽略,因为这是反向边,然后之后再返回的时...     u013013910   (2015-03-12)

POJ 2553 The Bottom of a Graph (强连通分量)

题目地址:POJ2553题目意思不好理解。题意是:G图中从v可达的所有点w,也都可以达到v,这样的v称为sink。然后升序输出所有的sink。对于一个强连通分量来说,所有的点都符合这一条件,但是如果这个分量还连接其他分...     u013013910   (2015-03-12)

POJ 2186 Popular Cows (强连通分量)

题目地址:POJ2186先用强连通分量缩点,然后形成一棵树。我第一次用的判定条件是入度为分量数-1。虽然这种情况下确实正确。但是在树中也是有间接关系的。这个条件并不是充分必要条件。正确的做法是逆序建树,然后...     u013013910   (2015-03-12)

POJ 2375 Cow Ski Area (强连通分量)

题目地址:POJ2375对每个点向与之相邻并h小于该点的点加有向边。然后强连通缩点。问题就转化成了最少加几条边使得图为强连通图,取入度为0和出度为0的点数的较大者即可。注意,当强连通分量只有一个的时候,答案...     u013013910   (2015-03-12)

POJ 3666 Making the Grade (DP+离散化)

题目地址:POJ3666dp[i][j]表示第i位时,值为j时的最小代价。因为j太大,由于要改变值的话,变到与之最近的值相同是最优的,所以可以离散化,这样,j对应了各个值得下标。复杂度O(n^2)。代码如下:#include #inclu...     u013013910   (2015-03-13)

HDU 1428 漫步校园 (BFS+优先队列+记忆化搜索)

题目地址:HDU1428先用BFS+优先队列求出所有点到机房的最短距离,然后用记忆化搜索去搜。代码如下:#include #include #include #include #include #include #include #include #include usingnamespacestd; #defi...     u013013910   (2015-03-13)

POJ 2762 Going from u to v or from v to u?(

题目地址:POJ2762先缩点,然后判断拓扑网络每层的个数是否为1(我承认如果事先不知道这题需要拓扑排序我是想不出来这点的。。。)。因为假如有一层为2的话,那么从此之后这两个岔路的点就不可能从一点到另一点的...     u013013910   (2015-03-13)

共71603条记录 5/7161页 [上一页][1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [下一页]
精彩专题
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号