【POJ2195】Going Home-最小费用最大流模板题

测试地址：Going Home

题目大意：有一些人要回到房子里去，一个人每在地图上走一格都要交1美元，问每个人都回到房子里最少要付多少钱。

做法：这道题据说是二分图最优匹配，但是用最小费用最大流做也可以。在人的点集和房子的点集之间连边，容量为1，费用为人和房子之间的曼哈顿距离，然后构造源点，与人的点集连边，再构造汇点，与房子的点集连边，容量为1，费用为0，然后直接做最小费用最大流求出最小费用即可。

以下是本人代码：

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
#define inf 999999999
using namespace std;
int n,m,mcase,hcase,mx[210],my[210],hx[210],hy[210],tot;
int first[510],s,t,laste[510],last[510],dis[510];
bool inque[510];
struct {int v,c,f,next;} e[100010];

void insert(int a,int b,int c)
{
  e[++tot].v=b;e[tot].c=c;e[tot].f=1;e[tot].next=first[a];first[a]=tot;
  e[++tot].v=a;e[tot].c=-c;e[tot].f=0;e[tot].next=first[b];first[b]=tot;
}

int dist(int i,int j)
{
  return abs(mx[i]-hx[j])+abs(my[i]-hy[j]);
}

bool spfa()
{
  queue<int> q;
  q.push(s);
  memset(inque,0,sizeof(inque));
  memset(laste,0,sizeof(laste));
  memset(last,0,sizeof(last));
  for(int i=1;i<=mcase*2+1;i++)
    dis[i]=inf;
  dis[s]=0;
  inque[s]=1;
  while(!q.empty())
  {
    int v=q.front();q.pop();
	for(int i=first[v];i;i=e[i].next)
	  if (e[i].f&&dis[e[i].v]>dis[v]+e[i].c)
	  {
	    dis[e[i].v]=dis[v]+e[i].c;
		last[e[i].v]=v;
		laste[e[i].v]=i;
		if (!inque[e[i].v])
		{
		  inque[e[i].v]=1;
		  q.push(e[i].v);
		}
	  }
	inque[v]=0;
  }
  if (dis[t]==inf) return 0;
  else return 1;
}

int mincost()
{
  int ans=0;
  while(spfa())
  {
	int v=t,maxf=inf;
	while(v!=s)
	{
	  maxf=min(maxf,e[laste[v]].f);
	  v=last[v];
	}
	v=t;
	while(v!=s)
	{
	  e[laste[v]].f-=maxf;
	  e[laste[v]^1].f+=maxf;
	  v=last[v];
	}
	ans+=dis[t]*maxf;
  }
  return ans;
}

int main()
{
  while(scanf("%d%d",&n,&m)!=EOF&&n&&m)
  {
    getchar();
	mcase=hcase=0;
    for(int i=1;i<=n;i++)
	{
	  for(int j=1;j<=m;j++)
	  {
	    char c;
	    scanf("%c",&c);
	    if (c=='m') mx[++mcase]=i,my[mcase]=j;
	    if (c=='H') hx[++hcase]=i,hy[hcase]=j;
	  }
	  getchar();
	}
	
	memset(first,0,sizeof(first));
	tot=1; //注意：要使真边i和回退边i^1对应，应使边0和1对应，边2和3对应...这里由于本人使用0来表示终止符，所以从2开始
	
	for(int i=1;i<=mcase;i++)
	  for(int j=1;j<=mcase;j++)
	    insert(i,mcase+j,dist(i,j));
	for(int i=1;i<=mcase;i++)
	  insert(0,i,0);
	for(int i=1;i<=mcase;i++)
	  insert(mcase+i,mcase*2+1,0);
	
	s=0,t=mcase*2+1;
	printf("%d
",mincost());
  }
  
  return 0;
}