P4289 [HAOI2008] 移动玩具 题解

· · 题解

这是本题一篇费用流做法的题解，如果不是以练习费用流为目的的建议跳过。

题意;

给定两个 4\times 4 的矩阵，若 mp_{i,j}=1 则表示该点有玩具，每一步可以移动任意一个玩具到其上下左右的其中一格，允许两个玩具在同一个点，询问从第一个图移动到第二个图的最小步数。

建模：

默认您已经学会了费用流的原理与板子，下面将讲解建模思路。

首先建立一个超级源与超级汇，超级源可以向第一个图中的每一个 \texttt{1} 连接一条流量为 1，费用为 0 的边，表示考虑移动当前这个玩具。超级汇同理，第二个图中的每一个 \texttt{1} 向超级汇连接一条流量为 1 费用为 0 的边，表示满足了有玩具在这个点的要求。

考虑移动，每一次移动等同于流向了上下左右其中一个点，产生费用 1，又因为同一条路线允许经过多次，所以每一个点向它上下左右四个点连一条流量为 inf，费用为 1 的边。

这样我们跑出来的最小费用就是最小步数了。

Code:

#include<bits/stdc++.h>
using namespace std;
int n;
char mp[520][520];
struct edge{
    int to,nxt;
    int val,spendf;
}e[5200010];
int tot=1,head[5200010],s,t;
inline void add(int nxt,int to,int val,int spendf){
    e[++tot].to=to;
    e[tot].nxt=head[nxt];
    e[tot].val=val;
    e[tot].spendf=spendf;
    head[nxt]=tot;

    e[++tot].to=nxt;
    e[tot].nxt=head[to];
    e[tot].val=0;
    e[tot].spendf=-spendf;
    head[to]=tot;
}
int ans=0,dis[5200010],vis[5200010];
inline bool spfa(){
    for(int i=1;i<=1002;i++){
        dis[i]=INT_MAX;
    }
    queue<int>q;
    q.push(s);
    dis[s]=0;
    vis[s]=1;
    while(!q.empty()){
        int x=q.front();
        q.pop();
        vis[x]=0;
        for(int i=head[x];i;i=e[i].nxt){
            int v=e[i].to;
            if(e[i].val&&dis[v]>dis[x]+e[i].spendf){
                dis[v]=dis[x]+e[i].spendf;
                if(!vis[v]){
                    vis[v]=1;
                    q.push(v);
                } 
            } 
        }
    }
    return dis[t]!=INT_MAX;
}
inline int dfs(int x,int sum){
    if(x==t)return sum;
    int res=0;
    vis[x]=1;
    for(int i=head[x];i&&sum;i=e[i].nxt){
        int v=e[i].to;
        if(e[i].val&&!vis[v]&&dis[v]==dis[x]+e[i].spendf){
            int k=dfs(v,min(sum,e[i].val));
            e[i].val-=k;
            e[i^1].val+=k;
            sum-=k;
            res+=k; 
            ans+=k*e[i].spendf;
        } 
    }
    vis[x]=0;
    return res;
}
inline void dinic(){
    while(spfa()){
        dfs(s,INT_MAX);
    }
}
int cx[]={1,0,0,-1};
int cy[]={0,1,-1,0};
int main(){
    s=1001;t=s+1;
    for(int i=1;i<=4;i++){
        for(int j=1;j<=4;j++){
            cin>>mp[i][j];
            if(mp[i][j]=='1'){
                add(s,(i-1)*4+j,1,0);
            }
            for(int k=0;k<4;k++){
                int x=i+cx[k],y=j+cy[k];
                if(x>=1&&x<=4&&y>=1&&y<=4){
                    add((i-1)*4+j,(x-1)*4+y,INT_MAX,1);
                }
            }
        } 
    }
    for(int i=1;i<=4;i++){
        for(int j=1;j<=4;j++){
            cin>>mp[i][j];
            if(mp[i][j]=='1'){
                add((i-1)*4+j,t,1,0);
            }
        } 
    }
    dinic();
    cout<<ans;
}