前言：sb环套树写错了，然后就送命了。。
a 巧克力铁丝
题目描述
在一个二维平面里，有n块巧克力，每块巧克力都是长方形(正方形也可以认为是长方形)，每块巧克力的四条边都平行于X轴或平行于Y轴。我们用(X1, Y1, X2, Y2)来描述一块巧克力的所在位置，其中(X1, Y1)表示这块巧克力左下角的坐标，(X2，Y2) 表示这块巧克力右上角的坐标。注意：题目给出的n块巧克力之间可能有重叠的地方。奶牛bessie手头上有一个a × b的长方形铁丝框. Bessie想知道它应该把铁丝框放在哪个位置，才能使得可以拿走的巧克力的个数最多？农夫FJ规定：bessie铁丝框放的位置也必须要平行X轴和Y轴，而且还规定，bessie只能拿走在铁丝框里面的巧克力，bessie最多能拿走多少块巧克力？bessie只能放一次铁丝框。解释：如果某块巧克力的位置是：(1,1, 2, 2), 而铁丝框的位置是(-1,1,2,100), 那么这块巧克力也是在铁丝框里面，可以被bessie拿走。也就是说，如果某块巧克力任何部分都没有超出铁丝框, 就可以认为是在铁丝框里面。
输入格式
第一行：一个整数n. 0 <= n <= 50。
第2至n+1行，每行四个整数: X1, Y1, X2, Y2, 描述巧克力的位置. -10^9 <= X1, Y1, X2, Y2 <= 10^9.
最后一行：两个整数: a 、b. 且1 <= a , b <= 10^9.
输出格式
一个整数，bessie最多能拿走多少块巧克力？
输入样例
样例1输入：
3
1 1 2 2
2 2 3 3
3 3 4 4
2 2
样例2输入:
2
0 1 2 3
3 0 4 2
4 3
输出样例
样例1输出：
2
样例解释：如果bessie把铁丝框放在(1,1,3,3)处, 那么它可以拿走第1和第2块巧克力；如果把铁丝框放在(2,2,4,4)那么它可以拿走第2和第3块巧克力。
样例2输出:
2
解题思路(直接做)
这题没有什么算法。直接按题目要求的做就可以了。
首先要明白每个框最好的放法肯定是贴着某(些)巧克力两条的边。
然后我们只需将所有巧克力的边收集起来然后枚举矩形框的位置，判断巧克力是否入框就行了。
值得注意的，框可以翻来覆去放。
时间
代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#define N 60
using namespace std;
int n, A, B, px[N<<1], py[N<<1], ans;
struct Data{
int x1, y1, x2, y2;
Data() {}
Data(int x1, int y1, int x2, int y2):x1(x1), y1(y1), x2(x2), y2(y2) {}
}rec[N];
bool Judge(Data P, Data Q){
return P.x1 >= Q.x1 && P.y1 >= Q.y1 && P.x2 <= Q.x2 && P.y2 <= Q.y2;
}
int main(){
freopen("a.in", "r", stdin);
freopen("a.out", "w", stdout);
scanf("%d", &n);
for(int i = 1; i <= n; i++){
scanf("%d%d%d%d", &rec[i].x1, &rec[i].y1, &rec[i].x2, &rec[i].y2);
px[++px[0]] = rec[i].x1;
px[++px[0]] = rec[i].x2;
py[++py[0]] = rec[i].y1;
py[++py[0]] = rec[i].y2;
}
scanf("%d%d", &A, &B);
for(int i = 1; i <= px[0]; i++)
for(int j = 1; j <= py[0]; j++){
Data Fe1 = Data(px[i], py[j], px[i]+A, py[j]+B);
Data Fe2 = Data(px[i], py[j], px[i]+B, py[j]+A);
int temp1 = 0, temp2 = 0;
for(int k = 1; k <= n; k++){
if(Judge(rec[k], Fe1)) temp1 ++;
if(Judge(rec[k], Fe2)) temp2 ++;
}
ans = max(ans, max(temp1, temp2));
}
printf("%d\n", ans);
return 0;
} b 旅行
题目描述
在一段时间之后，网络公司终于有了一定的知名度，也开始收到一些订单，其中最大的一宗来自B市。Blue Mary决定亲自去签下这份订单。
为了节省旅行经费，他的某个金融顾问建议只购买U航空公司的机票。U航空公司的所有航班每天都只有一班，并且都是上午出发当天下午到达的，所以他们每人每天只能坐一班飞机。经过调查，他们得到了U航空公司经营的所有航班的详细信息，这包括每一航班的出发地，目的地以及最多能买到的某一天出发的票数。(注意: 对于一个确定的航班，无论是哪一天，他们最多能买到的那一天出发的票数都是相同的。)
Blue Mary注意到他们一定可以只乘坐U航空公司的航班就从A市到达B市，但是，由于每一航班能买到的票的数量的限制，他们所有人可能不能在同一天到达B市。所以现在Blue Mary需要你的帮助，设计一个旅行方案使得最后到达B市的人的到达时间最早。
输入格式
第一行包含3个正整数N，M和T。题目中会出现的所有城市分别编号为1,2,…,N，其中城市A编号一定为1，城市B编号一定为N. U公司一共有M条（单向）航班。而连Blue Mary在内，公司一共有T个人要从A市前往B市。
以下M行，每行包含3个正整数X,Y,Z, 表示U公司的每一条航班的出发地，目的地以及Blue Mary最多能够买到的这一航班某一天出发的票数。(即：无论是哪一天，Blue Mary最多只能买到Z张U航空公司的从城市X出发到城市Y的机票。)
输入保证从一个城市到另一个城市的单向航班最多只有一个。
输出格式
仅有一行，包含一个正整数，表示最后到达B市的人的最早到达时间。假设他们第一次乘飞机的那一天是第一天。
输入样例
3 3 5
1 2 1
2 3 5
3 1 4
输出样例
6
本题数据范围
2 <= N <= 50
1 <= M <= 2450
1 <= T <= 50
1 <= X，Y <= N
X != Y
1 <= Z <= 50
解题思路(二分答案+网络流)
首先，这题我做得很差。一看到要使最晚到达的时间最早，立刻如醍醐灌顶、膝跳反射般想到二分答案。我想到了，这题我花了很久(另外两题都比较简单)，想二分后如何检验，贪心？应该不太可能。dp？退了好久，发现不会。网络流？我真想到过，但naive的我认为票数作为原图的边在网络上要拆，难道要写一个能拆边的网络流？(这里全是一个sb的想法)怎么办？写不了，弃！
然后我就写了一个类似于sp(b)fa的dp边宽搜边搞，最后发现有后效性。搞不定了。
其实网络流的构图和原图没有关系，原图上的一些限制在网络上用容量限制表示出来就行了，两者是互不影响的。
这题并不需要神么拆边，拆点才是解决网络流问题的常见手段。
这题如果熟悉网络流的技巧其实并不算难，但在考场上有且仅有网络流大神tututu做对了此题。据说玄学贪心也能过很多点。我写完sp(b)fa后就对这题不报太大希望了，谁知最后发现第三题写炸了，真是后悔莫及啊。。
现在讲正解。正解是动态流，要边做边构图。(tututu唬我们的)。其实只用将原图上的一个点拆成Limit个点，Limit是二分出来的时间限制，然后就开始按题目要求连边，建一个s向第一天的第一个点连边，容量为总人数T，建一个t由最后一天的最后一个点连过去，容量为T。中间有航班的就对应着时间和线路来连，容量为票数，可以在中途停留，所以也要向同一地点的明天连边，容量为oo。然后跑一遍最大流，如果流量恰好为T，则可行，否则不可行。
正确性的话，这是显然的，但在考场上想到，好像不是那么容易呢。
时间复杂度就是网络流的时间复杂度(玄学)。
讲一个笑话，我一开始这样写Dinic超时了，然后将二分的上界改到最小(T*2+1)后还是超。然后改成多路增广（以前我都是写单路），还是超。无奈之下请tututu帮忙看。他帮我把点数改成10万，边数改成100万，再交，居然过了！！定睛一看，果然是点数开小了导致超时。tututu的教诲：凡是网络流是正解的题，点开10万，边开100万肯定不会错，空间不会炸，而且多过这个限制的网络流做不了。果真强，不像蒟蒻我每次都去算该开多大。。%%%
然后这题就到这里了，要多学习总结网络流的建模，像二分+重新构图这种常见套路一定要熟记。抽空补一下网络流24题。
代码
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#define nn 60
#define N 5050
#define oo 0x7fffffff
using namespace std;
int n, m, T, cur, s, t;
int q[N], head_p[N], iter[N], level[N];
struct Data{int from, to, tic;} fli[N];
struct Ab{int next, obj, cap;} Edg[(N*nn+nn*nn+nn*2)*4];
void Insert(int a, int b, int c){
cur ++;
Edg[cur].next = head_p[a];
Edg[cur].obj = b;
Edg[cur].cap = c;
head_p[a] = cur;
}
bool bfs(){
int head, tail;
memset(level, -1, sizeof(level));
level[s] = 0;
q[head = tail = 0] = s;
while(head <= tail){
int now = q[head++];
for(int i = head_p[now]; ~ i; i = Edg[i].next){
int v = Edg[i].obj, c = Edg[i].cap;
if(level[v] == -1 && c){
level[v] = level[now] + 1;
q[++tail] = v;
}
}
}
return level[t] != -1;
}
int Dinic(int now, int f){
if(now == t || !f) return f;
int ret = 0;
for(int &i = iter[now]; ~ i; i = Edg[i].next){
int v = Edg[i].obj, c = Edg[i].cap;
if(level[v] > level[now] && c){
int d = Dinic(v, min(c, f));
f -= d;
Edg[i].cap -= d;
Edg[i^1].cap += d;
ret += d;
if(!f) break;
}
}
return ret;
}
int Max_flow(){
int flow = 0;
while(bfs()){
for(int i = s; i <= t; i++) iter[i] = head_p[i];
flow += Dinic(s, oo);
}
return flow;
}
bool Judge(int limit){
s = 1; t = s + limit * n + 1;
cur = -1;
for(int i = s; i <= t; i++) head_p[i] = -1;
Insert(s, s+1, T);
Insert(s+1, s, 0);
Insert(t-1, t, T);
Insert(t, t-1, 0);
for(int i = 1; i <= m; i++)
for(int j = 1; j < limit; j++){
Insert(s+(j-1)*n+fli[i].from, s+j*n+fli[i].to, fli[i].tic);
Insert(s+j*n+fli[i].to, s+(j-1)*n+fli[i].from, 0);
}
for(int i = 1; i <= n; i++)
for(int j = 1; j < limit; j++){
Insert(s+(j-1)*n+i, s+j*n+i, oo);
Insert(s+j*n+i, s+j*n+i, 0);
}
return Max_flow() == T;
}
int main(){
freopen("b.in", "r", stdin);
freopen("b.out", "w", stdout);
scanf("%d%d%d", &n, &m, &T);
for(int i = 1; i <= m; i++) scanf("%d%d%d", &fli[i].from, &fli[i].to, &fli[i].tic);
int L = 0, R = T * 2 + 1;
while(L + 1 < R){
int mid = (L + R) >> 1;
if(Judge(mid)) R = mid;
else L = mid;
}
printf("%d\n", R - 1);
return 0;
}c 交通违法
题目描述
禅城区有N条双向道路和N个路口，路口的编号从1至N。每条道路连接两个路口。两个路口之间不会有重边。
保证任意两个路口都是相互到达的。现在觉得在一些路口装上摄像头，检测路面的违法情况。
装在路口的摄像头可以监测到所有连接到这个路口的道路。现在的问题是：最少需要在多少个路口安装摄像头才能监测所有的道路？
输入格式
输入文件第1行包括一个数字N(1 <= N <= 100000)
接下来N行，第i+1行的第一个数字Ai表示有Ai条道路与路口i相连，后面紧跟着Ai个数字，表示与路口i直接相连的路口。
输出格式
最少的摄像头数量。
输入样例
3
2 2 3
2 1 3
2 1 2
输出样例
2
解题思路(环套树dp)
这题一看就是个环套树。
n点n边，求最小点覆盖。如果是二分图直接求最大匹配。一般图的话也不会考带花树什么鬼的吧，还好这题就是个环套树。
考场上犯了个傻叉无比的错误，导致信心满满的一题就此爆零。
不说废话，正解的话，直接记
虽然简单，但这题还有其他作法。由于最小点覆盖与最大独立集互为补集。我们就直接按某骑士那题一样写求最大独立集的模版，再用
然而由于点数较大，直接dfs写在win下会爆栈，如果硬不服气，就可以像KsCla那样将环套树拆成先树形dp后再做一遍环形dp，这样可以用bfs代替dfs，但除外这是没什么必要的。
另，环形dp也是要做的，如果在环上贪心明显是错的，因为环上还有外向树套在那里的。
再另，找到环后最后再做dp是好的，如果在dfs中做dp就会做两遍(一次在
时间
代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#define N 100010
using namespace std;
int n, cur = -1, head_p[N], ban1, ban2, ans;
int f[N], g[N];
struct Tadj{int next, obj;} Edg[N<<1];
bool vis[N];
void Insert(int a, int b){
cur ++;
Edg[cur].next = head_p[a];
Edg[cur].obj = b;
head_p[a] = cur;
}
void dp(int root, int fa){
f[root] = 1;
g[root] = 0;
for(int i = head_p[root]; ~ i; i = Edg[i].next){
int v = Edg[i].obj;
if((root == ban1 && v == ban2) || (root == ban2 && v == ban1) || v == fa) continue;
dp(v, root);
g[root] += f[v];
f[root] += min(f[v], g[v]);
}
}
int Work(int u, int v){
int temp;
dp(u, 0);
temp = f[u];
dp(v, 0);
temp = min(temp, f[v]);
return temp;
}
void dfs(int root, int fa){
vis[root] = true;
for(int i = head_p[root]; ~ i; i = Edg[i].next){
int v = Edg[i].obj;
if(v == fa) continue;
if(vis[v]){
ban1 = root;
ban2 = v;
}
else dfs(v, root);
}
}
int main(){
freopen("c.in", "r", stdin);
freopen("c.out", "w", stdout);
scanf("%d", &n);
for(int i = 1; i <= n; i++) head_p[i] = -1;
int num, x;
for(int i = 1; i <= n; i++){
scanf("%d", &num);
for(int j = 1; j <= num; j++){
scanf("%d", &x);
Insert(i, x);
}
}
dfs(1, 0);
ans = Work(ban1, ban2);
printf("%d\n", ans);
return 0;
}总结
但愿sb题不要再写错，不然标准分就天差地别，rank也天差地别了。加油吧，坚持下去。
美人如诗，草木如织。