[ICPC-Beijing 2006]狼抓兔子


题目链接:Luogu4001


Description
现在小朋友们最喜欢的”喜羊羊与灰太狼”,话说灰太狼抓羊不到,但抓兔子还是比较在行的,而且现在的兔子还比较笨,它们只有两个窝,现在你做为狼王,面对下面这样一个网格的地形:
https://cdn.luogu.org/upload/pic/11942.png
左上角点为(1,1),右下角点为(N,M)(上图中N=3,M=4).有以下三种类型的道路
1:(x,y)<==>(x+1,y)
2:(x,y)<==>(x,y+1)
3:(x,y)<==>(x+1,y+1)
道路上的权值表示这条路上最多能够通过的兔子数,道路是无向的. 左上角和右下角为兔子的两个窝,开始时所有的兔子都聚集在左上角(1,1)的窝里,现在它们要跑到右下角(N,M)的窝中去,狼王开始伏击这些兔子.当然为了保险起见,如果一条道路上最多通过的兔子数为K,狼王需要安排同样数量的K只狼,才能完全封锁这条道路,你需要帮助狼王安排一个伏击方案,使得在将兔子一网打尽的前提下,参与的狼的数量要最小。因为狼还要去找喜羊羊麻烦。


Input
第一行为N,M.表示网格的大小,N,M均小于等于1000.
接下来分三部分
第一部分共N行,每行M-1个数,表示横向道路的权值.
第二部分共N-1行,每行M个数,表示纵向道路的权值.
第三部分共N-1行,每行M-1个数,表示斜向道路的权值.


Output
输出一个整数,表示参与伏击的狼的最小数量.


Sample Input 1
3 4
5 6 4
4 3 1
7 5 3
5 6 7 8
8 7 6 5
5 5 5
6 6 6


Sample Output 1
14


Solution
练习平面图转对偶图写的题
也是一句话题解:转成对偶图跑最短路
不过不知道是不是我这种建图方式有点小问题
当n或m为1的时候出不了正解需要特判


如何建对偶图?
具体的建图过程可以点开下面这个链接qwq
平面图转对偶图


Code

#include<map>
#include<set>
#include<list>
#include<queue>
#include<vector>
#include<string>
#include<time.h>
#include<math.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#include<algorithm>
//#define Judge
//#define Online
#define reg register
#define ll long long
#define mod 1000000007
#define inf 2147483647
#define lowbit(x) ((x)&-(x))
#define abs(x) ((x)<0?-(x):(x))
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define isd(c) ('0'<=(c)&&(c)<='9')
#define isa(c) ('a'<=(c)&&(c)<='z')
#define isA(c) ('A'<=(c)&&(c)<='Z')
#define ckmax(a,b) ((a)=max((a),(b)))
#define ckmin(a,b) ((a)=min((a),(b)))
using namespace std;
#ifdef Judge
#define puts io.put
#define getchar io.gc
#define putchar io.wchar
#ifdef Online
FILE*in=stdin;
FILE*out=stdout;
#else
FILE*in=fopen(".in","r+");
FILE*out=fopen(".out","w+");
#endif
struct FastIO{
    #define S 1000000
    int wpos,len,pos;char wbuf[S],buf[S];
    FastIO(){wpos=0,len=0,pos=0;}
    inline char gc(){
        if (pos==len) pos=0,len=fread(buf,1,S,in);
        if (pos==len) return 0; return buf[pos++];
    }
    inline void wchar(int x) {
        if (wpos==S) fwrite(wbuf,1,S,out),wpos=0;
        wbuf[wpos++]=x;
    }
    inline void put(const char*s) {for(; *s; ) wchar(*s++);}
    ~FastIO() {
        if (wpos) fwrite(wbuf,1,wpos,out),wpos=0;
    }
}io;
#endif
template<typename T> inline void read(T&x){T f=1;x=0;char c;
    for (c=getchar(); !isd(c); c=getchar()) f=(c=='-')?-1:f;
    for (; isd(c); c=getchar()) x=(x<<3)+(x<<1)+(c^48);x*=f;
}
template<typename T> inline void wt(T x,char c=0){char ch[(sizeof(T)+1)<<1];if (x<0) x=-x,putchar('-');
    int t=-1; do ch[++t]=x%10+'0',x/=10; while(x); do putchar(ch[t]); while(t--); if (c!=0) putchar(c);
}
#define maxn 2010
int n,m,S,T;
int fir[maxn*maxn],nxt[maxn*maxn*6],to[maxn*maxn*6],flow[maxn*maxn*6],dis[maxn*maxn],vis[maxn*maxn],cnt;
inline void ins(int x,int y,int v){
    nxt[++cnt]=fir[x],fir[x]=cnt,to[cnt]=y,flow[cnt]=v;
    nxt[++cnt]=fir[y],fir[y]=cnt,to[cnt]=x,flow[cnt]=v;
}
struct cmp{
    inline int operator()(int x,int y)const{
        return dis[x]>dis[y];
    }
};
inline void Dijkstra(){
    memset(dis,127,sizeof dis);
    priority_queue<int,vector<int>,cmp> q;q.push(S),dis[S]=0,vis[S]=1;
    while(!q.empty()){
        int now=q.top();q.pop(),vis[now]=0;
        for (int i=fir[now]; i; i=nxt[i]){
            if (dis[now]+flow[i]<dis[to[i]]){
                dis[to[i]]=dis[now]+flow[i];
                if (!vis[to[i]]) vis[to[i]]=1,q.push(to[i]);
            }
        }
    }
}
inline void Init(){
    read(n),read(m);T=(n-1)*(m-1)*2+1;
    if (n==1||m==1) {//特判
        int ans=-1;
        for (int i=1,g=m+n-2; i<=g; ++i) {
            int x;read(x);
            ans=ans==-1?x:min(ans,x);
        }
        wt(ans,'\n');
        exit(0);
    }
    for (int i=1; i<=n; ++i){
        for (int j=1; j<m; ++j){
            int v; read(v);
            if (i==1) ins(S,j*2,v);
            else if (i==n) ins((i-2)*(m-1)*2+j*2-1,T,v);
            else ins((i-2)*(m-1)*2+j*2-1,(i-1)*(m-1)*2+j*2,v);
        }
    }
    for (int i=1; i<n; ++i){
        for (int j=1; j<=m; ++j){
            int v; read(v);
            if (j==1) ins(2*(m-1)*(i-1)+1,T,v);
            else if (j==m) ins(S,2*(m-1)*i,v);
            else ins(2*(i-1)*(m-1)+2*(j-1),2*(i-1)*(m-1)+2*(j-1)+1,v);
        }
    }
    int cnt=0;
    for (int i=1; i<n; ++i){
        for (int j=1; j<m; ++j){
            int v; read(v);
            ins(cnt+1,cnt+2,v);cnt+=2;
        }
    }
}
int main(int argv,char*argc[]){
    Init();Dijkstra();wt(dis[T],'\n');return 0;
}


点我回到主页

One thought on “[ICPC-Beijing 2006]狼抓兔子

  1. Pingback引用通告: 平面图转对偶图 – TaK-Vin

发表评论

Fill in your details below or click an icon to log in:

WordPress.com 徽标

You are commenting using your WordPress.com account. Log Out /  更改 )

Google photo

You are commenting using your Google account. Log Out /  更改 )

Twitter picture

You are commenting using your Twitter account. Log Out /  更改 )

Facebook photo

You are commenting using your Facebook account. Log Out /  更改 )

Connecting to %s