置顶随笔

[置顶]本博已停,请绕道http://blog.wamaker.net

对cpp有点失望,换http://blog.wamaker.net

posted @ 2010-09-21 12:59 ZAKIR 阅读(149) | 评论 (0)编辑 收藏

2010年9月21日

本博已停,请绕道http://blog.wamaker.net

对cpp有点失望,换http://blog.wamaker.net

posted @ 2010-09-21 12:59 ZAKIR 阅读(149) | 评论 (0)编辑 收藏

2010年9月18日

线段树学习笔记

hdu1166敌兵布阵
线段树的入门题,更新结点,查询区间和查看代码

hdu1754 I Hate It

入门题,更新结点,查询区间最大值


hdu 1698  Just a Hook 

更新一段区间上的颜色,求值。学习了懒操作。


poj 2777 Count Color

给区间染色,求一段区间内颜色的种树。学会了线段树的新写法以及位操作。



posted @ 2010-09-18 11:15 ZAKIR 阅读(83) | 评论 (0)编辑 收藏

2010年9月9日

网络流题目记录

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的边到结束点。


posted @ 2010-09-09 17:03 ZAKIR 阅读(241) | 评论 (0)编辑 收藏

2010年8月30日

图的割点与割边学习笔记

割点

割点:如果在图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

posted @ 2010-08-30 14:59 ZAKIR 阅读(2010) | 评论 (0)编辑 收藏

2010年5月26日

新博开通!

      由于原来的yo2不能用了,只好转战CPP。这个Blog将会用来记录一些胡思乱想的成果,神经质的言语。
      形式主义的来个HelloWorld:
   
1cout<<"Hello World"<<endl;

posted @ 2010-05-26 08:15 ZAKIR 阅读(77) | 评论 (0)编辑 收藏

仅列出标题  
<2019年4月>
31123456
78910111213
14151617181920
21222324252627
2829301234
567891011

导航

统计

常用链接

留言簿

随笔档案

文章分类

文章档案

大牛们

搜索

最新评论

阅读排行榜

评论排行榜