hdu1166敌兵布阵
线段树的入门题,更新结点，查询区间和
查看代码
hdu1754 I Hate It
入门题，更新结点，查询区间最大值
hdu 1698 Just a Hook
更新一段区间上的颜色，求值。学习了懒操作。
poj 2777 Count Color
给区间染色，求一段区间内颜色的种树。学会了线段树的新写法以及位操作。
hdu 3081 Marriage Match II
n男n女过家家，女生可以挑没有跟她吵过架的男生匹配，也可与没有跟她朋友吵过架的男生匹配（可以认为是她喜欢的男生）。每轮游戏，每个女生选个她没选过的男生，问游戏最多能进行几轮？
构图：先用并查集处理女生友情的传递。每个女向她喜欢的所有男生以及她朋友喜欢的男生连一条容量为1的边。二分最大能进行的轮数ans，源点向每个女生连一条容量为ans的边，每个男生向汇点连一条容量为ans的边。判断最大流是否等于ans*N;
hdu 3277 Marriage Match III
同上，每个女生可以跟最多K个她不喜欢的男生匹配。
构图：每个女生拆为两个点Gi1,Gi2。Gi1连一条容量为K的边到Gi2。每个Gi2连一条容量为1的边到女生i不喜欢的男生，源点连容量为ans的边到每个Gi1。其余同上。
一开始用Dinic，无限TLE~~~ T_T 。万般无奈下，只好上Qinz大牛的博客膜拜了ISAP的模板，再结合网上各路神牛的论文，终于得出了一份自己的ISAP模板～，提交果断AC～
hdu 3416 Marriage Match IV
有向图，求起点到终点的最短路的条数。
构图：求最短路，起点到所有点的最短路，所有边反向，求终点到所有点的最短路，对于边如果起点到u的距离加终点到v的距离加这条边的权值等于最短路长，那么在网络流的图中加一条u指向v，权值为1的边。求起点到终点的最大流。
poj 3281 Dining
N头牛，D种饮料，F种食物，每天牛吃一种食物一种饮料，食物和饮料都只有一份。问最大满足多少头牛。
构图：由于每头牛只需一份饮料和食物，所以每头牛要拆为两点，连容量为1的边。起点到所有食物连容量为1的边，饮料到汇点连容量为1的边。牛再和食物，饮料连。Dinic 0MS毫无压力。
poj 2135 Farm Tour
求起点到终点再回起点的最短路径。不能走重复的路。
构图：第一次写费用流。用的是朴素的spfa。费用是距离。源点到1连一条容量为2的边。终点到汇点连容量为2的边。每条路径的容量都为1.直接水过。
poj 2711 Leapin' Lizards
图上有些柱子，开始时，一些蜥蜴在柱子上，当蜥蜴跳离柱子时，柱子高度降1，蜥蜴不能跳到高度为0的柱子上，蜥蜴跳跃的距离为D，求有多少蜥蜴能够跳出来。
构图：把每个有高度柱子拆为两点，ai,bi，ai->bi容量为柱子高度。源点接到有蜥蜴的柱子ai上，能一步跳出去的柱子的bi接到汇点，容量INF，距离为D的任意两格子都连容量INF的边。求解最大流。求曼哈顿距离的时候出了点小问题，无限WA。注意输出，单复数是不同的。
poj 2516 Minimum Cost
有N个客户订单，M座仓库。给出订单内容和仓库库存，以及仓库到客户的费用。求满足所有客户需求的最小费用。
构图：原生态最小费用流。每种商品都是独立的，那么我们可以针对每种商品计算最小费用。从源点连容量为仓库i中k种商品库存费用为0的边到仓库i,仓库i接容量为无限，费用为到客户j的费用。如果最大流等于k的需求总量那么k就满足了。可以记录每种商品需求总量和库存总量。供不应求则输出-1 。
poj 3680 Intervals
已知N条线段的端点和线段的权值，选一些线段使权值最大，坐标轴上一点最多被覆盖K次。
构图：费用流。原打算拆点连边。感觉复杂度过不了，膜拜了传说中神一般的构图：先把点离散化，起点到第一点连权值为0，容量为K，i到i+1连权值为0容量为K的边，直到汇点。一条线段的起始点连一条容量为1权值为-w的边到结束点。
割点
割点：如果在图G中删去一个结点u后，图G的连通分枝数增加，即W(G-u)>W(G)，则称结点u为G的割点，又称关节点。
直观地说，就是删除了连通图的某点后，图不在连通，而是分为几个连通分量。
性质：（1）考虑根节点Root，如果Root有数量多于1的子结点时，Root是割点。
（2）考虑非根结点u，当且仅当u的某个儿子及儿子的子孙均没有指向u的祖先的后向边时，u是割点。（LOW[v]>=DFN[u],v是u的孩子）
代码：
1 void DFS(int cur,int par)
2 {
3 dfn[cur]=low[cur]=++Index;
4
5 int size=adj[cur].size();
6 int cnt=0;
7 for(int i=0;i<size;i++)
8 {
9 int v=adj[cur][i];
10 if(!dfn[v])
11 {
12 cnt++;
13 DFS(v,cur);
14 if(low[cur]>low[v])
15 low[cur]=low[v];
16 if((cur==root&&cnt==2)||(cur!=root&&low[v]>=dfn[cur]))
17 flag[cur]=true;
18 }
19 else if(v!=par&&low[cur]>dfn[v])
20 low[cur]=dfn[v];
21 }
22 }
23
割边
割边：如果在图G中删去一条边e后，图G的连通分支数增加，即W(G-e)>W(G)，则称边u为G的桥，又称割边或关节边。
性质: 对于一条边<u,v>，v是u的孩子如果儿子及儿子的子孙均没有指向u的祖先的后向边时，<u,v>是割边。（LOW[v]>DFN[u]）
代码：
1 void CutEdge(int cur,int par)
2 { dfn[cur]=low[cur]=++Index;
3
4 for(int i=head[cur];i;i=buf[i].next)
5 {
6 int v=buf[i].v;
7 if(v==par)continue;
8 if(!dfn[v])
9 {
10 CutEdge(v,cur);
11 if(low[cur]>low[v])
12 low[cur]=low[v];
13 if(low[v]>dfn[cur])
14 {
15 ans[nAns++]=buf[i].id;
16 }
17 }
18 else if(low[cur]>dfn[v])
19 low[cur]=dfn[v];
20 }
21 }
相关习题：
POJ 1144 Network 赤果果的求割点的题。
相关链接:
Beyond the Void的讲解，很精彩
推荐阅读：
lrj的黑书P285
由于原来的yo2不能用了，只好转战CPP。这个Blog将会用来记录一些胡思乱想的成果，神经质的言语。
形式主义的来个HelloWorld:
1
cout<<"Hello World"<<endl;