首页 > 搜索 > DFS搜索 > HDU 1553 Library-二分图-[解题报告] C++
2013
12-12

HDU 1553 Library-二分图-[解题报告] C++

Library

问题描述 :

Castaway Robinson Crusoe is living alone on a remote island. One day a ship carrying a royal library has wrecked nearby. Usually Robinson brings any useful stuff from the shipwreck to his island, and this time he has brought a big chest with books.

Robinson has decided to build a bookcase for these books to create his own library. He cut a rectangular niche in the rock for that purpose, hammered in wooden pegs, and placed wooden planks on every pair of pegs that have the same height, so that all planks are situated horizontally and suit to act as shelves.

Unfortunately, Robinson has discovered that one especially old and big tome does not fit in his bookcase. He measured the height and width of this tome and has decided to redesign his bookcase in such a way, as to completely fit the tome on one of the shelves, taking into account locations of other shelves and the dimensions of the niche. With each shelf in the bookcase, one of the following operations should be made:

Leave the shelf on its original place.
Move the shelf to the left or to the right.
Shorten the shelf by cutting off a part of the plank and optionally move it to the left or to the right.
Move one of the pegs to a different place at the same height and move the shelf to the left or to the right.
Shorten the shelf by cutting off a part of the plank, move one of the pegs to a different place at the same height, and optionally move the shortened shelf to the left or to the right.
Remove the shelf from the bookcase along with both supporting pegs.
We say that the shelf is properly supported by its pegs, if exactly two distinct pegs support the shelf and the center of the shelf is between its pegs or coincides with one of the pegs. The original design of Robinson’s library has all the shelves properly supported by their pegs and lengths of all shelves are integer number of inches. The Robinson may only cut an integer number of inches from the planks, because he has no tools for more precise measurements. All remaining shelves after the redesign must be properly supported by their pegs.

You are to find the way to redesign Robinson’s library to fit the special old tome without changing original design too much. You have to minimize the number of pegs that are to be removed from their original places during the redesign (operations 4 and 5 remove one peg, and operation 6 removes two pegs). If there are different ways to solve the problem, then you are to find the one that minimizes the total length of planks that are to be cut off (operations 3 and 5 involve cutting something from the planks, and operation 6 counts as if cutting off the whole plank). Width of planks and diameter of pegs shall be considered zero.

The tome may not be rotated. The tome should completely (to all its width) stand on one of the shelves and may only touch other shelves, their pegs or niche’s edge.

输入:

The input consists of several test cases.

The first line of each test case contains four integer numbers XN, YN, XT, and YT, separated by single spaces. They are, correspondingly, width and height of the niche, and width and height of the old tome in inches (1 ≤ XN, YN, XT, YT ≤ 1000).

The second line contains a single integer number N (1 ≤ N ≤ 100) that represents the number of the shelves. Then N lines follow. Each line represents a single shelf along with its two supporting pegs, and contains five integer numbers yi, xi, li, x1i, x2i, separated by spaces, where:

yi (0 < yi < YN) – the height of the ith shelf above the bottom of the niche in inches.
xi (0 ≤ xi < XN) – the distance between the left end of the ith shelf and the left edge of the niche in inches.
li (0 < li ≤ XN – xi) – the length of the ith shelf in inches.
x1i (0 ≤ x1i ≤ li/2) – the distance between the left end of the ith shelf and its leftmost supporting peg in inches.
x2i (li/2 ≤ x2i ≤ li; x1i < x2i) – the distance between the left end of the ith shelf and its rightmost supporting peg in inches.
All shelves are situated on different heights and are properly supported by their pegs. The problem is guaranteed to have a solution for the input data.

输出:

The output shall, for each test case, contain two integer numbers separated by a space. The first one is the minimal number of pegs that are to be removed by Robinson from their original locations to place the tome. The second one is the minimal total length of planks in inches that are to be cut off during the redesign that removes the least number of pegs.

样例输入:

11 8 3 4
4
1 1 7 1 4
4 3 7 1 6
7 2 6 3 4
2 0 3 0 3
11 8 4 6
4
1 1 7 1 4
4 3 7 1 6
7 2 6 3 4
2 0 3 0 3

样例输出:

0 0
1 3

题目大意:

给你一个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("%d\n",-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("%d\n",ans);
 	  }
 	  return 0;
 }

 

 

 

解题报告转自:http://blog.csdn.net/u010126535/article/details/13019755


  1. 第二种想法,我想来好久,为啥需要一个newhead,发现是把最后一个节点一直返回到嘴上面这层函数。厉害,这道题之前没样子想过。