（未完待续）

题目链接：Luogu P4001/BZOJ 1001/ICPC-Beijing 2006 Animal Run。

题目

题目描述

数据范围

$$3\leq n,m\leq 1000$$

时空限制

$$\text{Luogu}:3\text{s}/250\text{MiB}$$

$$\text{BZOJ}:15\text{s}/162\text{MiB}$$

$$\text{ICPC}:6\text{s}/+\infty\text{MiB}$$

题解

解法 A（网络流）

思路

把每条路径都作为边加入网络，用 $\text{Dinic}$ 求 $(1,1)$ 到 $(n,m)$ 的最小割即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define reg register
#define INF 0X3F3F3F3F
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
    reg bool f=false;
    reg char ch=getchar();
    reg int res=0;
    while(ch<'0'||'9'<ch)f|=(ch=='-'),ch=getchar();
    while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
    return f?-res:res;
}

const int MAXN=1000+5;
const int MAXM=1000+5;

inline void Read(void);
inline void Work(void);

int main(void){
    Read();
    Work();
    return 0;
}

int n,m,s,t;
int cnt=1,head[MAXN*MAXM],to[MAXN*MAXM*6],w[MAXN*MAXM*6],Next[MAXN*MAXM*6];

inline void Add_Edge(reg int u,reg int v,reg int len){
    Next[++cnt]=head[u];
    to[cnt]=v;
    w[cnt]=len;
    head[u]=cnt;
    return;
}

inline void Add_Tube(reg int u,reg int v,reg int len){
    Add_Edge(u,v,len);
    Add_Edge(v,u,len);
    return;
}

inline int GetID(reg int i,reg int j){
    return (i-1)*m+j;
}

inline void Read(void){
    n=read(),m=read(),s=1,t=GetID(n,m);
    for(reg int i=1;i<=n;++i)
        for(reg int j=1;j<m;++j){
            static int x;
            x=read();
            Add_Tube(GetID(i,j),GetID(i,j+1),x);
        }
    for(reg int i=1;i<n;++i)
        for(reg int j=1;j<=m;++j){
            static int x;
            x=read();
            Add_Tube(GetID(i,j),GetID(i+1,j),x);
        }
    for(reg int i=1;i<n;++i)
        for(reg int j=1;j<m;++j){
            static int x;
            x=read();
            Add_Tube(GetID(i,j),GetID(i+1,j+1),x);
        }
    return;
}

int dep[MAXN*MAXM];
queue<int> Q;

inline bool BFS(int s,reg int t){
    memset(dep,-1,sizeof(dep));
    while(!Q.empty())Q.pop();
    dep[s]=1,Q.push(s);
    while(!Q.empty()){
        reg int ID=Q.front();
        Q.pop();
        for(reg int i=head[ID];i;i=Next[i])
            if(dep[to[i]]==-1&&w[i]>0){
                dep[to[i]]=dep[ID]+1;
                Q.push(to[i]);
            }
    }
    return dep[t]!=-1;
}

int cur[MAXN*MAXM];

inline int DFS(reg int ID,reg int t,reg int lim){
    if(ID==t)
        return lim;
    reg int flow=0;
    for(reg int &i=cur[ID];i;i=Next[i])
        if(dep[to[i]]==dep[ID]+1&&w[i]>0){
            reg int f=DFS(to[i],t,min(lim-flow,w[i]));
            if(f){
                flow+=f;
                w[i]-=f;
                w[i^1]+=f;
                if(flow==lim)
                    break;
            }
        }
    return flow;
}

inline int Dinic(reg int s,reg int t){
    reg int res=0;
    while(BFS(s,t)){
        memcpy(cur,head,sizeof(head));
        res+=DFS(s,t,INF);
    }
    return res;
}

inline void Work(void){
    reg int ans=Dinic(s,t);
    printf("%d\n",ans);
    return;
}

解法 B（平面图转对偶图）

思路

平面图都可以转对偶图。

建立方法就是将平面图的每个面(包括外部面)看做一个节点。根据平面图上的每条边，将其划分的两个面所代表的顶点在对偶图中连接一条无向边，若边带权，则边权与原边相同。

接下来说这道题的做法。
首先想到解法 A（网络流）。但是复杂度太大了。

考虑平面图转化为对偶图的用处，根据这张从网上扒的图：

可知因为连接了外界的点，整个图存在一个经过 $s’−>t’$ 的环。实际上最小的环就是原图的最小割。

因为 $s’−>t’$ 这条边造成了环，所以删掉这条边，跑一遍 $s’−>t’$ 的最短路就是原图的最小割。

代码

来自duliu题之狼抓兔子题解 – 千载煜 – 博客园。

#include<cstdio>
#include<cmath>
#include<cstring>
#include<queue>
#include<algorithm>
#define ll long long
#define pa pair<int,int>
using namespace std;
inline int read()
{
    char ch=getchar(),lst;
    int x=0;
    while(ch<'0'||ch>'9')
    {
        lst=ch;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<3)+(x<<1)+(ch^48);
        ch=getchar();
    }return ((lst=='-')?-x:x);
}
int n,m,st=1,eend,head[2000009],cnt,dis[2000009];
const int inf=214748364;
bool vis[2000009];
struct Ed{
    int to,nxt,dis;
}edge[7000009]; 
void add(int fr,int to,int dis)
{
    cnt++;
    edge[cnt].to=to;
    edge[cnt].dis=dis;
    edge[cnt].nxt=head[fr];
    head[fr]=cnt;
}
void dij()//堆优化的dij
{
   for(int i=1;i<=eend;i++)
    dis[i]=inf; 
   dis[1]=0; 
   priority_queue<pa,vector<pa>,greater<pa> > q;
   q.push(make_pair(0,1));
   while(!q.empty())
   {
    int now=q.top().second;
     q.pop();
     if(vis[now])continue;
     vis[now]=1;
     for(int e=head[now];e;e=edge[e].nxt)
     {
        int v=edge[e].to,di=edge[e].dis;
        if(dis[now]+di<dis[v])
        {
            dis[v]=dis[now]+di;
            q.push(make_pair(dis[v],v));
        }
     }
   }
}
int main()
{
    n=read();m=read();
    eend=(n-1)*2*(m-1)+2;
    for(int i=1;i<=n;i++)//横边
    {
        for(int j=1;j<=m-1;j++)
        {
            int dis=read();
            int ss=2*(i-1)*(m-1)+j+1; 
            int ee=ss-m+1;
            if(i==1)
                {add(ss,eend,dis);add(eend,ss,dis);
                continue;}
            if(i==n)
                {add(st,ee,dis);add(ee,st,dis);
                continue;}    
            add(ss,ee,dis);add(ee,ss,dis);
        }
    }//竖边
    for(int i=1;i<n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            int dis=read();
            int ss=j+(m-1)*(2*(i-1)+1)+1;
            int ee=ss-m;
            if(j==1)
            {add(st,ss,dis);add(ss,st,dis);
            continue;}
            if(j==m)
            {add(ee,eend,dis);add(eend,ee,dis);
            continue;}
            add(ee,ss,dis);add(ss,ee,dis);
        }
    }//斜边
    for(int i=1;i<n;i++)
    {
        for(int j=1;j<m;j++)
        {
            int dis=read();
            int ss=2*(i-1)*(m-1)+j+1;
            int ee=ss+m-1;
            add(ee,ss,dis);
            add(ss,ee,dis);
        }
    }
    dij();
    printf("%d",dis[eend]);
}