学步园

//用它做过一些题（hdu3046,poj3469等），正确性和效率都有待改进<br /> //主要难题：如何在用邻接表表示余留网时迅速找到一条边的逆边？</p> <p>const int null = -1;<br /> const int VMAX = 40000;<br /> const int EMAX = 160000;<br /> struct Edge<br /> {<br /> int adj,next,re; //指向的点，下一边的下标，逆边的下标<br /> int r; //余留网边的容量<br /> }h[EMAX+10]; //用下标模拟指针构邻接表</p> <p>int p[VMAX+10],c; //各点的头指针，目前h数组开到的位置<br /> int Q[VMAX+10],level[VMAX+10];</p> <p>//插边，k,l为端点，cap为边容量，d为是否双向<br /> void insert(int k,int l,int cap,bool d)<br /> {<br /> h[++c].adj=l;<br /> h[c].r=cap;<br /> h[c].next=p[k];<br /> p[k]=c;<br /> h[c].re=c+1; //****解决逆边问题的技巧，多存一个逆边在h中的位置****</p> <p> //逆边<br /> h[++c].adj=k;<br /> int a=d ? cap : 0;<br /> h[c].r=a;<br /> h[c].next=p[l];<br /> p[l]=c;<br /> h[c].re=c-1; //与上面对应</p> <p>}</p> <p>//广搜求层次图<br /> bool bfs()<br /> {<br /> memset(level,-1,sizeof(level));<br /> int head=0,tail=0;<br /> Q[tail++]=s;<br /> level[s]=0;<br /> while (head<tail)<br /> {<br /> int v=Q[head++];<br /> for (int i=p[v];i!=null;i=h[i].next)<br /> {<br /> int j=h[i].adj;<br /> if (level[j]==-1 && h[i].r )<br /> {<br /> level[j]=level[v]+1;<br /> Q[tail++]=j;<br /> }<br /> }<br /> }<br /> return (level[t]!=-1);<br /> }</p> <p>//深搜扩充流<br /> int dfs(int v,int c)<br /> {<br /> if (v==t) return c; //遇汇点结束<br /> int sum=c;<br /> for (int i=p[v];i!=null && c;i=h[i].next)<br /> {<br /> int j=h[i].adj;<br /> if (h[i].r && level[j]==level[v]+1)<br /> {<br /> int a=dfs(j,min(c,h[i].r)); //递归确定本次要扩充的流大小<br /> h[i].r-=a; //增流<br /> h[h[i].re].r+=a;<br /> c-=a;<br /> }<br /> }</p> <p> return sum-c; //返回从v点扩充的流大小<br /> }<br /> //dinic<span class='wp_keywordlink'><a href="http://www.xuebuyuan.com/category/%E7%AE%97%E6%B3%95" title="算法" target="_blank">算法</a></span>主体，不断求层次图并增流，直至汇点不可达<br /> int dinic()<br /> {<br /> int ans=0;<br /> while (bfs())<br /> ans+=dfs(s,inf);<br /> return ans;<br /> }</p> <p>//初始化<br /> void init()<br /> {</p> <p> c=-1;<br /> memset(p,null,sizeof(p));<br /> //......</p> <p>}</p> <p>