danihao123

搜索

音乐播放器

RSS

RSS Link

计数器

29171
[CodeVS 1191]数轴染色
[POJ 2104]K-th Number

[BZOJ 1001]狼抓兔子

danihao123 posted @ 2016年2月04日 12:15 in 题解 with tags dijkstra bzoj 省选 最小割 BJOI 平面图转对偶图 pb_ds , 388 阅读
转载请注明出处:http://danihao123.is-programmer.com/

终于A了!

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

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

zzs在此列出此题坑点,望后人警觉:

  1. 最好写一个定位函数,不然点的位置很容易混。
  2. 不要用SPFA,不然会被卡。
  3. m等于1或n等于1的情况需要特判!
  4. 不要用边表,内存开销太惊人……
  5. 用邻接表的话,不要像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;
}
zdw1999 说:
Feb 11, 2016 08:10:45 PM

不要用SPFA——黄学长表示不服OAQ

Avatar_small
danihao123 说:
Feb 12, 2016 01:03:54 PM

@zdw1999: 有位朋友告诉我这题卡SPFA,还有神犇您是?

zdw1999 说:
Feb 12, 2016 01:07:16 PM

@danihao123: 哇哇哇%%%%%%,我这种蒟蒻竟然有人叫我神犇。。其实这题我也是用的dij+heap,这题卡SPFA也没错,然而hzwer确实用SPFA跑过去了。。可啪

danihao123 说:
Feb 12, 2016 04:46:08 PM

@zdw1999: 据说有人用Dinic都跑过去了。还有你怎么发现我的Blog的?

zdw1999 说:
Feb 12, 2016 04:47:42 PM

@danihao123: 在黄学长的博客上乱转悠,然后看到你的求加友链,然后就过来玩了2333333

Menci 说:
Apr 06, 2016 08:03:26 PM

2333333 我不会告诉你这题是 Dinic 水题 23333333333333

Avatar_small
danihao123 说:
Aug 03, 2016 05:12:07 PM

@Menci: 我不会告诉你我不会敲Dinic 233333333333333333333


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter