USACO 4-2-2 The Perfect Stall --网络流dinic算法
利用这题学习了下dinic.题意就不说了,很容易理解的一题
以前网络流的算法一直只懂最白痴的EK,后来大家说sap是万能的,于是就想学学sap,可是找了些资料之后发现我先学会的是dinic.下面说说我的理解吧.如有错误还请指出.
首先说明下层次图的概念:对原图的每一个点设置一个层次,这个新图就成了所谓的层次图了.然后允许弧就是层次图中有边且原图中也有边的弧.
dinic就是利用层次图,然后每次找增广路径的时候就只走允许弧,如果单纯这样的话,个人认为和EK算法还是差不了多少的,毕竟dinic也是多次bfs然后再dfs找增广路,那我不还如EK呢,何况EK还简单不易写错.dinic的精华应该是退栈,也就是dfs找到一条增广路之后,并不是再从源点开始找一次,而是退到从源点可达的最远一个点[这样说来很抽象]比如下面的例子
ab = 10 bc = 5 cd = 5 bf=5 fd=5 de=10[abcdef是顶点]
那么源点是a汇点是f的话
栈中情况是a->ab->abc->abcd->abcde–增广—然后退到b因为b是栈中a现在能够到达的最远的顶点了.现在从b开始增广就会出现时ab->abf->abfd->abfde—增广也就是dinic的精华在这里;具体的大家可以看2007年王上欣的论文<浅谈基于分层思想的网络流算法>
下面给出我的一份代码,经供参考
/
ID:qcx97811
LANG:C
TASK:stall4
/
#include
#include
#include
#include
ID:qcx97811
LANG:C
TASK:stall4
/
#include
#include
#include
#include
int N,M,maxflow//N和M是题目中的意思 maxflow就是最大流的值
int graph[406][406],pre[406],d[406];//graph是图 pre是每个节点的前驱 d表示每个节点的层次
int outdegree(int now)
{//返回传入顶点的出度包括在层次图中的信息
int i,out
out = 0//out代表传入顶点的出度
for(i = 0i <= (N+M+1);i++)
if(((d[now] + 1) == d[i]) & graph[now][i] > 0)
{//这里用break是因为只需要知道出度是否为0 不需要知道度为多少
out++
break
}
return out
}
int dinic()
{
int rear,front,u,out,i,top,add
int q[406];
maxflow = 0
while(1)
{
//通过bfs重构层次图
memset(d,-1,sizeof(d));
memset(pre,-1,sizeof(pre));
d[0] = pre[0] = 0//这里pre数组相当于一个bool数组记录某个顶点是否被用
rear = front = -1
rear++
q[rear] = 0
while(front < rear)
{//bfs构建层次图
u = q[++front];
for(i = 0i <= (N+M+1);i++)
{
if(-1 == pre[i] & graph[u][i] > 0)
{//如果这个点没有被用而且残留网络中有边
pre[i] = u//记录当前顶点已经被用
d[i] = d[u] + 1//层次加1
rear++//入队
q[rear] = i
}
}
}
<span style="font-weight: bold; color: #b0c4de;">if</span>(<span style="color: #f5deb3;">-</span><span style="color: #add8e6;">1</span> <span style="color: #f5deb3;">==</span> <span style="color: #f5deb3;">pre</span><span style="color: #f5deb3;">[</span>N<span style="color: #f5deb3;">+</span><span style="color: #f5deb3;">M</span><span style="color: #f5deb3;">+</span><span style="color: #add8e6;">1</span><span style="color: #f5deb3;">])</span>
<span style="font-weight: bold; color: #b0c4de;">break</span><span style="color: #da70d6;">//如果汇点不在层次图中标明已无增广路径</span>
<span style="color: #f5deb3;">out</span> <span style="color: #f5deb3;">=</span> <span style="color: #f5deb3;">outdegree</span>(<span style="color: #add8e6;">0</span>);
<span style="color: #f5deb3;">top</span> <span style="color: #f5deb3;">=</span> <span style="color: #add8e6;">0</span>
<span style="color: #f5deb3;">q</span><span style="color: #f5deb3;">[</span><span style="color: #f5deb3;">top</span><span style="color: #f5deb3;">]</span> <span style="color: #f5deb3;">=</span> <span style="color: #add8e6;">0</span><span style="color: #da70d6;">//这里的q是用来记录增广路径上的点</span>
<span style="font-weight: bold; color: #b0c4de;">while</span>(<span style="color: #f5deb3;">out</span>)<span style="color: #da70d6;">//循环直到源点的出度为0</span>
<span style="color: #f5deb3;">{</span>
<span style="color: #f5deb3;">u</span> <span style="color: #f5deb3;">=</span> <span style="color: #f5deb3;">q</span><span style="color: #f5deb3;">[</span><span style="color: #f5deb3;">top</span><span style="color: #f5deb3;">];</span><span style="color: #da70d6;">//取栈顶元素</span>
<span style="font-weight: bold; color: #b0c4de;">if</span>((N<span style="color: #f5deb3;">+</span><span style="color: #f5deb3;">M</span><span style="color: #f5deb3;">+</span><span style="color: #add8e6;">1</span>) <span style="color: #f5deb3;">==</span> <span style="color: #f5deb3;">u</span>)<span style="color: #da70d6;">//如果已经找到一条增广路径</span>
<span style="color: #f5deb3;">{</span><span style="color: #da70d6;">//增广 然后队列回退到从源点可达的最远点</span>
<span style="color: #f5deb3;">add</span> <span style="color: #f5deb3;">=</span> <span style="color: #f5deb3;">INT_MAX</span>
<span style="font-weight: bold; color: #b0c4de;">for</span>(<span style="color: #f5deb3;">i</span> <span style="color: #f5deb3;">=</span> <span style="color: #add8e6;">0</span><span style="color: #f5deb3;">i</span> <span style="color: #f5deb3;"><</span> <span style="color: #f5deb3;">top</span>;<span style="color: #f5deb3;">i</span><span style="color: #f5deb3;">++</span>)
<span style="color: #f5deb3;">{</span><span style="color: #da70d6;">//判定本次可增广的流量</span>
<span style="font-weight: bold; color: #b0c4de;">if</span>(<span style="color: #f5deb3;">graph</span><span style="color: #f5deb3;">[</span><span style="color: #f5deb3;">q</span><span style="color: #f5deb3;">[</span><span style="color: #f5deb3;">i</span><span style="color: #f5deb3;">]][</span><span style="color: #f5deb3;">q</span><span style="color: #f5deb3;">[</span><span style="color: #f5deb3;">i</span><span style="color: #f5deb3;">+</span><span style="color: #add8e6;">1</span><span style="color: #f5deb3;">]]</span> <span style="color: #f5deb3;"><</span> <span style="color: #f5deb3;">add</span>)
<span style="color: #f5deb3;">{</span>
<span style="color: #f5deb3;">add</span> <span style="color: #f5deb3;">=</span> <span style="color: #f5deb3;">graph</span><span style="color: #f5deb3;">[</span><span style="color: #f5deb3;">q</span><span style="color: #f5deb3;">[</span><span style="color: #f5deb3;">i</span><span style="color: #f5deb3;">]][</span><span style="color: #f5deb3;">q</span><span style="color: #f5deb3;">[</span><span style="color: #f5deb3;">i</span><span style="color: #f5deb3;">+</span><span style="color: #add8e6;">1</span><span style="color: #f5deb3;">]];</span>
<span style="color: #f5deb3;">}</span>
<span style="color: #f5deb3;">}</span>
<span style="font-weight: bold; color: #b0c4de;">for</span>(<span style="color: #f5deb3;">i</span> <span style="color: #f5deb3;">=</span> <span style="color: #add8e6;">0</span><span style="color: #f5deb3;">i</span> <span style="color: #f5deb3;"><</span> <span style="color: #f5deb3;">top</span>;<span style="color: #f5deb3;">i</span><span style="color: #f5deb3;">++</span>)
<span style="color: #f5deb3;">{</span><span style="color: #da70d6;">//更新残留网络</span>
<span style="color: #f5deb3;">graph</span><span style="color: #f5deb3;">[</span><span style="color: #f5deb3;">q</span><span style="color: #f5deb3;">[</span><span style="color: #f5deb3;">i</span><span style="color: #f5deb3;">]][</span><span style="color: #f5deb3;">q</span><span style="color: #f5deb3;">[</span><span style="color: #f5deb3;">i</span><span style="color: #f5deb3;">+</span><span style="color: #add8e6;">1</span><span style="color: #f5deb3;">]]</span> <span style="color: #f5deb3;">-=</span> <span style="color: #f5deb3;">add</span>
<span style="color: #f5deb3;">graph</span><span style="color: #f5deb3;">[</span><span style="color: #f5deb3;">q</span><span style="color: #f5deb3;">[</span><span style="color: #f5deb3;">i</span><span style="color: #f5deb3;">+</span><span style="color: #add8e6;">1</span><span style="color: #f5deb3;">]][</span><span style="color: #f5deb3;">q</span><span style="color: #f5deb3;">[</span><span style="color: #f5deb3;">i</span><span style="color: #f5deb3;">]]</span> <span style="color: #f5deb3;">+=</span> <span style="color: #f5deb3;">add</span>
<span style="color: #f5deb3;">}</span>
<span style="color: #f5deb3;">maxflow</span> <span style="color: #f5deb3;">+=</span> <span style="color: #f5deb3;">add</span><span style="color: #da70d6;">//增加网络流量</span>
<span style="color: #da70d6;">//下面回退到从源点可达的最远的一个点</span>
<span style="font-weight: bold; color: #b0c4de;">for</span>(<span style="color: #f5deb3;">i</span> <span style="color: #f5deb3;">=</span> <span style="color: #add8e6;">0</span><span style="color: #f5deb3;">i</span> <span style="color: #f5deb3;"><=</span> <span style="color: #f5deb3;">top</span>;<span style="color: #f5deb3;">i</span><span style="color: #f5deb3;">++</span>)
<span style="color: #f5deb3;">{</span>
<span style="font-weight: bold; color: #b0c4de;">if</span>(<span style="color: #f5deb3;">outdegree</span>(<span style="color: #f5deb3;">q</span><span style="color: #f5deb3;">[</span><span style="color: #f5deb3;">i</span><span style="color: #f5deb3;">])</span> <span style="color: #f5deb3;">==</span> <span style="color: #add8e6;">0</span>)
<span style="color: #f5deb3;">{</span><span style="color: #da70d6;">//这里不应该只考虑出度还应该考虑和q中的下一个元素是否有边(包括层次图和残留网络)</span>
<span style="color: #f5deb3;">top</span> <span style="color: #f5deb3;">=</span> <span style="color: #f5deb3;">i</span><span style="color: #f5deb3;">-</span><span style="color: #add8e6;">1</span><span style="color: #da70d6;">//这个地方如果出现top=-1应该也没问题的 因为这样的话out已经为0了</span>
<span style="font-weight: bold; color: #b0c4de;">break</span>
<span style="color: #f5deb3;">}</span>
<span style="font-weight: bold; color: #b0c4de;">if</span>(<span style="color: #f5deb3;">graph</span><span style="color: #f5deb3;">[</span><span style="color: #f5deb3;">q</span><span style="color: #f5deb3;">[</span><span style="color: #f5deb3;">i</span><span style="color: #f5deb3;">]][</span><span style="color: #f5deb3;">q</span><span style="color: #f5deb3;">[</span><span style="color: #f5deb3;">i</span><span style="color: #f5deb3;">+</span><span style="color: #add8e6;">1</span><span style="color: #f5deb3;">]]</span> <span style="color: #f5deb3;"><=</span> <span style="color: #add8e6;">0</span>)
<span style="color: #f5deb3;">{</span><span style="color: #da70d6;">//这个是防止某个点出度不为0但是q中这个点和下一个点的边已经为0了 那么就会一直死循环在里面这个while里</span>
<span style="color: #f5deb3;">top</span> <span style="color: #f5deb3;">=</span> <span style="color: #f5deb3;">i</span>
<span style="font-weight: bold; color: #b0c4de;">break</span>
<span style="color: #f5deb3;">}</span>
<span style="color: #f5deb3;">}</span>
<span style="color: #f5deb3;">}</span>
<span style="font-weight: bold; color: #b0c4de;">else</span>
<span style="color: #f5deb3;">{</span>
<span style="font-weight: bold; color: #b0c4de;">if</span>(<span style="color: #f5deb3;">outdegree</span>(<span style="color: #f5deb3;">u</span>) <span style="color: #f5deb3;">></span> <span style="color: #add8e6;">0</span>)
<span style="color: #f5deb3;">{</span><span style="color: #da70d6;">//该点的出度不为0 则改变队列 把当前顶点入队这里的出度包括层次图的信息</span>
<span style="font-weight: bold; color: #b0c4de;">for</span>(<span style="color: #f5deb3;">i</span> <span style="color: #f5deb3;">=</span> <span style="color: #add8e6;">0</span><span style="color: #f5deb3;">i</span> <span style="color: #f5deb3;"><=</span> (N<span style="color: #f5deb3;">+</span><span style="color: #f5deb3;">M</span><span style="color: #f5deb3;">+</span><span style="color: #add8e6;">1</span>);<span style="color: #f5deb3;">i</span><span style="color: #f5deb3;">++</span>)
<span style="color: #f5deb3;">{</span><span style="color: #da70d6;">//寻找u顶点的下一个顶点</span>
<span style="font-weight: bold; color: #b0c4de;">if</span>(<span style="color: #f5deb3;">d</span><span style="color: #f5deb3;">[</span><span style="color: #f5deb3;">u</span><span style="color: #f5deb3;">]</span><span style="color: #f5deb3;">+</span><span style="color: #add8e6;">1</span> <span style="color: #f5deb3;">==</span> <span style="color: #f5deb3;">d</span><span style="color: #f5deb3;">[</span><span style="color: #f5deb3;">i</span><span style="color: #f5deb3;">]</span> <span style="color: #f5deb3;">&</span> <span style="color: #f5deb3;">graph</span><span style="color: #f5deb3;">[</span><span style="color: #f5deb3;">u</span><span style="color: #f5deb3;">][</span><span style="color: #f5deb3;">i</span><span style="color: #f5deb3;">]</span> <span style="color: #f5deb3;">></span> <span style="color: #add8e6;">0</span>)
<span style="color: #f5deb3;">{</span>
<span style="color: #f5deb3;">top</span><span style="color: #f5deb3;">++</span><span style="color: #da70d6;">//入栈</span>
<span style="color: #f5deb3;">q</span><span style="color: #f5deb3;">[</span><span style="color: #f5deb3;">top</span><span style="color: #f5deb3;">]</span> <span style="color: #f5deb3;">=</span> <span style="color: #f5deb3;">i</span>
<span style="font-weight: bold; color: #b0c4de;">break</span>
<span style="color: #f5deb3;">}</span>
<span style="color: #f5deb3;">}</span>
<span style="color: #f5deb3;">}</span>
<span style="font-weight: bold; color: #b0c4de;">else</span>
<span style="color: #f5deb3;">{</span><span style="color: #da70d6;">//弹出队列的最高顶点</span>
<span style="color: #f5deb3;">d</span><span style="color: #f5deb3;">[</span><span style="color: #f5deb3;">u</span><span style="color: #f5deb3;">]</span> <span style="color: #f5deb3;">=</span> <span style="color: #f5deb3;">-</span><span style="color: #add8e6;">1</span><span style="color: #da70d6;">//当前顶点从层次图中删除</span>
<span style="color: #f5deb3;">top</span><span style="color: #f5deb3;">--</span><span style="color: #da70d6;">//从栈中删除</span>
<span style="color: #f5deb3;">}</span>
<span style="color: #f5deb3;">}</span>
<span style="color: #f5deb3;">out</span> <span style="color: #f5deb3;">=</span> <span style="color: #f5deb3;">outdegree</span>(<span style="color: #add8e6;">0</span>);<span style="color: #da70d6;">//判定当前源点的出度</span>
<span style="color: #f5deb3;">}</span>
<span style="color: #f5deb3;">}</span>
}
int main(void)
{
freopen(“stall4.in”,“r”,stdin);
freopen(“stall4.out”,“w”,stdout);
int i,j,ct,c
memset(graph,0,sizeof(graph));
scanf(“%d%d”,N,&M);
/下面是初始化图/
for(i = 1i <= N;i++)
{
scanf(“%d”,ct);
for(j = 0j < ct;j++)
{
scanf(“%d”,c);
graph[i][c+N] = 1
}
}
for(i = 1i <= N;i++)
graph[0][i] = 1
for(i = N+1i <= (N+M);i++)
graph[i][N+M+1] = 1
/上面是初始化图/
dinic();//调用dinic求最大流
printf(“%d\n“,maxflow);//输出最大流
return 0
}
