Submit: 21218  Solved: 5311

[][][]

Description

现在小朋友们最喜欢的"喜羊羊与灰太狼",话说灰太狼抓羊不到，但抓兔子还是比较在行的，

而且现在的兔子还比较笨，它们只有两个窝，现在你做为狼王，面对下面这样一个网格的地形：

 

左上角点为(1,1),右下角点为(N,M)(上图中N=4,M=5).有以下三种类型的道路 

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个数，表示斜向道路的权值. 

输入文件保证不超过10M

Output

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

Sample Input

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

14

HINT

 

 2015.4.16新加数据一组，可能会卡掉从前可以过的程序。

思路：最小割转最大流

然而我的第二种方法本来应该更偏向于正解，却被bzoj的极限数据T掉了，可能是我技巧不够高吧。

170404：对偶图重新构图+最短路看起来更吊，然而结果得不偿失。

代码实现：

Accepted

129728 kb

1512 ms

/

1775 B

2017-03-18 08:50:39

1 #include
      
        2 #include
       
         3 #define inf 1000000000 4 int n,m,s,t,ans; 5 int a,b,c,hs=1,head,tail; 6 int h[3000010],d[3000010],q[3000010]; 7 struct edge{
    int s,n,w;}e[8000010]; 8 inline int min(int x,int y){
    return y
        
         '9');13     l++;14     do{ch[l++]=getchar();}while(ch[l-1]>='0'&&ch[l-1]<='9');15     l-=2;16     for(int i=l,j=1;i>=0;i--,j*=10) ret+=(ch[i]-'0')*j;17     return ret;18 }19 void bfs(){20     memset(d,0,sizeof(d));21     head=tail=0;22     q[head++]=s,d[s]=1;23     while(head>tail){24         a=q[tail++];25         for(int i=h[a];i;i=e[i].n) if(!d[e[i].s]&&e[i].w){26             d[e[i].s]=d[a]+1;27             if(e[i].s==t) return;28             q[head++]=e[i].s;29         }30     }31 }32 int ap(int k,int v){33     if(k==t) return v;34     int act=v;35     for(int i=h[k];i;i=e[i].n)36     if(e[i].w&&d[e[i].s]==d[k]+1&&act){37         int ret=ap(e[i].s,min(act,e[i].w));38         if(ret) e[i].w-=ret,e[i^1].w+=ret,act-=ret;39         else d[e[i].s]=0;40     }41     return v-act;42 }43 bool Dinic(){44     bfs();45     if(!d[t]) return 0;46     ans+=ap(s,inf);47 }48 int main(){49     n=read(),m=read();50     s=1,t=n*m;51     for(int i=0;i
        
       
      

Time_Limit_Exceed

149260 kb

15784 ms

/

1651 B

2017-03-15 20:52:11

1 #include
      
        2 #include
       
         3 int n,m,s,t; 4 int a,b,c,hs=1,head,tail; 5 int h[3000010],w[3000010],q[8000010]; 6 struct edge{
    int s,n,w;}e[8000010]; 7 inline bool bj(long long x,long long y,long long z){
    return y+z
        
         '9');12     l++;13     do{ch[l++]=getchar();}while(ch[l-1]>='0'&&ch[l-1]<='9');14     l-=2;15     for(int i=l,j=1;i>=0;i--,j*=10) ret+=(ch[i]-'0')*j;16     return ret;17 }18 int main(){19     n=read(),m=read();20     s=m+1,t=2*n*m+2*n-m;21     for(int i=1;i
         
          tail){55         a=q[tail++];56         for(int i=h[a];i;i=e[i].n)57         if(bj(w[e[i].s],w[a],e[i].w)){58             w[e[i].s]=w[a]+e[i].w;59             q[head++]=e[i].s;60         }61     }62     printf("%d\n",w[t]);63     return 0;64 }65
         
        
       
      

建议先去COGS做一下，然后再去bzoj交。

题目来源：bzoj