[BZOJ 1001]狼抓兔子

danihao123 posted @ 2016年2月04日 12:15 in 题解 with tags dijkstra bzoj 省选最小割 BJOI 平面图转对偶图 pb_ds , 1410 阅读

转载请注明出处：http://danihao123.is-programmer.com/

终于A了！

再给大家欣赏一下zzs这个逗比百折不挠的卡评记录（一页半慎看）：

这道题就是平面图转对偶图的恶心题~

zzs在此列出此题坑点，望后人警觉：

最好写一个定位函数，不然点的位置很容易混。
不要用SPFA，不然会被卡。
m等于1或n等于1的情况需要特判！
不要用边表，内存开销太惊人……
用邻接表的话，不要像zzs这个逗比一样开小内存……

代码：

/**************************************************************
    Problem: 1001
    User: danihao123
    Language: C++
    Result: Accepted
    Time:2680 ms
    Memory:94668 kb
****************************************************************/
 
#include <cstdio>
#include <vector>
#include <cstring>
#include <utility>
#include <ext/pb_ds/priority_queue.hpp>
#include <bitset>
using namespace std;
const int maxn=1996003,maxm=5992003;
// 图相关
int cnt=0;
int dist[maxm],to[maxm],next[maxm],first[maxn];
void Add_Edge(int x,int y,int z){
    next[cnt]=first[x];
    first[x]=cnt;
    to[cnt]=y;
    dist[cnt]=z;
    cnt++;
}
inline bool isdigit(char c){
    return c>='0' && c<='9';
}
// I/O优化
inline int readint(){
    register int x=0;
    char c=getchar();
    while(!isdigit(c))
        c=getchar();
    while(isdigit(c)){
        x=x*10+c-'0';
        c=getchar();
    }
    return x;
}
// 读入并建图（以及相关函数）
int n,m,t,ans=0;
inline int Get_Point(int x,int y,int d){
    return (x-1)*(m-1)*2+2*y-1+d;
}
void read_graph(){
    register int i,j,d,u,v;
    n=readint();
    m=readint();
    t=(m-1)*(n-1)*2+1;
    memset(first,-1,sizeof(first));
    if(m==1 || n==1){
        ans=0xfffffff;
        if(m==1)
            j=n;
        else
            j=m;
        for(i=1;i<j;i++){
            scanf("%d",&d);
            if(d<ans)
                ans=d;
        }
        return;
    }
    for(i=1;i<m;i++){
        d=readint();
        u=Get_Point(1,i,0);
        Add_Edge(u,t,d);
        Add_Edge(t,u,d);
    }
    for(i=1;i<(n-1);i++){
        for(j=1;j<m;j++){
            d=readint();
            u=Get_Point(i,j,1);
            v=Get_Point(i+1,j,0);
            Add_Edge(u,v,d);
            Add_Edge(v,u,d);
        }
    }
    for(i=1;i<m;i++){
        d=readint();
        u=Get_Point(n-1,i,1);
        Add_Edge(u,0,d);
        Add_Edge(0,u,d);
    }
    for(i=1;i<n;i++){
        d=readint();
        u=Get_Point(i,1,1);
        Add_Edge(u,0,d);
        Add_Edge(0,u,d);
        for(j=2;j<=(m-1);j++){
            d=readint();
            u=Get_Point(i,j,1);
            v=Get_Point(i,j-1,0);
            Add_Edge(u,v,d);
            Add_Edge(v,u,d);
        }
        d=readint();
        u=Get_Point(i,m-1,0);
        Add_Edge(u,t,d);
        Add_Edge(t,u,d);
    }
    for(i=1;i<n;i++)
        for(j=1;j<m;j++){
            d=readint();
            u=Get_Point(i,j,0);
            v=Get_Point(i,j,1);
            Add_Edge(u,v,d);
            Add_Edge(v,u,d);
        }
}
int d[maxn];
bitset<maxn> vis;
typedef pair<int,int> my_pair;
typedef __gnu_pbds::priority_queue<my_pair,greater<my_pair> > Heap;
Heap::point_iterator ite[maxn];
Heap Q;
int dij(){
    register int i,u;
    memset(d,0x7f,sizeof(d));
    d[0]=0;
    ite[0]=Q.push(make_pair(0,0));
    while(!Q.empty()){
        u=Q.top().second;
        Q.pop();
        if(vis[u])
            continue;
        vis[u]=true;
        for(i=first[u];i!=-1;i=next[i]){
            if(d[to[i]]>(dist[i]+d[u])){
                d[to[i]]=dist[i]+d[u];
                if(ite[to[i]]!=0)
                    Q.modify(ite[to[i]],make_pair(d[to[i]],to[i]));
                else
                    ite[to[i]]=Q.push(make_pair(d[to[i]],to[i]));
            }
        }
    }
    return d[t];
}
int main(){
    read_graph();
    if(ans)
        printf("%d\n",ans);
    else
        printf("%d\n",dij());
    return 0;
}