程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU1507(最大二分匹配)

HDU1507(最大二分匹配)

編輯：C++入門知識

題意：給你一個n*m的地，然後給你p個點，表示這些點代表的地是不能賣的，問你最多能賣出多少塊1*2的地。

找出i+j為奇數的且能賣的地，作為集合1，與這塊地相鄰的且能賣的地為集合2，這就轉化為最大二分匹配了。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define LL long long
#define maxn 105
#define INF 999999999
using namespace std;

struct point
{
	int x,y;
}w[5];

int n,m;
int f[maxn][maxn];
int flag[maxn*maxn],vis[maxn*maxn];
vector G[maxn*maxn];					//用來儲存相連接的且能賣的地
set s;									//用來儲存那幾塊地是賣掉的
set::iterator it;

bool cmp(point a,point b)
{
	if(a.x==b.x)
		return a.y>n>>m)
	{
		if(n==0 && m==0)
			break;
		memset(f,0,sizeof(f));
		s.clear();
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++)
			{
				f[i][j]=1;
			}
		}
		memset(flag,0,sizeof(flag));
		for(int i=0;i<=n*m;i++)
			G[i].clear();
		int p;
		cin>>p;
		while(p--)
		{
			int u,v;
			cin>>u>>v;
			f[u][v]=0;
		}
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++)
			{
				if(f[i][j]==1)
				{
					if((i+j)%2==1)				//存入與這塊地相連且能賣的地
					{
						if(f[i][j+1]==1)
							G[(i-1)*m+j].push_back((i-1)*m+j+1);
						if(f[i][j-1]==1)
							G[(i-1)*m+j].push_back((i-1)*m+j-1);
						if(f[i-1][j]==1)
							G[(i-1)*m+j].push_back((i-2)*m+j);
						if(f[i+1][j]==1)
							G[(i-1)*m+j].push_back((i)*m+j);
					}
				}
			}
		}
		int ans=match();
		printf("%d\n",ans);
		for(it=s.begin();it!=s.end();it++)
		{
			int num=*it;
			w[0].y=num%m;
			if(w[0].y==0)
				w[0].y+=m;
			w[0].x=((num-w[0].y)/m+1);
			w[1].y=flag[num]%m;
			if(w[1].y==0)
				w[1].y+=m;
			w[1].x=((flag[num]-w[1].y)/m+1);
			sort(w,w+2,cmp);
			printf("(%d,%d)--(%d,%d)\n",w[0].x,w[0].y,w[1].x,w[1].y);
		}
		printf("\n");
	}
	return 0;
}