二分图最大匹配(匈牙利算法)--zoj1516,1525,2223

        二分图G（E,V）将点集合V分成两个部分L,R，使得，图G中所有属于E的边相关联的两个点分别在L和R中。

        二分图的一个匹配，即是图G中的边集合，其中，任意两条边都不共用一个顶点，或者说，每个顶点都之多只有一条边和它相关联。

        二分图中的最大匹配M，就是求边数最大的边集合。

        求二分图匹配有很多算法，这里介绍两种，效率都是O(EV)。

       一、将最大匹配问题规约为最大流问题。

       构造一个s源点，构造s到左边顶点集合中，每一个顶点的边。构造一个t汇点，构造右边顶点集合中，每一个顶点到t的边。把图中所有的边容量设为1，那么求原图的最大匹配即是求流网络的最大流。具体参考算法导论

       二、匈牙利算法

      具体参考：http://imlazy.ycool.com/post.1603708.html

    代码模板

#include<iostream>
#include<cstdio>
#include<string.h>
#include<map>
using namespace std;
int const MAXI=51;
bool useif[MAXI];
int links[MAXI];
bool array[MAXI][MAXI];
int left_num,right_num;
bool can(int t)
{
    for(int i=0;i<right_num;i++)
    {
       if(!useif[i]&&array[t][i])
       {
           useif[i]=true;
           if((links[i]==-1)||can(links[i]))
           {
              links[i]=t;
              return true;
           }
       }
 
    }
    return false;
}

      最大匹配的应用：

    1.二分匹配的直接模拟

    2.图的最小点覆盖数 = 图的最大匹配数；
    3.图的最大点独立集 = 图顶点数 - 图的最大匹配数；
    4.图的最小路径覆盖数 = 原图的顶点数 - 原图拆点后形成的二分图的最大匹配数；

   zoj_1516

  

#include<iostream>
#include<cstdio>
#include<string.h>
#include<map>
using namespace std;
int const MAXI=51;
bool useif[MAXI];
int links[MAXI];
bool array[MAXI][MAXI];
int left_num,right_num;
bool can(int t)
{
    for(int i=0;i<right_num;i++)
    {
       if(!useif[i]&&array[t][i])
       {
           useif[i]=true;
           if((links[i]==-1)||can(links[i]))
           {
              links[i]=t;
              return true;
           }
       }
 
    }
    return false;
}
int row,col,pond;
bool grid[101][101];
int main()
{
	freopen("e:\\zoj\\zoj_1516.txt","r",stdin);
	while(scanf("%d %d",&row,&col)!=EOF&&row&&col)
	{
		map<int,int>lp;
		lp.clear();
		map<int,int>rp;
		rp.clear();
		scanf("%d",&pond);
		int r,c;
		memset(grid,false,sizeof(grid));
		memset(array,false,sizeof(array));
		for(int i=0;i<pond;++i)
		{
			scanf("%d %d",&r,&c);
			grid[r-1][c-1]=true;		
		}
		int lindex=0;
		int rindex=0;
		left_num=right_num=0;
		for(int i=0;i<row;++i)
		{
			for(int j=0;j<col;++j)
			{
				if(!grid[i][j])
				{
					if((i+j)%2==0)
					{	
						left_num++;
						lp[col*i+j]=lindex;
						lindex++;
					}
					else
					{
						right_num++;
						rp[col*i+j]=rindex;
						rindex++;
					}
				}	
			}
		}
		for(int i=0;i<row;++i)
		{
			for(int j=0;j<col;++j)
			{
				if(!grid[i][j])
				{
					if(i+1<row&&!grid[i+1][j])
					{
						if((i+j)%2==0)
							array[lp[col*i+j]][rp[col*(i+1)+j]]=true;
						else
							array[lp[col*(i+1)+j]][rp[col*i+j]]=true;	
					}
					if(j+1<col&&!grid[i][j+1])
					{
						if((i+j)%2==0)
							array[lp[col*i+j]][rp[col*i+j+1]]=true;
						else
							array[lp[col*i+j+1]][rp[col*i+j]]=true;
					}	
				}	
			}
		}
		for(int i=0;i<MAXI;i++)
			links[i]=-1;
		int res=0;
		for(int i=0;i<left_num;++i)
		{
			memset(useif,0,sizeof(useif));
			if(can(i))
				++res;
		}
		printf("%d\n",res);
	}		
}

 zoj_1525

 

