POJ 2195 Going Home 最小费用流 裸题

给出一个n*m的图，其中m是人，H是房子，.是空地，满足人的个数等于房子数。

现在让每个人都选择一个房子住，每个人只能住一间，每一间只能住一个人。

每个人可以向4个方向移动，每移动一步需要1$，问所有人移动到房子里的最少花费。

其中，n,m<=100,最多有100个人。

最小给用流裸题。

建立一个超级源点，跟每一个房子连一条边，容量为1，花费为0

每一个人与超级汇点连一条边，容量为1，花费为0

一个房子与每一个人建一条边，房子指向人，容量为1，花费用2者的距离（不是直线距离）

然后跑最小费用流算法就可以了。

#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>

using namespace std;

const int maxn=205;
const int inf=0x3f3f3f3f;
const int s=0;
int t;
int tot;
char maze[maxn];
char str[maxn][maxn];
bool vis[maxn];
int dis[maxn];
int prev[maxn];
int pree[maxn];

struct Point
{
    int x,y;
};
Point point[maxn];
struct Edge
{
    int to,cap,cost,rev;
};
vector<Edge>edge[maxn];

inline int get_abs(int tmp)
{
    if(tmp>0)
        return tmp;
    return -tmp;
}

inline int min(int x,int y)
{
    return x<y?x:y;
}

inline int get_dis(int i,int j)
{
    return get_abs(point[i].x-point[j].x)+get_abs(point[i].y-point[j].y);
}

void addedge(int from,int to,int cap,int cost)
{
    edge[from].push_back((Edge){to,cap,cost,edge[to].size()});
    edge[to].push_back((Edge){from,0,-cost,edge[from].size()-1});
}

void build_graph(int n,int m)
{
    //要从0开始
    for(int i=0;i<maxn;i++)
        edge[i].clear();
    tot=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(str[i][j]=='H')
            {
                point[tot].x=i;
                point[tot++].y=j;
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(str[i][j]=='m')
            {
                point[tot].x=i;
                point[tot++].y=j;
            }
        }
    }
    t=tot;
    tot--;
    tot/=2;
    for(int i=1;i<=tot;i++)
    {
        addedge(s,i,1,0);
        addedge(i+tot,t,1,0);
    }
    for(int i=1;i<=tot;i++)
    {
        for(int j=tot+1;j<=tot*2;j++)
        {
            addedge(i,j,1,get_dis(i,j));
        }
    }
}

void spfa()
{
    memset(vis,false,sizeof vis);
    for(int i=0;i<=t;i++)
        dis[i]=inf;
    queue<int>que;
    while(!que.empty())
        que.pop();
    que.push(s);
    dis[s]=0;
    vis[s]=true;
    while(!que.empty())
    {
        int u=que.front();
        que.pop();
        vis[u]=false;   //要记得这步
        for(int i=0;i<edge[u].size();i++)
        {
            Edge &e=edge[u][i];
            if(e.cap>0&&dis[e.to]>dis[u]+e.cost)
            {
                dis[e.to]=dis[u]+e.cost;
                prev[e.to]=u;
                pree[e.to]=i;
                if(!vis[e.to])
                {
                    vis[e.to]=true;
                    que.push(e.to);
                }
            }
        }
    }
    return ;
}

int solve()
{
    int ret=0;
    int flow=tot;
    while(flow>0)
    {
        spfa();
        int f=flow;
        for(int i=t;i!=s;i=prev[i])
        {
            f=min(f,edge[prev[i]][pree[i]].cap);
        }
        flow-=f;
        ret+=dis[t]*f;
        for(int i=t;i!=s;i=prev[i])
        {
            Edge &e=edge[prev[i]][pree[i]];
            e.cap-=f;
            edge[e.to][e.rev].cap+=f;
        }
    }
    return ret;
}

int main()
{
    int n,m;
    while(~scanf("%d%d",&n,&m))
    {
        if(!n&&!m)
            break;
        for(int i=1;i<=n;i++)
        {
            scanf("%s",str[i]+1);
        }
        build_graph(n,m);
        printf("%d
",solve());
    }
    return 0;
}