hdu 1553 Going Home (最大权匹配/费用流)

93 阅读 0 评论 62 点赞

我是靠谱客的博主鳗鱼老虎，最近开发中收集的这篇文章主要介绍hdu 1553 Going Home (最大权匹配/费用流)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目大意：

给你一个N行M列的矩阵，其中“.”代表空地，“H”代表房子，“m”代表人，其中有n个房子和n个人。现在要求每个人进入一间房子，且人走一步需要支付1美元。

求最小需要花费多少美元才能让所有人都进入到房子中（每个人只能进入一间房子，每个房子只能容纳一个人）。

解题思路：

这道题其实就是二分图最优匹配的变形而已。

因为要求的其实是最小权值之和。而KM算法求的是最大权值之和。把权值改为负数，结果再转换为正的就好了；

1.在建图的时候，将每条边的权值变为负数。结果输出-ans，就可以得到最小权值。

最小费用最大流：

加源点汇点，n个人连源点，容量为1，花费为0 ；每个人和n个房子连边，容量为1，花费为坐标的距离；n个房子连汇点，容量1，花费0；

之后跑一边费用流；记住是有向边；

KM_match:

#include<cstdio>
#include<cstring>
#include<map>
#include<vector>
#include<cmath>
#include<cstdlib>
#include<stack>
#include<queue>
#include <iomanip>
#include<iostream>
#include<algorithm>
using namespace std ;
const int M=110 ;
struct node
{
	int  x,y ;
}men[M],house[M];
int lx[M],ly[M],fx[M],fy[M],w[M][M],match[M];
char mm[M][M];
int n , m ;

int dfs(int x)
{
	fx[x]=1;
   for(int i = 1 ; i <= n ; i++)
   {
   	   if(!fy[i] && lx[x]+ly[i]==w[x][i])
   	   {
   	   	    fy[i]=1;
   	   	    if(match[i]==-1 || dfs(match[i]))
   	   	    {
   	   	    	   match[i]=x;
   	   	    	   return 1;
   	   	    }
   	   }
   }	
	 return 0;
}

void KM_match()
{
     int  Min ;
	  for(int i = 1 ; i <= n ; i++)
	  {
	  	   lx[i]=w[i][1];
	  	   for(int j = 2 ; j <= n ; j++)
	  	      lx[i]=max(lx[i],w[i][j]);
	  }	
	  memset(ly,0,sizeof(ly));
	  memset(match,-1,sizeof(match));
	 for(int k = 1 ; k <= n ; k++)
	 { 
	      while(1)
		  {
		  	   memset(fx,0,sizeof(fx));
		  	   memset(fy,0,sizeof(fy));
		  	   if(dfs(k)) break ;
		  	   Min=2147483647;
		  	   for(int i = 1 ; i <= n ;i++)
		  	     if(fx[i])
		  	     	   for(int j = 1 ; j <= n ; j++)
		  	     	      if(!fy[j])
		  	     	          Min=min(Min,lx[i]+ly[j]-w[i][j]);
		  	     	
		  	    for(int i = 1 ; i<= n ;i++)  if(fx[i]) lx[i]-=Min;
				for(int i = 1 ; i<= n ; i++) if(fy[i]) ly[i]+=Min;   	
		  }	
	 }
} 

int main()
{
	 int  sum , f1,f2 ;
	 while(~scanf("%d%d",&n,&m))
	 {
	 	   if(m+n==0) break;
	 	   f1=f2=0;
	 	   for(int i = 0 ; i < n ; i++)
	 	   {
	 	   	     scanf("%s",mm[i]);
	 	   	     for(int j = 0 ; mm[i][j] ; j++)
	 	   	     {
	 	   	     	   if(mm[i][j]=='m') {  f1++ ; men[f1].x=i ; men[f1].y=j ;}
	 	   	     	   if(mm[i][j]=='H') {  f2++ ; house[f2].x=i ; house[f2].y=j;}
	 	   	     }
	 	   }
	 	   for(int i = 1 ; i <= f1 ; i++)
			 for(int j = 1 ; j <= f2 ; j++)
			      w[i][j] = -(abs(men[i].x-house[j].x)+abs(men[i].y-house[j].y)) ;  
	 	   n=f1 ; sum=0 ;
	 	   KM_match();
	 	   for(int i = 1 ; i <= n ; i++)    sum += w[match[i]][i]  ;
	 	   printf("%dn",-sum) ;
	 }
	  return 0;
}

