二分图

二分图：图中有两个点集，集合内的点互不连边，两个集合的点互相连边

二分图最大匹配：在二分图找到最多的匹配数 匈牙利算法： 时间复杂度： 邻接矩阵:O(n^3) 邻接表:O(n*m)

int e[N][N];   //邻接矩阵  //可以用邻接表稍微优化一下 
int vis[N],link[N];  //link[i]表示编号为i的人的对象是谁(编号为i的女生喜欢的男生是谁) //vis[i]表示i是否在增广路上出现过 
int dfs(int x){   //男生x
	for(int i=1;i<=n;++i){  //女生i
		if(!e[i][x]||vis[i]) continue;  //!e[i][x]表示i和x无边即i和x并不相互喜欢  
		//vis[i]表示i已经出现在这条增广路（交错路）上h，此时连此边则必不能增广；或 曾经搜过此点结果并不可行（可行当时就return了）；所以continue  
		vis[i]=1;  //vis标记的是女生即右点集
		if(link[i]==0||dfs(link[i])){  // link[x]==0表示x没有对象  //dfs找i的对象能否找到新的对象 //dfs女生i的心仪男生能否找到新的女生
			link[i]=x;   //女生i的现男友是x //i和x配对成功
			return 1;  //配对成功返回1 
		}
	}
	return 0;  //配对失败返回0 
}

int main(){
	for(int i=1;i<=n;++i){
		memset(vis,0,sizeof vis);
		dfs(i);   //搜索第i个男生能否配对 //即i是否增广成功
	}
}

匈牙利搜的是男生，原配增广的也是男生，即只有原配男生增广成功，女生才能和新男生配对

konig定理：二分图的最大匹配数==最小点覆盖数 最小点覆盖：每个点覆盖以它为端点的所有边，选择最少的点来覆盖所有的边

图中的边就是关系 完美匹配：所有人都匹配上 最优匹配：是完美匹配（实际上n<=m，n是左点集的个数，m是右点集的个数），且匹配得分即满意度最高 匈牙利+降低标准（修改点标） O(nnm)【此复杂度为使用邻接表的复杂度】

int const INF=0x7f7f7f7f;
int dfs(int x){
	visx[x]=1;
	for(int i=1;i<=m;++i){
		if(!visy[i]&&l[x]+r[i]==e[x][i]){
			visy[i]=1;
			if( !link[i] || dfs(link[i]) ){
				link[i]=x;
				return 1;
			}
		}
	}
	return 0;
}
int solve(){
	memset(l,-0x7f,sizeof l);  //左点集 
	memset(r,0,sizeof r);  //右点集 
	for(int i=1;i<=n;++i){
		for(int j=1;j<=n;++j) l[i]=max(l[i],e[i][j]);  //令左点标等于最大边权 
	}
	for(int i=1;i<=n;++i){  //为每个点找匹配 
		while(1){ //若没找到匹配，则修改点标即加边 //最坏情况下，每个点都要修改，O(n)的复杂度（此循环）
			memset(visx,0,sizeof visx);
			memset(visy,0,sizeof visy);
			if(dfs(i)) break;
			int d=INF; 
            //以下为降低标准，即加边（修改点标）
			for(int lz=1;lz<=n;++lz){ //n是左点集 
				if(visx[lz]) {
					for(int rz=1;rz<=m;++rz){ //m是右点集，从代码和算法来看 n<=m 
						if(!visy[rz]) d=min(l[lz]+r[rz]-e[lz][rz]); 
					}
				}
			}
			if(d==INF) return -1;  //若没有加边成功，则说明没有最优匹配
			for(int j=1;j<=n;++j) if(visx[j]) l[j]-=d;
			for(int k=1;k<=m;++k) if(visy[k]) r[j]+=d;
		}
	}	
}

所有二分图的题都可以用网络流解