HDU3035-平面圖最小割轉最短路

2019-11-11 06:53:33

字體：大中小

來源：轉載

供稿：網友

PS：這是get姿勢后的第一道建圖稍微麻煩的題，居然寫完代碼沒調試一次AC了~~~哈哈~~~~

War

Time Limit: 20000/10000 MS (java/Others) Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 1386 Accepted Submission(s): 403PRoblem DescriptionCountry X is under attack by enemies. Now the army of enemy has arrived at City Y. City Y consists of an N×M grid. All the paths in the grid are bidirectional, horizontal or vertical or diagonal. The upper-left corner is (0, 0) and lower-right corner is (N, M). The army enters at (0, 0) and they must get to (N, M) in order to continue their attack to the capital of Country X. The figure below shows what does City Y looks like.

Every blackened node represents a vertex. The number beside each edge is the amount of TNT needed to destroy that road. The army of Country X is unable to beat the enemy now. The only thing they can do is to prevent them from heading to their capital so that they can have more time to prepare for striking back. Of course they want to use the least amount of TNT to disconnect (0, 0) and (N, M). You are a talented programmer, please help them decide the least amount needed. InputThere are multiple test cases.The first line of each test case contains two positive integers N and M, representing height and width of the grid.Then N+1 lines each containing M integers, giving you the amount needed of horizontal roads in row major order.Then N lines each containing M+1 integers, giving you the amount needed of vertical roads in row major order.Then 2N lines each containing 2M integers, giving you the amount needed of diagonal roads in row major order.There is a blank line after each input block. The sample input is corresponding to the figure above.Restriction:1 <= N, M <= 5001 <= amount <= 1,000,000 OutputOne line for each test case the least amount of TNT needed to disconnect (0, 0) and (N, M). Sample Input

2 31 9 41 8 76 2 37 5 4 86 2 8 710 4 1 7 5 35 4 10 2 1 96 3 2 9 5 38 9 6 3 10 10 Sample Output18 Source2009 Multi-University Training Contest 13 - Host by HIT
題目思路：
                    s-t平面圖最小割轉最短路的裸題，具體可以參見我之前寫的博客：   s-t平面圖最小割轉最短路算法
                    這題我們很容易可以得到對偶圖的點的個數為n*m*4+2 ,邊的個數為n*m*4+n*m*2+n+m-2,
                    所以如果用普通的spfa的話會超時，因此我們這里要用優先隊列優化，這里編號的話我們可以
                    以0點為S*，n*m*4+1為T*，然后中間每個大格子中的四個小格子編號可以1 2 3 4 這樣按順序排
                    從上到下，從左到右！ 注意下細節，應改建起圖還是不難的！
AC代碼：
#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<queue>using namespace std;const int maxn = 1e6+100;const int inf = 1e9;struct nod{   int v,w,nex;}edge[maxn<<2];int n,m,nn,e,k;int dis[maxn],hed[maxn];bool vis[maxn];void add(int u,int v,int w){    edge[e].v = v,edge[e].w = w,edge[e].nex = hed[u],hed[u]=e++;    edge[e].v = u,edge[e].w = w,edge[e].nex = hed[v],hed[v]=e++;}void dij(){   for(int i=0;i<=nn;i++)    dis[i]=inf,vis[i]=0;   dis[0]=0;   priority_queue<pair<int,int > >q;   q.push(make_pair(-dis[0],0));   while(!q.empty()){        int u = q.top().second;q.pop();        if(vis[u])continue;vis[u]=1;        for(int i=hed[u];~i;i=edge[i].nex){            int v = edge[i].v;            if(dis[v]>dis[u]+edge[i].w){                dis[v]=dis[u]+edge[i].w;                if(!vis[v]){                    q.push(make_pair(-dis[v],v));                }            }        }   }}int main(){    while(~scanf("%d%d",&n,&m)){        nn = n*m*4+1;e=0;        memset(hed,-1,sizeof(hed));        for(int i=1;i<=n+1;i++){            for(int j=1;j<=m;j++){                scanf("%d",&k);                if(i==1)                  //最上面的邊                    add(nn,(j-1)*4+1,k);                   else if(i==n+1)            //最下面的邊                    add(0,(n-1)*m*4+(j-1)*4+3,k);                else                       //中間水平的邊                    add((i-2)*m*4+(j-1)*4+3,(i-1)*m*4+(j-1)*4+1,k);            }        }        for(int i=1;i<=n;i++){            for(int j=1;j<=m+1;j++){                scanf("%d",&k);                if(j==1)                 //最左面的邊                    add(0,(i-1)*m*4+2,k);                else if(j==m+1)            //最右面的邊                    add(nn,i*m*4,k);                else                        //中間垂直的邊                    add((i-1)*m*4+(j-1)*4,(i-1)*m*4+(j-1)*4+2,k);            }        }        for(int i=0;i<2*n;i++){            for(int j=0;j<2*m;j++){                scanf("%d",&k);                //中間斜著的邊，這個公式在圖上畫畫應該不難推                add(i/2*m*4+j/2*4+1+(i%2)*2,i/2*m*4+j/2*4+2+(j%2)*2,k);            }        }        dij();        printf("%d/n",dis[nn]);    }    return 0;}