#include<iostream>
#include<cstdio>
#include<string.h>
using namespace std;
const int MAXI=125;
bool useif[MAXI];
int links[MAXI];
bool array[MAXI][MAXI];
int left_num,right_num;
bool can(int t)
{
    for(int i=0;i<right_num;i++)
    {
       if(!useif[i]&&array[t][i])
       {
           useif[i]=true;
           if((links[i]==-1)||can(links[i]))
           {
              links[i]=t;
              return true;
           }
       }
 
    }
    return false;
}
int cases;
int e,v,from,to;
int main()
{
	freopen("e:\\zoj\\zoj_1525.txt","r",stdin);
	scanf("%d",&cases);
	while(cases--)
	{
		memset(array,false,sizeof(array));
		for(int i=0;i<MAXI;i++)
			links[i]=-1;
		scanf("%d",&v);
		scanf("%d",&e);
		left_num=right_num=v;
		while(e--)
		{
			scanf("%d %d",&from,&to);
			array[from-1][to-1]=true;
		}
		int res=0;
		for(int i=0;i<left_num;i++)
		{
			memset(useif,false,sizeof(useif));
			if(can(i))
				++res;
		}
		printf("%d\n",v-res);	
	}
}

  zoj_2223

#include<iostream>
#include<cstdio>
#include<string.h>
#include<map>
using namespace std;
int cases;
bool useif[30];
int links[30];
int left_num,right_num;
bool array[30][30];
int lcards[30];
int rcards[30];
map<char,int>mv;
map<char,int>ms;
bool can(int t)
{
    for(int i=0;i<right_num;i++)
    {
       if(!useif[i]&&array[t][i])
       {
           useif[i]=true;
           if((links[i]==-1)||can(links[i]))
           {
              links[i]=t;
              return true;
           }
       }
 
    }
    return false;
}
int main()
{
	freopen("e:\\zoj\\zoj_2223.txt","r",stdin);
	ms['C']=0;
	ms['D']=1;
	ms['S']=2;
	ms['H']=3;
	mv['2']=2;
	mv['3']=3;
	mv['4']=4;
	mv['5']=5;
	mv['6']=6;
	mv['7']=7;
	mv['8']=8;
	mv['9']=9;
	mv['T']=10;
	mv['J']=11;
	mv['Q']=12;
	mv['K']=13;
	mv['A']=14;
	scanf("%d",&cases);
	while(cases--)
	{
		char value,suit;
		int k;
		scanf("%d",&k);
		left_num=right_num=k;
		for(int i=0;i<k;i++)
		{
			getchar();
			scanf("%c%c",&value,&suit);
			lcards[i]=mv[value]*4+ms[suit];		
		}
		for(int i=0;i<k;i++)
		{
			getchar();
			scanf("%c%c",&value,&suit);
			rcards[i]=mv[value]*4+ms[suit];	
		}
		memset(array,false,sizeof(array));
		for(int i=0;i<30;i++)
			links[i]=-1;
		for(int i=0;i<k;i++)
		{
			for(int j=0;j<k;j++)
			{
				if(lcards[i]<rcards[j])
				{
					array[i][j]=true;
				}
			}
		}
		int res=0;
		for(int i=0;i<left_num;i++)
		{
			memset(useif,0,sizeof(useif));
			if(can(i))
				++res;
		}
		printf("%d\n",res);
	}
	return 0;	
}