[综合] ZOJ 2760 最短路径条数问题

虽然以前做过最短路径的条数问题，但这个问题有点奇葩，在最短路径数量中，路径不能重复使用==.... 如果可以重复使用还是很简单的，用dij去推就好了。将起点赋值为1，向相邻的边推自己，如果0->1有两条边同样短，那么..0->1就推两次，所以0->1就有两种走法。 这题不同，路径不...

[综合] POJ 2391 floyd+二分+最大流

思路构图还是十分的好想的...比较的有经验了。对这题，没啥难度了。 题目大意: FJ有很多田地，一些田地有雨棚，雨棚有容纳牛的容量，现在给你田中的牛和田里的雨棚的容纳量，还有田间路径走完花费的时间。 要求出使得所有牛都躲进雨棚里的最小时间。 构图还是很简单的： 将牛棚拆点为in和out点。 源点到i...

[综合] POJ 2299 树状数组+离散化

上课前看了下题，上课时构了下思，下课敲了10min...交了就A了...好吧..这题弱爆了！ 题目大意： 求一个数列中的逆序数.... 这题可以用坐标离散化。然后...从大的数向树状数组更新..查的时候求和，把这个数前面的大的数求出来就OK了。 水爆了...1Y #include<iostr...

[综合] HDU 4217 树状数组+二分查找

比赛中做出这题来让我开心了好久啊~哈哈~温习了一下树状数组。 开始惊奇和雄爷爷和我说树状数组没有这个性质，我不信。后来码畜来之后，才发现，确实树状数组确实没有这么个性质。 于是开始用vector做==TLE....还好想出了二分这个好办法...1234msAC了...嘿嘿... 其实我还是挺膜拜那些...

[综合] POJ 2352 树状数组

这是一道YY题==... 确实..做这题我就是YY出来的。一交没想到1Y了~哈哈哈~笑死我了~ 树状数组再练一道就罢手！ #include<iostream> #include<algorithm> #include<cstdio> usingnamespace...

[综合] POJ 1966 最大流最小割...

最近写的代码都挺长的啊... 下面说一下最小割吧。 以下内容引自：这里 首先介绍一个概念： 点连通度：一个具有N个顶点的图G，去除K个顶点后，图成为非连通图，去除任意K-1个顶点后，图仍为连通图。责成图G为K连通图。 独立轨：A,B是图G中两个顶点，从A至B的无公共内顶点的路径叫做独立轨，其最大条数...

[综合] CSUOJ 1165 枚举

题目 其实这题水题本来不打算写的，晚上看了下题解，发现和我那时TLEN久的代码是一样的。 后来才发现我把最小值ans初始化: longlongans=(longlong)1<<60; intindex=0;这样的最小值不够大，导致后面的数乘起来比这个最小值还要大，导致了没有更新inde...

[综合] FZU 2080 二维单调队列

hev神让我做做这题... 大概我们可以用一个二维的单调队列来写的。 用两个矩阵来记录大矩阵的部分最值。 例如用A[i][j]来记录mat[i][j]---mat[i+r-1][j]这一列的最小值，用Mi[i][j]来记录A[i][j]--A[i][j+c-1]这一行的最小值，于是乎Mi[i][j]...

[综合] POJ 3308 最小割最优点权覆盖

题目大意： 火星人入侵地球，他们降落的区域为一个n*m的矩形兵工厂，在这个区域行顶点和列顶点处有激光束，激光束一次能消灭一排或一列的敌人。为了消灭所有入侵的火星人，求最小的花费。每安装一个激光束都有一个权值，花费所有激光束权值的积。 思路： 如果不考虑到点权值，如POJ3041，每个点权值都为1,也...

[综合] POJ 2125 最小割最小点权覆盖

做这题还是看了Amber大神的论文... 还是在这里冗余一下吧： 点覆盖集：无向图G的一个点集，使得该图中所以边都至少有一个端点在该集合内。形式化的定时意思点覆盖集为V'∈V，满足对于所有的(u,v)∈E,都有u属于V'或v属于V'成立，即至少一个成立。形象的说是若干点“覆盖”住了与他们邻接的边。这...

