題解 UVA1376 【Animal Run】

雙倍經驗題 q w q q q qwqqq qwqqq

如果您 A C AC AC 了本題，您可以去隔壁洛谷P4001狼抓兔子

(完全一樣的題目，隻是需要更改一下格式)

本題表面上看着像是網絡流最小割，但是網絡流蒟蒻不會的複雜度可能無法接受

是以本題是一個最短路

是以需要把圖轉為對偶圖

将原圖内圍成的每一個三角形看作一個虛點

因為要将起點和終點分割開，是以所練的路徑異地逆回購是從左或下到達右或上

是以需要 2 2 2 個點，一個點指向左和下的點，一個點被上或右的所有點指向

其餘的店指向與之相鄰的點

邊權為删除該邊的代價

是以很建好圖跑一遍 d i j k s t r a dijkstra dijkstra 就行了

P . S . P.S. P.S. 可能存在 n n n 或 m = 1 m=1 m=1 的情況，直接輸出所有邊中的最小值即可

具體細節見代碼(蒟蒻寫的可能還有一些複雜)

下面附上蒟蒻的代碼

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
inline int read()
{
    int r,s=0,c;
    for(;!isdigit(c=getchar());s=c);
    for(r=c^48;isdigit(c=getchar());(r*=10)+=c^48);
    return s^45?r:-r;
}
const int M=2100000,inf=2e9+7;
int n,m,minn,t;
inline int calc(int x,int y,int pos)
{//pos=1下,pos=2 上
    int ans=(2*m-2)*(x-1)+2*y-1;
    if(pos==2)ans++;
    return ans;
}
struct edge
{
    int to,next,val;
}mem[M<<2];
int head[M],cnt;
inline void add(int u,int v,int val)
{
    mem[++cnt].next=head[u];
    mem[cnt].to=v;
    mem[cnt].val=val;
    head[u]=cnt;
}
struct node
{
    int val,num;
    friend bool operator < (node a,node b)
    {
        return a.val>b.val;
    }
}f,ff;
int d[M];
bool vis[M];
inline void dijkstra(int s)
{
    int num=2*n*m-2*n-2*m+4;
    for(int i=1;i<=num;i++)
        d[i]=inf,vis[i]=0;
    priority_queue<node> q;
    f.num=s,f.val=0;
    d[s]=0;
    q.push(f);
    while(!q.empty())
    {
        f=q.top();
        q.pop();
        if(vis[f.num])continue;
        vis[f.num]=1;
        for(int i=head[f.num];i>0;i=mem[i].next)
        {
            int to=mem[i].to;
            if(d[to]>d[f.num]+mem[i].val)
            {
                d[to]=d[f.num]+mem[i].val;
                ff.num=to,ff.val=d[to];
                q.push(ff);
            }
        }
    }
}
int main()
{
    while(1)
    {

        minn=inf; 
        n=read(),m=read();
        if(n==0||m==0)
            return 0;
        memset(mem,0,sizeof(mem));
        memset(head,0,sizeof(head));
        cnt=0;
        int val;
        for(int i=1;i<=n;++i)//橫邊 
            for(int j=1;j<m;++j)
            {
                val=read();
                minn=min(minn,val);
                if(i==1)
                    add(calc(i,j,2),2*n*m-2*n-2*m+4,val);
                else if(i==n)
                    add(2*n*m-2*n-2*m+3,calc(i-1,j,1),val);
                else
                    add(calc(i-1,j,1),calc(i,j,2),val),add(calc(i,j,2),calc(i-1,j,1),val);
            }
        for(int i=1;i<n;++i)//縱邊
            for(int j=1;j<=m;++j)
            {
                val=read();
                minn=min(minn,val);
                if(j==1)
                    add(2*n*m-2*n-2*m+3,calc(i,j,1),val);
                else if(j==m)
                    add(calc(i,j-1,2),2*n*m-2*n-2*m+4,val);
                else
                    add(calc(i,j-1,2),calc(i,j,1),val),add(calc(i,j,1),calc(i,j-1,2),val);
            }
        for(int i=1;i<n;++i)//斜邊
            for(int j=1;j<m;++j)
            {
                val=read();
                minn=min(minn,val);
                add(calc(i,j,1),calc(i,j,2),val),add(calc(i,j,2),calc(i,j,1),val);
            }
        if(n==1||m==1)
        {
            printf("%d\n",minn);
            return 0;
        }
        dijkstra(2*n*m-2*n-2*m+3);
        t++;
        printf("Case %d: Minimum = %d\n",t,d[2*n*m-2*n-2*m+4]);
    }
    return 0;
}