ZOJ 1516 Ucle Tom's Inherited Land(2点マッチ最大マッチハンガリーですね)
テーマリンク:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=516
Your old uncle Tom inhersited a piece of land from his great-great-uncle.Originaly、the property had been in the shop of a rectangle.A long time ago、however、his great-great-uncle dededed to divided the and and and and landararares.inarares.s.for he love d to hnt ducks and wanted to attact them to his property(You cannot be sure、for you have not been to the place、but he made so mandy ponds the land may now consist of several sconnecthers.You.lanthers.but local rules now reglate property sales.Your uncle has been informed that,at his great t-uncle's request,a law has bens passed which establishes property canlybe sold sorectures of proquare.ponds are not salable property.Your uncle asked your help to determine the largest number of properties he could sell(the remaning squares will bell berecreational parks)
Input Input Input will include several test cases.The first line of a test case contains two integers N and M、representing、repectively、the number of columns of the land(1<=N、M=100)theinininininininininininininininininininstststststststinininininininininininininininininininininininininininininininininininininininininininininininininininininininininininststststststststinininininininininininin- K<=50)Each of the next K lineas contains two integers X and Y describing the position of a square which was turned into a pond(1<=X==N and 1<=M).The end of input is indicated by N=0.
Output For each test case in the input your program shuld produce one line of output、containing an integer value representing the maximumber of properties which can be sold.
Sample Input
4 4 4 6 1 1 1 4 4 4 4 4 4 4 4 4 4 2 2 2 2 2 2 3 1 0
Sample Output
4 3
ソース:
South America 2002、Practice
件名:
N*Nの土地があります.その中のいくつかの点が池に掘られました.残りのところは空き地です.
今は1*2の空き地に分けて売ります.
最大販売できる数量を求めます.
PS:
それぞれの土地と彼の上下左右を境界に建設する!
コードは以下の通りです
Your old uncle Tom inhersited a piece of land from his great-great-uncle.Originaly、the property had been in the shop of a rectangle.A long time ago、however、his great-great-uncle dededed to divided the and and and and landararares.inarares.s.for he love d to hnt ducks and wanted to attact them to his property(You cannot be sure、for you have not been to the place、but he made so mandy ponds the land may now consist of several sconnecthers.You.lanthers.but local rules now reglate property sales.Your uncle has been informed that,at his great t-uncle's request,a law has bens passed which establishes property canlybe sold sorectures of proquare.ponds are not salable property.Your uncle asked your help to determine the largest number of properties he could sell(the remaning squares will bell berecreational parks)
Input Input Input will include several test cases.The first line of a test case contains two integers N and M、representing、repectively、the number of columns of the land(1<=N、M=100)theinininininininininininininininininininstststststststinininininininininininininininininininininininininininininininininininininininininininininininininininininininininininststststststststinininininininininininin- K<=50)Each of the next K lineas contains two integers X and Y describing the position of a square which was turned into a pond(1<=X==N and 1<=M).The end of input is indicated by N=0.
Output For each test case in the input your program shuld produce one line of output、containing an integer value representing the maximumber of properties which can be sold.
Sample Input
4 4 4 6 1 1 1 4 4 4 4 4 4 4 4 4 4 2 2 2 2 2 2 3 1 0
Sample Output
4 3
ソース:
South America 2002、Practice
件名:
N*Nの土地があります.その中のいくつかの点が池に掘られました.残りのところは空き地です.
今は1*2の空き地に分けて売ります.
最大販売できる数量を求めます.
PS:
それぞれの土地と彼の上下左右を境界に建設する!
コードは以下の通りです
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
// 1
#define MAXN 117
int LN, RN;//L,R
int g[MAXN][MAXN], linker[MAXN];
bool used[MAXN];
int vis[MAXN][MAXN], a[MAXN][MAXN];
int dirx[4] = {0,0,1,-1};
int diry[4] = {1,-1,0,0};
int dfs(int L)//
{
int R;
for(R = 1; R <= RN; R++)
{
if(g[L][R]!=0 && !used[R])
{
// ，
used[R]=true;
if(linker[R] == -1 || dfs(linker[R]))
{
linker[R]=L;
return 1;
}
}
}
return 0;
}
int hungary()
{
int res = 0 ;
int L;
memset(linker,-1,sizeof(linker));
for( L = 1; L <= LN; L++)
{
memset(used,0,sizeof(used));
if(dfs(L) != 0)
res++;
}
return res;
}
void init()
{
memset(a,0,sizeof(a));
memset(vis,0,sizeof(vis));
memset(g,0,sizeof(g));
}
int main()
{
int n, m;
int L, R;
int k;
while(~scanf("%d%d",&n,&m))
{
if(n==0 && m==0)
break;
init();
scanf("%d",&k);
int x, y;
int cont = 1;
for(int i = 1; i <= k; i++)
{
scanf("%d%d",&x,&y);
vis[x][y] = 1;//
}
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
if(!vis[i][j])
{
a[i][j] = cont++;
}
}
}
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
if(!vis[i][j])
{
for(int h = 0; h < 4; h++)
{
int tx = i+dirx[h];
int ty = j+diry[h];
if(tx>=1&&tx<=n && ty>=1&&ty<=m && !vis[i][j])
{
g[a[i][j]][a[tx][ty]] = 1;
g[a[tx][ty]][a[i][j]] = 1;
}
}
}
}
}
LN = cont;
RN = cont;
int ans = hungary();
printf("%d
",ans/2);
}
return 0 ;
}