题解：P10943 [PacNW 2004] Going Home

· · 题解

原题即为求让房子和人一一配对的最小费用，这类求总费用最小的完美匹配的题，不难想到用最小费用最大流。\ 考虑如何转化题目，将房子和人分别列为左侧点和右侧点，根据题意，两者之间的费用为曼哈顿距离，流量为 1。建立超级源点，向左侧点连边，费用为 0，流量为 1。建立超级汇点，让每个右侧点向超级汇点连边，费用为 0，流量为 1。建图完成，接下来直接跑最小费用最大流模板即可。

::::success[AC Code]

#include<bits/stdc++.h>
using namespace std;
const int N=109*2; 
int n,m;
struct Node{
    int x,y;
}a[N],b[N];
int topa,topb;
struct Edge{
    int to,nxt,c,w;
}e[N*N+2*N];
int hd[N*2];
int nE=1;
int d[N*2],f[N*2];
bool inq[N*2];
int S,T;
int pre[N*2],preE[N*2];
int ans;
void add(int u,int v,int cost,int flow){
    e[++nE]=(Edge){v,hd[u],cost,flow};
    hd[u]=nE;
    e[++nE]=(Edge){u,hd[v],-cost,0};
    hd[v]=nE;
}
bool spfa(){
    memset(d,0x3f,sizeof(d));
    memset(inq,0,sizeof(inq));
    memset(f,0x3f,sizeof(f));
    queue<int> q;
    d[S]=0,inq[S]=1;
    q.push(S);
    while(!q.empty()){
        int u=q.front(); q.pop();
        inq[u]=0;
        for(int i=hd[u];i;i=e[i].nxt){
            int v=e[i].to;
            if(e[i].w>0&&d[v]>d[u]+e[i].c){
                d[v]=d[u]+e[i].c;
                pre[v]=u,preE[v]=i;
                f[v]=min(f[u],e[i].w);
                if(!inq[v]){
                    q.push(v);
                    inq[v]=1;
                }
            }
        }
    }
    return d[T]!=0x3f3f3f3f;
}
void SSP(){
    ans=0;
    while(spfa()){
        if(f[T]<=0) break;
        ans+=d[T];
        int u=T;
        while(u!=S){
            int i=preE[u];
            e[i].w=0;
            e[i^1].w=1; 
            u=pre[u];
        }
    }
}
int main(){
    while(cin>>n>>m){
        if(n==0&&m==0) break;
        topa=0;
        topb=0;
        nE=1;
        memset(hd,0,sizeof(hd));
        for(int i=1;i<=n;i++){
            string s;
            cin>>s;
            for(int j=1;j<=m;j++){
                if(s[j-1]=='H') a[++topa]=(Node){i,j};
                if(s[j-1]=='m') b[++topb]=(Node){i,j};
            }
        }
        S=0,T=topa+topb+1;
        for(int i=1;i<=topa;i++){
            for(int j=1;j<=topb;j++){
                add(i,j+topa,abs(a[i].x-b[j].x)+abs(a[i].y-b[j].y),1);
            }
        }
        for(int i=1;i<=topa;i++){
            add(S,i,0,1);
        }
        for(int i=1;i<=topb;i++){
            add(i+topa,T,0,1);
        }
        SSP();//最小费用最大流
        cout<<ans<<endl;
    }
    return 0;
}

::::