[BZOJ1001] [Beijing2006] 狼抓兔子 (最短路)

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新加数据一组，可能会卡掉从前可以过的程序。

Solution

　　乍一看是一道网络流的题，但是实际写完会发现超时超到姥姥家去了。

　　定理：平面图的最大流=该图对偶图的最短路，某形象解释见某贴心神犇

　　之后SPFA乱搞或Dijkstra乱搞，不过我建边的方式有点鬼畜。

 #include <cstdio>
 #include <cstring>
 using namespace std;
 struct node
 {
     int v, w;
 }edge[];
 int fst[], nxt[], sss, ttt, dis[], q[], front, back;
 bool inq[];

 void qscanf(int &x)
 {
     char c = getchar();
     x = ;
     while(c < '' || c > '')
         c = getchar();
     while(c >= '' && c <= '')
         x = x *  + c - '', c = getchar();
 }

 void addedge(int i, int u, int v, int w)
 {
     edge[i << ] = (node){v, w}, nxt[i << ] = fst[u], fst[u] = i << ;
     edge[i <<  | ] = (node){u, w}, nxt[i <<  | ] = fst[v], fst[v] = i <<  | ;
 }

 void SPFA()
 {
     memset(dis, , sizeof(dis));
     dis[sss] = , inq[sss] = q[++back] = sss;
     while(front != back)
     {
         int u = q[++front % ];
         inq[u] = false, front %= ;
         for(int i = fst[u]; i; i = nxt[i])
         {
             int v = edge[i].v, w = edge[i].w;
             if(dis[v] > dis[u] + w)
             {
                 dis[v] = dis[u] + w;
                 if(!inq[v])
                 {
                     dis[v] = dis[u] + w;
                     inq[v] = true;
                     q[++back % ] = v;
                     back %= ;
                 }
             }
         }
     }
 }

 int main()
 {
     int n, m, etot = ;
     qscanf(n), qscanf(m);
     n--, m--;
     if(n && m)
     {
         sss = n * m *  + , ttt = n * m *  + ;
         for(int i = ; i <= n + ; i++)
             for(int j = ; j <= m; j++)
             {
                 int u = ((i - ) * m + j) *  - , v = ((i - ) * m + j) * , w;
                 qscanf(w);
                 if(i == )
                     addedge(++etot, sss, v, w);
                 else if(i == n + )
                     addedge(++etot, u, ttt, w);
                 else
                     addedge(++etot, u, v, w);
             }
         for(int i = ; i <= n; i++)
             for(int j = ; j <= m + ; j++)
             {
                 int u = ((i - ) * m + j) *  - , v = ((i - ) * m + j) *  - , w;
                 qscanf(w);
                 if(j == )
                     addedge(++etot, ttt, v, w);
                 else if(j == m + )
                     addedge(++etot, u, sss, w);
                 else
                     addedge(++etot, u, v, w);
             }
         for(int i = ; i <= n; i++)
             for(int j = ; j <= m; j++)
             {
                 int u = ((i - ) * m + j) *  - , v = ((i - ) * m + j) * , w;
                 qscanf(w), addedge(++etot, u, v, w);
             }
         SPFA();
     }
     else
     {
         if(m)
             n = m;
         dis[ttt] = ;
         for(int i = ; i <= n; i++)
         {
             qscanf(fst[i]);
             if(dis[ttt] > fst[i])
                 dis[ttt] = fst[i];
         }
     }
     printf("%d\n", dis[ttt]);
     return ;
 }