二分图最大匹配(匈牙利算法)--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 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;}

?