hdu 4291 A Short problem 打表找规律&矩阵快速幂
http://www.cnblogs.com/kuangbin/archive/2012/09/17/2688852.html
//author: CHC//First Edit Time: 2014-10-18 16:11//Last Edit Time: 2014-10-18 23:27#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <set>#include <vector>#include <map>#include <queue>#include <set>#include <algorithm>#include <limits>using namespace std;typedef long long LL;const int MAXN=1e+4;const int MAXM=1e+5;const int INF= numeric_l ...
NOI 2008 志愿者招募
题目链接：
http://codevs.cn/problem/1803/
或
http://www.lydsy.com:808/JudgeOnline/problem.php?id=1061
神一般的建图方式。。。参考了byv大牛的博客。
https://www.byvoid.com/blog/noi-2008-employee/
这种建图方式让我大开眼界。。
首先根据题目要求找可行解。
找到可行解之后再在这基础上进行最小费用流。
找可行解的方式、
对于每一天构造一个不等式使得满足每一天的需求。当然第0天和第n+1天的需求是0
由于是一个不等式。需要添加一个辅助变量来使不等式化为等式、
第i个等式减去第i-1个等式。
观察发现满足流量守恒的定理。。每个变量只出现两次并且一次为正一次为负。右边的常数相加为0，满足。。
可行解。。
满足可行解之后对应变量添加对应的费用权值。。跑最小费用流。。
//author: CHC//First Edit Time: 2014-10-17 19:25//Last Edit Time: 2014-10-18 10 ...
HDU 4807 Lunch Time
题意好懂。。
枚举费用流路径&贪心。
找费用流路径，如果这条路径的流量是v，花费是c，那么，在第c秒的时候有v个人通过，c秒过后每一秒的时间这条路径有v个人通过。
知道这点就很好办了。
把所有的最小费用最大流路径找出来，然后先从最小花费开始遍历
判断，取 走后面路径需要花费的时间和不走后面的路径花费的时间最小。贪心
代码。
//author: CHC//First Edit Time: 2014-10-15 12:38//Last Edit Time: 2014-10-15 14:15#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <set>#include <vector>#include <map>#include <queue>#include <set>#include <algorithm>#include <limit ...
HDU 5025 Saving Tang Monk
搜索
优先队列或普通队列的特殊处理。
法一：
//First Edit Time: 2014-09-20 22:37//Last Edit Time: 2014-09-20 22:40#include <iostream>#include <cstdio>#include <cstring>#include <queue>#include <map>#include <set>#include <cmath>using namespace std;#define MAXN 110int vis[MAXN][MAXN][1<<6][15];char map1[MAXN][MAXN];struct point{ int x,y,step,stats,statk; bool operator<(point y)const { return step>y.step; }}st,et;struct snack ...
HDU 5040 Instrusive 搜索
题意：给n*m的图。图中有一些监视器。如果暴露在监视器下就会被发现。但是他有一个卡片盒子，他能躲在卡片盒子中，在卡片盒子中到下一个点需要花费3个单位的时间，如果不在卡片盒子中走到下一个点需要1个单位的时间，每个监视器可以监视的范围为它本身和四周的一个格子(上下左右)。如果一个点正在被监视。那么只能藏在盒子里走过去。他能在盒子里走到正在被监视的格子。每个监视器一开始监视某个格子，然后每秒顺时针旋转九十度。
这个图中包含
. 空地
# 障碍物
N 朝向北
S 朝向南
W 朝向西
E 朝向东
M 起始点
T 目标点
做法：暴搜，判断一个点在某个时间是否正在被监视比较麻烦。但是可以特殊处理。可以根据step%4的值来判断。
//author: CHC//First Edit Time: 2014-09-21 18:59//Last Edit Time: 2014-09-21 20:26#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include &l ...
HDU 3472 HS BDC 混合图欧拉回路 网络流
题意：给n个字符串，这些字符串如果某个字符串的尾部字母和另一个字符串的首部字母相等，那么这两个字母就可以连起来，有的字符串可以反转，问是否存在一种情况使得所有字符串都连成一条链。
这题真是好题。
建图方法一：
(无法做出。)
如果按照题意给定的方式建图，那么问题就转换为：
判断这个图中是否存在一条通路，通路访问图中所有点一次仅且一次。
一开始我的想法是找最长路，发现思路不可行。spfa碰到环就跪惨。
(tips:有人会最长路吗?为毛感觉这似乎是个不可解的问题= =)
后来查找资料过后发现是这是一个著名的图论模型：哈密顿图(也称Hamilton图)。
那么问题就变成了：
判断这个图有无哈密顿通路
哈密顿通路：经过图中所有节点一次仅且一次的通路。
哈密顿回路：经过图中所有节点一次仅且一次的回路。
哈密顿图： 存在哈密顿回路的图。
网上找了些资料，原来这是个NP问题。
多项式时间复杂度O(n!*n)，可以通过状态压缩&动态规划把复杂度降为O(2n*n3)。
对于这题来说。明显不能用。所以这种建图方式XX
建图方法二：
如果换一种建图方式。
字符串的首字母–>字符串的尾字母 ...
Zoj 3811 Untrusted Patrol 求连通顺序
题意：
给一个n个点m条边的无向图，给k个点。问你是否存在一条路径按顺序访问这些点并且这个图是连通的，就输出Yes，否则输出No
就是说。k=5 然后顺序是 1 2 3 4 5
1->2有路，并且路上不经过3 4 5
2->3有路，并且路上不经过4 5
3->4有路，并且不经过5
4->5有路
思路：
其实就是判断相邻两个点是否连通，用并查集做，先把不相关的点都并起来，然后依次把1相关的边合并，注意在合并1相关边的时候不能合并到2 3 4 5，同理合并2相关的边的时候，不能合并3 4 5，合并完后判断a[i]和a[i-1]这两个点是否同一集合，是的话再判断整个图的是否连通，是的话就输出Yes
代码如下：
//author: CHC//First Edit Time: 2014-09-07 13:55//Last Edit Time: 2014-09-08 09:03#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#incl ...
HDU 3998 Sequence
题意：
找最长上升子序列的长度。并且输出这个长度下的最长上升子序列有多少个（元素不能重复）。
建图：
超级源点->标为1的点
标为len的点->超级汇点
其他点(标为i)->标为i+1的点
//author: CHC//First Edit Time: 2014-09-06 10:35//Last Edit Time: 2014-09-06 11:21#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <set>#include <vector>#include <map>#include <queue>#include <set>#include <algorithm>#include <limits.h>using namespace std;typedef long long LL;const int MAXN=1e+4 ...
HDU 3338 Kakuro Extension
建了两次图。第一次建图后样例都跑不对。
一气之下全删重新建图就对了。。
建图方式：
超级源点->行 权值=行和-行约束点个数
行->约束点 权值=8
约束点->列 权值=8
列->超级汇点 权值=列和-列约束点个数
//author: CHC//First Edit Time: 2014-09-05 16:45//Last Edit Time: 2014-09-05 17:20#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <set>#include <vector>#include <map>#include <queue>#include <set>#include <algorithm>#include <limits.h>using namespace std;typedef long l ...
HDU 2732 Leapin' Lizards
直接暴力建图。。
//author: CHC//First Edit Time: 2014-08-16 21:47//Last Edit Time: 2014-08-17 11:01#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <set>#include <vector>#include <map>#include <queue>#include <set>#include <algorithm>#include <limits.h>using namespace std;typedef long long LL;const int MAXN=1e+4;const int MAXM=1e+5;const int INF = INT_MAX;struct Edge{ int from,to,ci,next; Edge()&# ...