当前位置: 代码迷 >> 综合
 解决方案列表
  • [综合] poj 1144 Network 无向图求割点

    题意: 给一个有n个结点的连通无向图,求它的割点个数。 思路: 裸求割点,直接上模板,这个模板是从一本书上找的,很简洁。 代码: //poj1144 #include<iostream> usingnamespacestd; constintmaxN=128; intg[maxN][m...

    33
    热度
  • [综合] poj 3694 Network 无向图求桥

    题意: 给一个无向图,有q次插入操作,每次加入一条边,求每次插入后图中的桥有多少。 思路: 缩点成一棵树后每次插入操作都查询一次LCA,沿路更新整个图中的桥数ans。 //poj3694 //sepNINE #include<iostream> #include<stack>...

    86
    热度
  • [综合] poj 3160 Father Christmas flymouse 强连通分量

    题意: 给一个有n个节点的有向图,每个节点有一个值,现在要在图中遍历一次,遍历到一个点可以取走该点的值,现在求在一次遍历中能取到的最大和。 思路: 用tarjan算法缩点后直接搜索最大值。 代码: //poj3160 //sepNINE #include<iostream> #incl...

    31
    热度
  • [综合] poj 1904 King's Quest 强连通分量

    题意: 有n男n女,每个男的可能喜欢多个女的,男的只能跟自己喜欢的人结婚,现在对每个男的要求一个女子集合,使当他跟其中任何女的结婚后其他的n-1个男的都还有喜欢的女孩可以结婚。输入还给出一组可行的结婚方案。 思路:经典构图题,把输入给的结婚方案中的n对男女看做n个顶点,如果i对中的男喜欢j对中的女则...

    90
    热度
  • [综合] poj Knights of the Round Table 点双连通分量

    题意: 有n个骑士,要去参加人数为奇数且大于1的圆桌会议,有的骑士不能坐在一起,现在要处死一些骑士,使得剩下的骑士都有圆桌会议可以参加,注意不是要剩下的骑士一起去开会,只要有能参加会议的可能就好。 分析: 求补图后每条边连的是可以参加会议的骑士。对补图求点双连通分量,求的的每个点双连通分量中都没有割...

    64
    热度
  • [综合] poj 1759 Garland 二分搜索

    题意: 有n个灯泡,给出第一个灯泡的高度h1和n,求第n个灯泡hn的最小值。所有灯泡满足Hi=(Hi-1+Hi+1)/2-1,forall1<i<N,Hi>=0,forall1<=i<=N。 分析: 所求hn与h2有单调关系,直接二分枚举h2。 代码: //poj17...

    84
    热度
  • [综合] poj 3279 Fliptile 枚举子集

    题意: 给一个01矩阵,求它经过最少多少次翻转能得到全0矩阵,翻转(i,j)后(i,j)四周的点也会被翻转。 分析: 因为第一行的翻转情况确定后为达到目标矩阵之后各行的翻转情况就确定了,所以枚举第一行的m个点的所有子集进行翻转,求可以达到目标矩阵的最小翻转数。 代码: //poj3279 //se...

    16
    热度
  • [综合] poj 1734 Sightseeing trip 扩展floyd求最小环

    题意: 有一个无向图内的最小环。 思路: 求最小环的模板题。 代码: #include<iostream> usingnamespacestd; constintmaxN=128; intg[maxN][maxN]; intdirectConnect[maxN][maxN]; intp...

    53
    热度
  • [综合] poj 3512 Incidental Points 计算几何

    题意: 给n个点,判断其中最多有多少个点共线。 分析: n<=1000,n^3的算法会TLE。将所有点按y从小到大排序,若y相同按x排序,这样每次确定跟点i最多有多少点共线就只需看要下标比i大的点了。对于每个点i,将下标比i大的点按与i成的角度排序,这样所有与i共线的点必然在新排序中相邻,遍历...

    80
    热度
  • [综合] poj 3653 Here We Go(relians) Again 最短路

    题意: 给一个城市网络,有n*m个街区组成,每条路所花时间易求,要算从城市左上角到右下叫的最短时间。 分析: 简单最短路,只是输入有点恶心。 代码: //poj3653 //sepNINE #include<iostream> #include<queue> usingna...

    83
    热度
  • [综合] poj 1639 Picnic Planning 单度限制的最小生成树

    题意: 给一个无向图连通图,求它的最小生成树,生成树满足条件点v0的度小于等于limit。 分析: 一般有度限制的最小生成树问题是np完全的,但单点度限制就比较简单了,先在原图上求不含v0的最小生成森林,然后再将森林中每一棵树选一条最短的边连到v0上,设最小生成森林中有k0棵树,如果k0>li...

    94
    热度
  • [综合] poj 2973 无序字符串含通配符的匹配

    题意: 求两个无序字符串含通配符的匹配。 分析: 直接统计字符频率即可。 代码: //poj2973 //sepNINE #include<iostream> #include<map> #include<string> usingnamespacestd; s...

    34
    热度
  • [综合] poj 1486 Sorting Slides 二分匹配唯一性判定

    题意: 在平面给n个矩形和n个点,问有哪些矩形和哪些点可以唯一匹配。 思路: 用匈牙利算法做唯一性判定,设在一次最大匹配M后A匹配到4,即match(A)=4,那么A能和4不是唯一匹配的条件是将g[A][4]删除后求得最大匹配M‘==M&&match[A]!=0。 代码: //po...

    61
    热度
  • [综合] poj 3613 Cow Relays 经L边的最短路

    题意: 求无向图s,t点间经过L条边的最短路。 思路: 矩阵连乘求图中任意两点间的最短路不经常用,因为复杂度是N^3logN的,但这种算法对最短路径经过的路径数的描述却非常清晰,尤其当需经过路径L比较大而顶点数N比较小的时候,N^3logL就比较可观了,求最短路径的特殊矩阵乘法满足结合律,可以幂乘加...

    1
    热度
  • [综合] poj 1692 Crossed Matchings 动态规划

    题意: 给两行数,第一行的数与第二行的数如果相同可以连线,每个数字只能连一次线,且每条连线必须与另外一条数字不同的线相交,求最多能连多少条线。 思路: 动态规划,状态dp[i][j]:第一行数的前i个数能和第二行数的前j个数的最多连线次数。转移:dp[i][j]=max{dp[i-1][j],dp[...

    84
    热度
  • [综合] poj 2704 Pascal's Travels 动态规划

    题意: 给一个n*n的矩阵,矩阵里的数表示在这个点能走的距离长度,只能向右走或者向下走,求从左上角到右下角一共有多少种走法。 分析: 简单dp,状态O(n^2):dp[i][j]表示到(i,j)有多少种走法;转移O(1):dp[i][j]=sum{dp[i][j-k]}(g[i][j-k]==k,1...

    27
    热度
  • [综合] poj 2738 Two Ends 区间dp

    题意: 给一列数a[1...n],A和B轮流从其中剩余两端取一个数,B只能取两端数最大的,取完后比较谁的和大,问A最多可以比B多多少。 分析: 区间动态规划,状态dp[i][j]:A能从第i到第j个数中获得的最大和。转移:根据当前区间长度分奇偶考虑,详见代码。 代码: //poj2738 //se...

    0
    热度
  • [综合] poj 3604 Professor Ben 组合计数

    题意: 给一个数n,设它有因子a1,a2,a3..am,每个因子a[i]的因子个数为bi,求sum(b1^3+b2^3+...b^m)。 思路: 用到两个公式sum(1^3+2^3...k^3)==(k*(k+1)/2)^2,设n=x1^y1*x2^y2...xt^yt,那么n的因子个数(y1+1)...

    14
    热度
  • [综合] poj 3411 Paid Roads dfs+状态压缩

    题意: 求点1到点n的最短路,每条路可能有两种权值,如果之前访问过某个点c则权值为p,否则为r。 思路: 将之前访问过的点序列状态压缩+深搜。其实也可以不用状态压缩,当判断是否访问过c时判断cnt[c]>0就可以了。 代码: //poj3411 //sepNINE #include<i...

    43
    热度
  • [综合] poj 2460 Brownie Points I 坐标判断

    题意: 给n个点,判断他们相对于第n/2+1个点的位置关系。 分析: 水题,太水。 代码: //poj2460 //sepNINE #include<iostream> usingnamespacestd; constintmaxN=200024; intx[maxN],y[maxN]...

    45
    热度