- 博客(97)
- 收藏
- 关注
RSS订阅转载 Python入门学习指导（VS Code配置向）
代码编辑器或IDE 推荐Vs Code，Atom和Sublime（本文以Vs Code为例，Sublime对中文支持不是很好，时常弄好了Sublime的乱码，却在复制到其他编辑器时出了问题） Vs Code官网：VS Code Vs Code快捷键官方文档：VS Code快捷键手册Python版本及安装问题 Python3.x有一些不兼容Python2.x的地...
2017-10-02 17:41:00
150
转载 QT特供 CGAL配置流程（基于QT5+VS2015）
最近做的QT项目涉及计算几何库，需要用到CGAL，其配置着实麻烦，而且相互关联的软件也存在版本兼容一类的问题，在这里就对其配置流程做一些整理说明，以便后来者能够少些烦恼。（注：以下使用Win10作说明）本流程前题条件VS+QT的配置已经没有问题CGAL配置相关软件说明在CGAL官网下载页面上有相关软件的安装配置说明（Download CGAL for Windows...
2017-01-02 16:11:00
535
转载 ACM/ICPC 之 中国剩余定理+容斥原理(HDU5768)
二进制枚举+容斥原理+中国剩余定理#include<iostream>#include<cstring>#include<cstdio>#include<algorithm>#include<cmath>using namespace std;#define MAXN 20typ...
2016-08-16 11:15:00
173
转载 ACM/ICPC 之 三维计算几何+暴力枚举+判重(HDU5839)
CCPC网赛第八题，求立体几何数量，题解见注释//立体几何-求满足要求的四面体个数//要求1：至少4条边相等//要求2：四条边相等时，另两条边一定不相邻（即对边）//题解：以当前边为不相邻的其中一条边，对可以构成等腰三角形的第三点进行枚举//再对这些第三点的集合做一次n^2的枚举，分两种情况找出四面体//如果四条边或五条边相同，则只存在两种重复情况(当前...
2016-08-15 01:00:00
116
转载 ACM/ICPC 之 有流量上下界的网络流-Dinic(可做模板)(POJ2396)
//有流量上下界的网络流//Time:47Ms Memory:1788K#include<iostream>#include<cstring>#include<cstdio>#include<algorithm>#include<queue>using namespace st...
2016-08-05 11:32:00
109
转载 ACM/ICPC 之 Dinic+枚举最小割点集(可做模板)(POJ1815)
最小割的好题，可用作模板。//Dinic+枚举字典序最小的最小割点集//Time:1032Ms Memory:1492K#include<iostream>#include<cstring>#include<cstdio>#include<algorithm>#include<queu...
2016-08-04 14:19:00
109
转载 ACM/ICPC 之 DP解有规律的最短路问题(POJ3377)
//POJ3377//DP解法-解有规律的最短路问题//Time:1157Ms Memory:12440K#include<iostream>#include<cstring>#include<cstdio>using namespace std;#define MAXN 1000005typede...
2016-08-04 10:40:00
98
转载 ACM/ICPC 之 DFS+SPFA-贪心+最短路(POJ2679)
//POJ2679//DFS+SPFA+邻接表//只能走每个点费用最小的边，相同则需保证距离最短//求最小费用及最短距离//Time:47Ms Memory:900K#include<iostream>#include<cstring>#include<cstdio>#include<algor...
2016-08-03 12:40:00
106
转载 ACM/ICPC 之 靠墙走-DFS+BFS(POJ3083)
//POJ3083//DFS求靠左墙(右墙)走的路径长+BFS求最短路//Time:0Ms Memory:716K#include<iostream>#include<cstring>#include<cstdio>#include<queue>using namespace std;#def...
2016-08-02 19:48:00
102
转载 ACM/ICPC 之 计算几何入门-叉积-to left test(POJ2318-POJ2398)
POJ2318 本题需要运用to left test不断判断点处于哪个分区，并统计分区的点个数(保证点不在边界和界外)，用来做叉积入门题很合适//计算几何-叉积入门题//Time:157Ms Memory:828K#include<iostream>#include<cstring>#include<cstdio...
2016-08-02 11:06:00
180
转载 ACM/ICPC 之 机器调度-匈牙利算法解最小点覆盖集(DFS)(POJ1325)
//匈牙利算法-DFS//求最小点覆盖集 == 求最大匹配//Time:0Ms Memory:208K#include<iostream>#include<cstring>#include<cstdio>#include<algorithm>using namespace std;#define ...
2016-08-02 11:04:00
109
转载 ACM/ICPC 之 卡卡的矩阵旅行-最小费用最大流(可做模板)(POJ3422)
将每个点拆分成原点A与伪点B，A->B有两条单向路(邻接表实现时需要建立一条反向的空边，并保证环路费用和为0)，一条残留容量为1，费用为本身的负值(便于计算最短路)，另一条残留容量+∞，费用为0(保证可以多次通过该点，但费用只计算一次)。 另外伪点B与原点右侧与下方的点有一条单向路(邻接表实现需要建立反向空边)，残留容量为+∞，费用为0。源点0到点1有一条单向路，残留容量...
2016-07-29 17:30:00
102
转载 ACM/ICPC 之 伞兵-最小割转最大流(POJ3308)
//以行列建点，伞兵位置为单向边-利用对数将乘积转加法//最小割转最大流//Time:63Ms Memory:792K#include<iostream>#include<cstring>#include<cstdio>#include<cmath>#include<algorithm>...
2016-07-29 09:41:00
101
转载 ACM/ICPC 之 最小割转网络流(POJ3469)
重点：构图//最小割转网络流//邻接表+Dinic//Time:5797Ms Memory:6192K#include<iostream>#include<cstring>#include<cstdio>#include<algorithm>#include<queue>us...
2016-07-28 18:28:00
92
转载 ACM/ICPC 之 ACM计算机工厂-EK算法(POJ3436)
题意有点难读懂//网络流-EK算法-ACM计算机工厂-构图重点//Time:0Ms Memory:208K#include <iostream>#include<cstring>#include<cstdio>#include<algorithm>#include<queue>us...
2016-07-28 14:45:00
152
转载 ACM/ICPC 之 网络流-拆点构图(POJ2391)
需要直接到达，因此源点经过三条边后必须要达到汇点，但为了保证网络流的正确性（路径可反悔），因此不可限制层次网络的最高层次为3，最好的方法既是让所有点拆分成两个点，一个点从汇点进入，一个点通向汇点，任意两点的路径则标注为最短路径。//Dinic算法-拆点构图//Time:625Ms Memory:2108K#include<iostream>...
2016-07-28 14:43:00
128
转载 ACM/ICPC 之 混合图的欧拉回路判定-网络流(POJ1637)
//网络流判定混合图欧拉回路//通过网络流使得各点的出入度相同则possible，否则impossible//残留网络的权值为可改变方向的次数，即n个双向边则有n次//Time:157Ms Memory:348K#include <iostream>#include<cstring>#include<cstdio>...
2016-07-28 14:38:00
87
转载 ACM/ICPC 之 Unix会议室（POJ1087）
采用EK算法解网络流经典题，本题构图思路比较明确。//Unix会议室插座转换//网络流-EK算法//Time:47Ms Memory:1188K#include<iostream>#include<cstring>#include<cstdio>#include<algorithm>#i...
2016-07-26 13:42:00
94
转载 ACM/ICPC 之 电力网络-EK算法(POJ1459)
按照电站发电（从源点到电站），消费者消费（从消费者到汇点）的想法构建网络，以下是EK解法//网络流EK算法//Time:922Ms memory:224K#include<iostream>#include<cstring>#include<cstdio>#include<algorithm>...
2016-07-26 12:40:00
128
转载 ACM/ICPC 之 Dinic算法（POJ2112）
Optimal Milking//二分枚举最大距离的最小值+Floyd找到最短路+Dinic算法//参考图论算法书，并对BFS构建层次网络算法进行改进//Time:157Ms Memory:652K#include<iostream>#include<cstring>#include<cstdio>#in...
2016-07-26 09:38:00
77
转载 ACM/ICPC 之 网络流入门-EK算法(参考模板)(POJ1273)
基于残留网络与FF算法的改进-EK算法，核心是将一条边的单向残留容量的减少看做反向残留流量的增加。//网络流//EK算法//Time:16Ms Memory:348K#include<iostream>#include<cstring>#include<cstdio>#include<algorithm...
2016-07-25 16:50:00
110
转载 ACM/ICPC 之 网络流入门-Ford Fulkerson与SAP算法(POJ1149-POJ1273)
第一题：按顾客访问猪圈的顺序依次构图（顾客为结点），汇点->第一个顾客->第二个顾客->...->汇点//第一道网络流//Ford-Fulkerson//Time:47Ms Memory:276K#include<iostream>#include<cstring>#include<cs...
2016-07-25 12:07:00
99
转载 ACM/ICPC 之 DFS求解欧拉通路路径（POJ2337）
判断是欧拉通路后，DFS简单剪枝求解字典序最小的欧拉通路路径//Time:16Ms Memory:228K#include<iostream>#include<cstring>#include<cstdio>#include<algorithm>using namespace std;#...
2016-07-24 13:01:00
120
转载 ACM/ICPC 之 DFS求解欧拉回路+打表（POJ1392）
本题可以通过全部n位二进制数作点，而后可按照某点A的末位数与某点B的首位数相等来建立A->B有向边，以此构图，改有向图则是一个有向欧拉回路，以下我利用DFS暴力求解该欧拉回路得到的字典序最小的路径。//求咬尾数，一个2^n位环形二进制数，该二进制的每n位连续二进制数都不同//DFS求解欧拉回路//Time:32ms Memory:1668K#i...
2016-07-24 09:31:00
129
转载 ACM/ICPC 之 暴力打表(求解欧拉回路)-编码（POJ1780）
///找到一个数字序列包含所有n位数(连续)一次且仅一次///暴力打表///Time:141Ms Memory:2260K#include<iostream>#include<cstring>#include<cstdio>using namespace std;#define MAX 1000010b...
2016-07-23 14:15:00
136
转载 ACM/ICPC 之 昂贵的聘礼-最短路解法(POJ1062)
//转移为最短路问题，枚举必经每一个不小于酋长等级的人的最短路//Time:16Ms Memory:208K#include<iostream>#include<cstring>#include<cstdio>#include<cmath>#include<algorithm>usin...
2016-06-07 22:42:00
57
转载 ACM/ICPC 之 SPFA-兑换货币(POJ1860)
//水题-SPFA解法//套汇是指兑换货币后能使本金上升//给定本金货币编号，货币间的汇率和手续费，求能否套汇成功//Time:16Ms Memory:200K#include<iostream>#include<cstring>#include<cstdio>#include<queue>usin...
2016-06-07 09:38:00
149
转载 ACM/ICPC 之 欧拉回路两道(POJ1300-POJ1386)
两道有关欧拉回路的例题POJ1300-Door Man//判定是否存在从某点到0点的欧拉回路//Time:0Ms Memory:116K#include<iostream>#include<cstring>#include<cstdio>using namespace std;#define...
2016-05-23 12:45:00
82
转载 ACM/ICPC 之 差分约束系统两道(ZOJ2770-POJ1201)
当对问题建立数学模型后，发现其是一个差分方程组，那么问题可以转换为最短路问题，一下分别选用Bellmanford-SPFA解题ZOJ2770-Burn the Linked Camp//差分约束方程组-转换为最短路问题//d[v] <= d[u] + dis[u][v] -> d[v] - d[u] <= dis[u][v]//...
2016-05-21 21:15:00
110
转载 ACM/ICPC 之 Floyd练习六道(ZOJ2027-POJ2253-POJ2472-POJ1125-POJ1603-POJ2607)
以Floyd解法为主的练习题六道ZOJ2027-Travelling Fee//可免去一条线路中直接连接两城市的最大旅行费用，求最小总旅行费用//Time:0Ms Memory:604K#include<iostream>#include<cstring>#include<cstdio>#include&...
2016-05-16 22:42:00
114
转载 ACM/ICPC 之 Floyd范例两道(POJ2570-POJ2263)
两道以Floyd算法为解法的范例，第二题如果数据量较大，须采用其他解法POJ2570-Fiber Network//经典的传递闭包问题，由于只有26个公司可以采用二进制存储//Time:141Ms Memory:328K#include<iostream>#include<cstring>#include<c...
2016-05-12 09:37:00
86
转载 ACM/ICPC 之 SPFA练习两道(ZOJ3088-ZOJ3103)
两道题都需要进行双向SPFA，比范例复杂，代码也较长，其中第二题应该可以用DFS或者BFS做，如果用DFS可能需要的剪枝较多。ZOJ3088-Easter Holydays//利用SPFA找出下降最长路径和上升最短路径，输出最大的比值和回路路径//Time:0Ms Memory:328K#include<iostream>...
2016-05-11 11:22:00
99
转载 ACM/ICPC 之 SPFA范例两道(POJ3268-POJ3259)
两道以SPFA算法求解的最短路问题，比较水，第二题需要掌握如何判断负权值回路。POJ3268-Silver Cow Party//计算正逆最短路径之和的最大值//Time:32Ms Memory:360K#include<iostream>#include<cstring>#include<cstdio>...
2016-05-09 23:04:00
83
转载 ACM/ICPC 之 树形DP(POJ1192)
将某点看做根状态，邻接点看做子状态，由子状态向根状态转移。POJ1192-最优连通子集 题解：将每一个点分成两个状态进行保存，因此可以构造一个数组dp[i][2]。 dp[i][0]：不包括该点权值的子集最大权值和 dp[i][1]：包括该点权值的子集最大权值和//Time:16Ms Memory:184K#inc...
2016-05-08 23:34:00
81
转载 ACM/ICPC 之 Floyd+记录路径后继(Hdu1385(ZOJ1456))
需要处理好字典序最小的路径HDU1385(ZOJ1456)-Minimum Transport//Hdu1385-ZOJ1456//给定邻接矩阵，求给定起点到终点的最短路径，若有相同路长的路径按照字典序输出//Floyd比较适合此题//网上看到的两种做法比较推荐//第一种是Floyd+记录起点后继//第二种是Floyd+深搜(从...
2016-05-08 23:26:00
76
转载 ACM/ICPC 之 Bellman Ford练习题(ZOJ1791(POJ1613))
这道题稍复杂一些，需要掌握字符串输入的处理+限制了可以行走的时间。ZOJ1791(POJ1613)-Cave Raider//限制行走时间的最短路//POJ1613-ZOJ1791//Time:16Ms Memory:324K#include<iostream>#include<cstring>#incl...
2016-05-08 23:22:00
101
转载 ACM/ICPC 之 最短路径-Bellman Ford范例(POJ1556-POJ2240)
两道Bellman Ford解最短路的范例，Bellman Ford只是一种最短路的方法，两道都可以用dijkstra, SPFA做。 Bellman Ford解法是将每条边遍历一次，遍历一次所有边可以求得一点到任意一点经过一条边的最短路，遍历两次可以求得一点到任意一点经过两条边的最短路...如 此反复，当遍历m次所有边后，则可以求得一点到任意一点经过m条边后的最短路（有...
2016-05-03 22:27:00
108
转载 ACM/ICPC 之 最短路-SPFA+正逆邻接表(POJ1511(ZOJ2008))
求单源最短路到其余各点，然后返回源点的总最短路长，以构造邻接表的方法不同分为两种解法。POJ1511(ZOJ2008)-Invitation Cards 改变构造邻接表的方法后，分为两种解法解法一： 1 //POJ1511-ZOJ2008 2 //Time：7766Ms Memory：99112K 3 //求从1处到各...
2016-05-02 15:39:00
104
转载 ACM/ICPC 之 最短路-Floyd+SPFA(BFS)+DP(ZOJ1232)
这是一道非常好的题目，融合了很多知识点。ZOJ1232-Adventrue of Super Mario 这一题折磨我挺长时间的，不过最后做出来非常开心啊，哇咔咔咔 题意就不累述了，注释有写，难点在于状态转移方程的确立和SPFA的过程 1 //最短路：Floyd+SPFA(BFS)+DP 2 //Time:20Ms ...
2016-05-02 15:32:00
100
转载 ACM/ICPC 之 两道dijkstra练习题(ZOJ1053(POJ1122)-ZOJ1053)
两道较为典型的单源最短路径问题，采用dijkstra解法 本来是四道练习题，后来发现后面两道用dijkstra来解的话总觉得有点冗余了，因此暂且分成三篇博客（本篇以及后两篇）。ZOJ1053(POJ1122)-FDNY to the Rescue! 1 //POJ1122-ZOJ1053 2 //dijkstra-需要记录路径 3...
2016-05-02 15:17:00
115
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人