BZOJ1001: [BeiJing2006]狼抓兔子 (最小割转最短路)

浅析最大最小定理在信息学竞赛中的应用---周东

↑方法介绍

对于一个联通的平面图G(满足欧拉公式) 在s和t间新连一条边e;

然后建立一个原图的对偶图G*,G*中每一个点对应原图中每一个面,每一条边对应分割面的每一条边;

那么对偶图G*中,以原图s和t间边e新划分出的面作为起点(s*),最外的面作为终点(t*);

那么从s*到t*的每一条路都是原图G的一个割;

下图来自上方标出百度文库网址的ppt;

然后用堆(优先队列)优化的迪杰斯特拉,复杂度 O((m+n)logn) n为点数,m为边数...

嗯存一个堆优化迪杰斯特拉的代码...很久以前那个没有标签的一通好找..

 #include<cmath>
 #include<cstdio>
 #include<cstring>
 #include<iostream>
 #include<algorithm>
 #include<queue>
 using namespace std;
 #define pa pair<int,int>
 int n,m,s,t;
 struct node{
     int y;
     int next;
     int v;
 }e[];
 int head[]={},tot=,dis[]={};
 bool vis[]={};
 priority_queue< pa, vector< pa >, greater< pa > >q;
 inline void init(int x,int y,int v){
     e[++tot].y=y;
     e[tot].next=head[x];
     e[tot].v=v;
     head[x]=tot;
 }
 inline int ge(int x,int y,int k){//x行,y列,在斜线的左(1)右(2);返回格子的编号
     return *(x-)*(m-)+*(y-)+k;
 }
 /*
 事实上如果按照从上到下从左到右来编号,在输入时的块编号是有规律的;
 不一定要像上面一样这样找格子编号;
 */
 void doit(){
     memset(dis,,sizeof(dis));
     int x,y;
     dis[s]=;
     q.push(make_pair(,s));
     while(!q.empty()){
         x=q.top().second;
         q.pop();
         if(vis[x]){
             continue;
         }
         vis[x]=;
         for(int i=head[x];i;i=e[i].next){
             y=e[i].y;
             if(dis[y]>dis[x]+e[i].v){
                 dis[y]=dis[x]+e[i].v;
                 vis[y]=;
                 q.push(make_pair(dis[y],e[i].y));
             }
         }
     }
 }
 int main(){
     scanf("%d%d",&n,&m);
     int v;
     t=(m-)*(n-)*+;
     s=t-;
     for(int i=;i<=n;i++){
         for(int j=;j<m;j++){
             scanf("%d",&v);
             if(i==){
                 init(s,*j,v);
                 init(*j,s,v);
             }else if(i==n){
                 init(ge(n-,j,),t,v);
                 init(t,ge(n-,j,),v);
             }else{
                 init(ge(i-,j,),ge(i,j,),v);
                 init(ge(i,j,),ge(i-,j,),v);
             }
         }
     }
     for(int i=;i<n;i++){
         for(int j=;j<=m;j++){
             scanf("%d",&v);
             if(j==){
                 init(t,ge(i,,),v);
                 init(ge(i,,),t,v);
             }else if(j==m){
                 init(ge(i,m-,),s,v);
                 init(s,ge(i,m-,),v);
             }else{
                 init(ge(i,j-,),ge(i,j,),v);
                 init(ge(i,j,),ge(i,j-,),v);
             }
         }
     }
     for(int i=;i<n;i++){
         for(int j=;j<m;j++){
             scanf("%d",&v);
             init(ge(i,j,),ge(i,j,),v);
             init(ge(i,j,),ge(i,j,),v);
         }
     }
     doit();
     printf("%d\n",dis[t]);
     return ;
 }