最小费用最大流：

#include<cstdio>
#include<cstring>
#include<map>
#include<vector>
#include<cmath>
#include<cstdlib>
#include<stack>
#include<queue>
#include <iomanip>
#include<iostream>
#include<algorithm>
using namespace std ;
const int N=1010;
const int maxM=1000200;
const int inf = 1<<30 ;
struct node
{
	int u,v,c,cost ,next;
}edge[maxM];
struct node1
{
	int x,y;
}H[300],M[300];
 int dist[N],head[N],vist[N],pre[N];
 char mm[N][N];
 int top,sumflow ;
 
 void add(int u,int v, int c,int cost)
 {
     edge[top].u=u;	edge[top].v=v; edge[top].c=c; edge[top].cost=cost ;
	 edge[top].next=head[u];head[u]=top++;
     edge[top].u=v;	edge[top].v=u; edge[top].c=0; edge[top].cost=-cost ;
	 edge[top].next=head[v];head[v]=top++;
 }
 
 int SPFA(int s,int t ,int n)
 {
 	 memset(vist,0,sizeof(vist));
 	 memset(pre,-1,sizeof(pre));
 	 int i,u,v;
 	 for(int i = 0 ; i <= n ; i++)  dist[i]=inf;
 	 vist[s]=1;dist[s]=0;
 	 queue<int>q ;
 	 q.push(s);
 	 while(!q.empty())
 	 {
 	 	    u=q.front();
 	 	    q.pop();
 	 	    vist[u]=0;
 	 	    for( i = head[u] ; i!=-1 ; i=edge[i].next)
 	 	    {
 	 	    	  v=edge[i].v;
 	 	    	  if(edge[i].c && dist[v] > dist[u]+edge[i].cost)
 	 	    	  {
 	 	    	  	    dist[v]=dist[u]+edge[i].cost ;
 	 	    	  	    pre[v]=i;
 	 	    	  	    if(!vist[v])
 	 	    	  	    {
 	 	    	  	    	  vist[v]=1;
 	 	    	  	    	  q.push(v);
 	 	    	  	    }
 	 	    	  }
 	 	    	
 	 	    }
 	 }
 	 if(dist[t]==inf) return 0 ;
 	 return 1;
 }
 
 int MCMF(int s,int t, int n)
 {
 	  int minflow ,flow=0 ,mincost=0,i ;
 	  while(SPFA(s,t,n))
 	  {
 	  	    minflow=inf+1;
 	  	    for(i = pre[t];i!=-1 ;i=pre[edge[i].u])
 	  	          minflow = min(minflow,edge[i].c) ;
 	  	    for(i = pre[t];i!=-1 ;i=pre[edge[i].u])
 	  	    {
 	  	    	 edge[i].c -=minflow ;
 	  	    	 edge[i^1].c +=minflow ;
 	  	    }  
 	  	    mincost += dist[t]*minflow ; //有minflow条路存在最短路，每条路的总花费为dist[t] ;
 	  	    flow+=minflow ;
 	  }
 	  sumflow=flow ;   //最大流 
 	  return mincost ;
 }
 
 int main()
 {
 	  int n,m,u,v,c;
 	  while(~scanf("%d%d",&n,&m))
 	  {
 	  	  if(n+m==0)  break ;
 	  	   top=0;
	       memset(head,-1,sizeof(head));
		   int f1=0,f2=0;
		   for(int i = 0 ; i< n  ; i++)
		   {
		   	      scanf("%s",mm[i]);
				 for(int j = 0 ; mm[i][j] ; j++)	      
		   	     { 
		   	           if(mm[i][j]=='m')  {  f1++ ; M[f1].x=i ; M[f1].y=j ;}
		   	           if(mm[i][j]=='H')  { f2++ ;H[f2].x=i ; H[f2].y= j ; }
		   	     }      
		   }	    
		   int s=0,t=2*f1+1 ;
		   for(int i = 1 ; i <= f1 ; i++)
		   {
		   	   add(s,i,1,0);    //连源点 
		   	   for( int j = 1 ; j <= f2 ;j++)
		   	   {
		   	   	    int temp=fabs(H[i].x-M[j].x)+fabs(H[i].y-M[j].y);
					add(i,f2+j,1,temp);	    //人连房子 
		   	   }
		   	   add(i+f2,t,1,0);   //连汇点； 
		   }
		   int ans=MCMF(s,t,t+1);
		   printf("%dn",ans);
 	  }
 	  return 0;
 }