[综合] POJ 3469 构图最小割+链表SAP

题目大意： 有一台双核处理器的电脑，现有很多模块，每个模块放在不同的核中都有一个花销。若某两个模块不放在同一个核中执行，那么会产生额外的花销。求出使得所有的模块都进入处理器中的总花销值最小。 首先可以明确的是，该题为二分图，模块放入两个核中。 如果没有惩罚。 那么该题就是赤裸裸的最小割（其实是贪心）...

[综合] POJ 2987 最大流最小割最大权闭合图

基本的最小割问题做得也差不多了.... 这题整死我了.... 在Amber的论文里有这个解法，大家去看看吧。 其他的不说了。 这题把数据类型全都改成longlong才过，瞪大眼睛找了一晚上，没找出trick....悲催.... 如果你也WA了，不妨试试这种方法...PS：我连bool都改longlo...

[综合] POJ 3084 最大流最小割求割边

这种题目做过蛮多道了，主要是再练习一下我的网络流链表写法。 这题坑爹的理解错题意了，弄了很久。 题意： 有M个房间，现在要保护N号房间，房间编号为[0,M-1]。起初所有的房间的门都是打开的，房间内有关门的控制面板，也就是说，如果该房间能控制几个相应的门，则从该房间可以通过这些门去往其他房间。如果控...

[综合] POJ 3204 求使得最大流增大的边

这题还是有点技巧的。 我们求出了最大流，怎样知道哪些边可以使得流量增大呢？ 若存在e(U,V):S->U路径上的点都有剩余容量，V->T路径上的点都有剩余容量。 如果有某条边为上述情况，那么对边e进行扩容，最大流增大。 应该十分好理解吧。通过源点进行DFS寻找S集合中所有的点进行标号，...

[综合] POJ 1719 有意思的水题[二分图多重匹配]

题目大意： 有一个R*C（R<=C）的棋盘，由黑白两色格子组成，每列只有两个白色格子，其余为黑色。 现在求：在每列恰巧取一个，每行最少取一个的取法，按列的顺序由小到大输出取出棋子所在的行。 我的思路： 由于每行最少取一个，可以先把行的最大二分图匹配做出来，如果行都不能满足，肯定是无解的。 若行...

[综合] FZU 2087 统计树边

[题目大意] 给定一个无向图，求出这些边(至少出现在一棵生成树中的边)的数目。 [解题思路] 理解MST的思想，将贪心思想运用。 由小到大遍历这些边，权值相同的为一组。 先判断这些边是否能够成为树边，再对这些边进行合并。 [注意事项] 不知道为何，以前一直写的模板不顶用了... 一定要改成比较丑的样...

[综合] FZU 2090 无向图最小环 floyd

【题目大意】 给定一个无向图，求出图中的最小环。并输出最小环的个数。 【解题思路】 1.朴素算法。 对于边e(u,v)，除掉e之后的最短路径mind(u,v)，那么最小环则为mind(u,v)+e(u,v); 2.<图论中的圈与块> 一个环中的最大结点为k(编号最大)，与他相连的两个点为...

[综合] FZU 1481 KMP

【题目大意】 判断两条环形字符串是否相同。 【思路】 将待匹配串复制一份接在后面，再用模式串做KMP，若能找到说明为同一个串。 蛮久没写KMP了，算法忘得差不多了.. 小悲剧啊~ 【CODE】 #include<iostream> #include<cstdio> usin...

[综合] [计算几何]平面空间点旋转坐标变换

下班在写....

[综合] POJ 1444 计算几何趣题

求长方体上两点表面距离。 用到了比较神奇的递归，很有趣。学习之。 将1点旋转至XOY平面，再用递归四面展开，限制步数，得到最近的距离。 /**********************Creater:Sevenster**Time:2012.07.3113:28**PID:POJ1444******...