hdu 1281ボードゲーム（2点マッチ）

リンクはクリックしてください:http://acm.hdu.edu.cn/showproblem.php?pid=1281
転載は出典を明記してください。http://blog.csdn.net/u012860063/article/details/20403337

----------------------------------------------------------------------------------------------------------------------------------------------------------

        ：http://user.qzone.qq.com/593830943/main

 
  
----------------------------------------------------------------------------------------------------------------------------------------------------------
Problem Description
希ちゃんとGardonさんはゲームをしています。N*Mの碁盤に対して、格子の中にできるだけ多くのチェスの中の「車」を入れて、お互いに攻撃できないようにします。もちろん簡単です。しかし、Gardonさんはいくつかのチェックしか入れられません。希ちゃんはこの問題を簡単に解決しました。（下の図を見て）車を置く場所が車の攻撃に影響しないように注意してください。  
だから、今Gardonは希ちゃんにもっと難しい問題を解決してもらいたいです。できるだけ多くの「車」を保証する前提で、碁盤の中には避けられる格子があります。つまり、これらの格子の上に車を置かなくても、できるだけ多くの「車」が下ろされることが保証されます。しかし、いくつかの格子を置かないと、できるだけ多くの「車」を置くことが保証されません。このような格子は重要なポイントと呼ばれています。Gardonは、希ちゃんにどれぐらいの重要な点があるかを計算してもらいたいですが、この問題を解決できますか？

  
 
 

   Input 
 
 
 

   输入包含多组数据，  
  
 第一行有三个数N、M、K(1<N,M<=100 1<K<=N*M)，表示了棋盘的高、宽，以及可以放“车”的格子数目。接下来的K行描述了所有格子的信息：每行两个数X和Y，表示了这个格子在棋盘中的位置。 
 
 
 

     
 
 
 
 
 

   Output 
 
 
 

   对输入的每组数据，按照如下格式输出：  
  
 Board T have C important blanks for L chessmen. 
 
 
 

     
 
 
 
 
 

   Sample Input 
 
 
 
 
  

    3 3 4 
  
 
  

    1 2 
  
 
  

    1 3 
  
 
  

    2 1 
  
 
  

    2 2 
  
 
  

    3 3 4 
  
 
  

    1 2 
  
 
  

    1 3 
  
 
  

    2 1 
  
 
  

    3 2 
  
 
 
 
 

     
 
 
 
 
 

   Sample Output 
 
 
 
 
  

    Board 1 have 0 important blanks for 2 chessmen. Board 2 have 3 important blanks for 3 chessmen. 
  
 
 
 
 

     
 
 
 
 
 

   Author 
 
 
 

   Gardon 
 
 
 
//         X Y  ，    x，y      ，  x y       ，             ，                     
//       ，         
        ：
    ：
                ，               。 i  j        ｉ ｊ        。  ，            ；“ ”              。          。         ans，            。 1 ：         ，      （          ，        ），            　　 if  (          　=＝　ans）
                 then          　　 else //          ans     ，           ，     ans。 -->    　　          then   +1 2 :           。   ，            （                ）。  ，    ans  ，       。           ，       ，                    ，           --->                。  ，            。 3 :           ：                  ，                                ：                      ，       ，       


    ：
#include<stdio.h>
#include<string.h>
const int maxn=1000+10;
int n,m;
int g[maxn][maxn],link[maxn],vis[maxn];
int dfs(int x)
{
	int i;
	for(i=1;i<=n;i++)
	{
		if(g[x][i]&&!vis[i])
		{
			vis[i]=1;
			if(link[i]==-1||dfs(link[i]))
			{
				link[i]=x;
				return 1;
			}
		}
	}
	return 0;
}
int hungary()
{
	int i,ans=0;
	memset(link,-1,sizeof(link));
	for(i=1;i<=n;i++)
	{
		memset(vis,0,sizeof(vis));
		if(dfs(i))
			ans++;
	}
	return ans;
}
int main()
{
	int k,x,y,ans,i,j,cnt,count=1;
	while(scanf("%d%d%d",&n,&m,&k)!=EOF)
	{
		memset(g,0,sizeof(g));
		while(k--)
		{
			scanf("%d%d",&x,&y);
			g[x][y]=1;
		}
		ans=hungary();//     
		cnt=0;
		for(i=1;i<=n;i++)
			for(j=1;j<=m;j++)
				if(g[i][j]==1)
				{
					g[i][j]=0;//       
					if(ans>hungary())
						cnt++;
					g[i][j]=1;
				}
				printf("Board %d have %d important blanks for %d chessmen.
",count++,cnt,ans);
	}
	return 0;
}