-
[综合] poj 1947 Rebuilding Roads 树型dp
题意: 给一个有n个结点的树,要去掉一些边分离出一棵恰有p个结点的子树,求去掉的最少边数。 思路: 树型dp,dp[root][x]表示root子树得到x个结点的子树需去掉的最少边数,设点root有num个孩子,那么经过num个阶段就能确定dp[root][x]的值,dp即可,用滚动数组节省空间。 ...
52
热度 -
[综合] poj 2508 Conic distance 计算几何
题意: 求圆锥面上两点之间距离。 思路: 将圆锥展开成扇形,求两点间距离即可。 代码: //poj2508 //sepNINE #include<iostream> #include<cmath> usingnamespacestd; constdoublepi=acos(...
42
热度 -
[综合] poj 1948 Triangular Pastures 二维01背包
题意: 给n个片段,每个片段的长度为a[i],求用它们围成三角形的面积最大值。 思路: dp[k][i][j]表示前k个数能否组成长度为i和j的边,用滚动数组可以将dp数组由三维降到二维。 代码: //poj1948 //sepNINE #include<iostream> #inclu...
76
热度 -
[综合] poj 3189 Steady Cow Assignment 二分图多重匹配
题意: 有n头牛和B个栏,每头牛i对每个栏j有喜爱程度rank[i][j],每个栏i有容量cap[i],现在要把牛赶到栏里,在保证每个栏内的牛数量不超过容量的情况下,求所有牛中最大喜爱程度和最小喜爱程度差值的最小值。 思路: 枚举所有牛的最大喜爱程度high和最小喜爱程度low,对牛的集合和栏的集合...
84
热度 -
[综合] poj 2239 Selecting Courses 二分图最大匹配
题意: 裸的二分图最大匹配。 思路: 直接用匈牙利算法的模板即可。 代码: //poj2239 //sepNINE #include<iostream> usingnamespacestd; constintmaxN=302;intM,v1,v2; boolg[maxN][maxN];...
91
热度 -
[综合] poj 2536 Gopher II 二分图最大匹配
题意: 有n只鼠和m个洞,给出他们的坐标和时间速度s,v,看在s*v能走的距离内最少有多少只鼠不能进洞(每洞最多1鼠)。 思路: 裸的二分图最大匹配,直接匈牙利。 代码: //poj2536 //sepNINE #include<iostream> #include<cmath&...
63
热度 -
[综合] poj 1087 A Plug for UNIX 二分图最大匹配
题意: 给n个插座和m个设备,每个设备只能接特定的插头,另外给k个适配器,每个适配器有两个参数:插座类型和插头类型,各个适配器间可互联且适配器使用不限。求不能接通的最小设备数。 思路: 对设备器可转换矩阵用floyd算法求闭包。然后对插座集和设备集进行二分图最大匹配。 代码: #include&l...
46
热度 -
[综合] poj 2420 A Star not a Tree? 随机化变步长贪心
题意: 平面上给n个点,求一个点到所有点的距离之和最小。 思路: 随机化变步长贪心,与退火算法的区别是没有以一定的概率接受估值较差的点,因为起始点较多而且在每点都向较多方向更新,所以没必要用退火算法,直接变步长贪心就行,起始这么多点每次更新这么多次撞到一个全局最优点是概率很大的。一般的贪心常常会陷于...
93
热度 -
[综合] poj 1379 Run Away 随机化变步长贪心
题意: 给一个矩形和在其中的n个点,要求一个到所有点距离最小值最大的点。 思路: 用简化的退火算法即随机化变步长贪心方法解决,还是用了退火算法的思路。 代码: //poj1379 //sepNINE #include<iostream> #include<cmath> us...
9
热度 -
[综合] poj 2569 Etaoin Shrdlu 统计字符频率
题意: 给一个字符串,统计里面各个相邻的两个字符组成的字符串的出现频率。 思路: 水题,只是按行读入时要小心一点。用getchar()清空n后的多余空格,用fflush(stdin)会wa。 代码: //poj2569 //sepNINE #include<iostream> #inc...
59
热度 -
[综合] poj 2570 Fiber Network floyd算法
题意: 在一个有n个结点的图中,点a,b之间可以有属于不同公司的边,现在要查询对于点a,b,有哪些公司可以从属于本公司的边上从a到b。 思路: 对每个公司都建图,直接floyd。 代码: //poj2570 //sepNINE #include<iostream> usingnames...
56
热度 -
[综合] poj 3275 Ranking the Cows floyd算法
题意: 有n有牛,已经确定了m对大小关系,求还需确定多少对大小关系可以对这n头牛排序。 思路: 最后可排序时有n*(n-1)/2对关系,现在对已确定的关系用floyd求闭包得到现在可确定的关系数k,相减即为答案。 代码: //poj3275 //sepNINE #include<iostre...
82
热度 -
[综合] poj 3311 Hie with the Pie floyd+枚举排列
题意: 有0~n共n+1个点,任意两点所需时间已知,现在要从0起遍历完1~n之间的所有点再回到0点,求所需的最小时间。 思路: 先用floyd求出任意两点之间的最小时间,再枚举从0出发后的遍历顺序,取最小的时间。 代码: //poj3311 //sepNINE #include<iostre...
27
热度 -
[综合] poj 1135 Domino Effect 最短路spfa
题意: 给一个结点数为n的无向图,边x,y的值为l表示x,y之间有l张多米诺骨牌,现在推倒点1处的多米诺骨牌,每张多米诺骨牌倒下要1s,求最后一张多米诺骨牌倒下时的时间。 思路; 先求单源最短路,再枚举最后一张到的位置,注意要枚举倒在两点之间的情况。 代码: //poj1135 //sepNINE...
52
热度 -
[综合] poj 2267 From Dusk till Dawn or: Vladimir the Vampire 最短路spfa
题意: 有n个城市,城市之间有m列火车,每列火车都有发车时间和行驶时间。吸血鬼先生要乘火车从a到b,可以经过一些中间车站。但是他只能在晚上6点到次日凌晨6点之间在火车上而且他中午12点要和1L血,现在问最少要多少L血。 思路: 以用的血为消耗用spfa求最短路。 代码: //poj2267 //se...
32
热度 -
[综合] poj 1569 Myacm Triangles 判断点在三角形内+求三角形面积
题意: 给平面上的n个点,求中间没有其他点面积最大的三角形。 思路: 枚举三角形的三个顶点,判断点是否在三角形内再求三角形面积。 代码: //poj1569 //sepNINE #include<iostream> #include<cmath> usingnamespac...
28
热度 -
[综合] poj 3191 The Moronic Cowmpouter 十进制转-2进制
题意: 给一个10进制的数。把他转化为-2进制。 思路: 水题,直接边除边模即可。 代码: #include<iostream> usingnamespacestd; inta[64]; intmain() {intcnt=0,n;scanf("%d",&n); while(n...
62
热度 -
[综合] poj 3352 Road Construction 边双连通分量
题意: 给一个有桥的非边双连通无向图(当然也就是非点双连通图了),求最少加多少条边让它变成边双连通的。 思路; 网上很多解题报告不区分点双连通和边双连通。。。这题求的是边双连通分量。求出各个边双连通分量后缩点得一棵树,把树的叶节点按离最近公共祖先距离和由长到段两两配对相连就可以了,答案为(leaf+...
65
热度 -
[综合] poj 3177 Redundant Paths 边双连通分量
题意: 跟poj3352一样,给一个有桥的无向图,求最少加多少条边后能变为边双连通的。 思路: 求边双连通分量,缩点后得到一颗树,求得树叶树leaf后答案为(leaf+1)/2。 代码: //poj3177 //sepNINE #include<iostream> #include&l...
58
热度 -
[综合] poj 3662 Telephone Lines spfa算法的灵活运用
题意: 给一个有n个结点的无向图,要求一条从1到n的路径,你可以让其中的k条免费,这条路径的花费是这条路径上剩下的边中长度的最大值,现在要求花费的最小值。 思路: 这道题可以首先想到二分枚举路径上的最大值,我觉得用spfa更简洁一些。spfa的本质是一种搜索算法,既然是搜索,就涉及到状态的转移。在一...
90
热度