1001: [BeiJing2006]狼抓兔子

Time Limit: 15 Sec  Memory Limit: 162 MB Submit: 24482  Solved: 6197 [][][]

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

 

这题求的是“平面s-t图”的最小割，建其对偶图跑最短路即可

具体做法参见论文

#include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;char buf[10000000], *ptr = buf - 1;inline int readint(){    int n = 0;    char ch = *++ptr;    while(ch < '0' || ch > '9') ch = *++ptr;    while(ch <= '9' && ch >= '0'){        n = (n << 1) + (n << 3) + ch - '0';        ch = *++ptr;    }    return n;}const int INF = 2147483647;struct Edge{    int to, val, next;    Edge(){}    Edge(int _t, int _v, int _n): to(_t), val(_v), next(_n){}}e[6000000];int fir[2000000] = {
    0}, cnt = 0;inline void ins(int u, int v, int w){    e[++cnt] = Edge(v, w, fir[u]); fir[u] = cnt;    e[++cnt] = Edge(u, w, fir[v]); fir[v] = cnt; }int n, m, nm;struct Node{    int dis, idx;    Node(){}    Node(int _d, int _i): dis(_d), idx(_i){}}t;class cmp{    public:        bool operator () (const Node &a, const Node &b){            return a.dis > b.dis;        }};priority_queue
          
           , cmp> pq;int S, T;bool state[2000000];int dis[2000000];int dijkstra(){    for(int i = T; i; i--){        dis[i] = INF;        state[i] = false;    }    dis[S] = 0;    pq.push(Node(0, S));    int u, v;    while(!pq.empty()){        t = pq.top(); pq.pop();        if(state[t.idx]) continue;        u = t.idx;        state[u] = true;        for(int i = fir[u]; i; i = e[i].next){            v = e[i].to;            if(dis[v] > dis[u] + e[i].val){                dis[v] = dis[u] + e[i].val;                pq.push(Node(dis[v], v));            }        }    }}int main(){    fread(buf, sizeof(char), sizeof(buf), stdin);    n = readint();    m = readint();    if(n != 1 && m != 1){        nm = (n - 1) * (m - 1);        S = 2 * nm + 1;        T = S + 1;        int u, v;        for(int i = 1; i <= n; i++)            for(int j = 1; j < m; j++){                u = i == 1 ? T : (i - 2) * (m - 1) + j + nm;                v = i == n ? S : (i - 1) * (m - 1) + j;                ins(u, v, readint());            }        for(int i = 1; i < n; i++)            for(int j = 1; j <= m; j++){                u = j == 1 ? S : (i - 1) * (m - 1) + j - 1;                v = j == m ? T : (i - 1) * (m - 1) + j + nm;                ins(u, v, readint());            }        for(int i = 1; i < n; i++)            for(int j = 1; j < m; j++){                u = (i - 1) * (m - 1) + j;                v = u + nm;                ins(u, v, readint());            }        dijkstra();        printf("%d\n", dis[T]);    }    else{        int ans = INF;        if(m == 1) swap(n, m);        for(int i = 1; i < m; i++)            ans = min(ans, readint());        printf("%d\n", ans);    }    return 0;}
          
         
        
       
      

其实网络流写得好的话也可以过，不过是$1000000$个点和$3000000$条边而已

效率还不输于建对偶图