题解：P10943 Going Home

· · 题解

Going Home 题解

题目大意

在一个 n\times m 的地图上，存在等量的人和房子，一个人走到一个房子的代价为他们的曼哈顿距离。
我们需要安排人与房子的对应关系，使得总代价最小。

n,m\leq 100

样例分析

HH..m 
..... 
.....
.....
mm..H

按照题目画出的图走就是最优方法。

ans=10

思考

注意到：

  1. 每一个人都要找到房子，每一个房子都要找到人，是匹配问题
  2. 匹配时候不同的对应关系有不同的代价

根据第一条，想到网络流进行匹配，考虑到第二条，应当使用费用流。

图论建模

人和房子是对应的，网络流建立如下：

  1. 每个人作为源点，仅能流出 1 的流量
  2. 每个房子作为汇点，仅能接受 1 的流量

而对于每个人都可以选择每个房子，所以对于每一个人，连接到每一个房子，费用为他们之间的曼哈顿距离。
跑最小费用最大流。

程序设计

  1. 一个超级源点，对每一个人指向一条流量为 1，费用为 0 的边
  2. 一个超级汇点，所有房子对其指向一条流量为 1，费用为 0 的边
  3. 枚举每一个人，对每个房子指向一条费用为他们之间曼哈顿距离的边
  4. 答案即为最大流的最小费用

代码

#include<bits/stdc++.h>
typedef long long ll;

const int E=25e6+10;
const int V=1e4+10;

int n,m;

struct pair{int x,y,id;};//这里的id指这个人或者房子在图中的编号
struct Star{int to,w,c,nxt;};
Star e[E*2];
int hd[V],star=1;

void addEdge(int u,int v,int w,int c){
    star++;
    e[star]={v,w,c,hd[u]};
    hd[u]=star;
}
void CostFlow(int u,int v,int w,int c){//建立流量边
    addEdge(u,v,w,c);
    addEdge(v,u,0,-c);
}

const int S=1,T=2;//超级源点，超级汇点
int cnt=2;//往后开点

int Distance(const pair &a,const pair &b){
    return abs(a.x-b.x)+abs(a.y-b.y);
}

int dis[V],pre[V];

bool SPFA(){
    std::bitset<V> in;
    std::queue<int> q;
    memset(dis,0x3f,sizeof(dis));

    q.push(S);
    dis[S]=0;
    in[S]=1;

    while(!q.empty()){
        int u=q.front();q.pop();
        in[u]=0;

        for(int id=hd[u];id;id=e[id].nxt){
            int v=e[id].to,w=e[id].w,c=e[id].c;
            if(!w)continue;

            if(dis[u]+c<dis[v]){
                pre[v]=id;
                dis[v]=dis[u]+c;
                if(!in[v]){
                    q.push(v);
                    in[v]=1;
                }
            }
        }
    }
    return (dis[T]<(int)(1e9));// 能否到达汇点
}
ll SSP(){//最小费用最大流 ssp
    ll ans=0;
    while(SPFA()){
        ans+=dis[T];
        for(int u=T;u!=S;u=e[pre[u]^1].to){
            e[pre[u]].w=0;
            e[pre[u]^1].w=1;
        }
    }
    return ans;
}

ll solve(){
    star=1;
    memset(hd,0,sizeof(hd));
    //输入
    std::vector<pair> H,M;//分别代表人和房子出现的位置
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            char c;
            std::cin>>c;
            if(c=='H')H.push_back({i,j,++cnt});
            else if(c=='m')M.push_back({i,j,++cnt});
        }
    }

    //图论建模
    for(pair p:H)CostFlow(S,p.id,1,0);
    for(pair p:M)CostFlow(p.id,T,1,0);

    for(pair a:H){
        for(pair b:M){
            CostFlow(a.id,b.id,1,Distance(a,b));
        }
    }
    //最小费用最大流

    return SSP();
}

signed main(){
    std::ios::sync_with_stdio(0);std::cout.tie(0);std::cin.tie(0);

    while(std::cin>>n>>m){
        if(!n)break;
        std::cout<<solve()<<"\n";
    }
}