二分图学习小记 Poj 1274 The Perfect Stall

绝地灬酷狼 2021-12-01 15:14 195阅读 0赞

记录匈牙利算法的模板。貌似二分图用网络流做也挺方便。

Konig定理：最小顶点覆盖学习小记 - 将狼踩尽 19891101 - 博客园  
http://www.cnblogs.com/jianglangcaijin/articles/2745325.html

最小路径覆盖学习小记 - 将狼踩尽 19891101 - 博客园  
http://www.cnblogs.com/jianglangcaijin/articles/2746947.html

最大独立集学习小记 - 将狼踩尽 19891101 - 博客园  
http://www.cnblogs.com/jianglangcaijin/articles/2747857.html

最大团学习小记 - 将狼踩尽 19891101 - 博客园  
http://www.cnblogs.com/jianglangcaijin/articles/2750212.html

基本结论：

**最小顶点覆盖等于二分图的最大匹配**

**最小路径覆盖=|G|-二分图的最大匹配。**

**最大独立集=|G|-最小顶点覆盖**

**最大团=补图的最大独立集=|G|-补图的最大匹配**

题目链接：http://poj.org/problem?id=1274

题意：n头牛到m个畜栏,每头牛只有在自己喜欢的畜栏产奶，求最大产奶量。

思路：匈牙利算法求解二分图的最大匹配

#include <iostream>
    using namespace std;
    
    const int MAX=205;
    bool map[MAX][MAX];               //存储图,map[u][v]=奶牛u喜欢到畜栏v
    bool vis[MAX];                    //访问标志数组
    int match[MAX];                   //match[i]=j表示i畜栏被分配给奶牛j
    int n,m;                          //n为牛的数量,m为畜栏的数量
    
    bool Dfs (int u)                  //能不能给奶牛u分配一个畜栏.若能,return true;否则,return false。
    {
    	for (int v=1;v<=n;v++)
    		if (vis[v] == false && map[u][v]) //畜栏v未被占 && 奶牛u喜欢到畜栏v  //第一圈所有的vis[v]都是false,在递归中避免重复访问
    		{
    			vis[v]=true;          //畜栏v已被占
    			if (match[v]==0 || Dfs(match[v])) //畜栏v还未分配 || 畜栏v已经被分配,但占有该畜栏的奶牛match[v]还可以再能分配到自己喜欢的畜栏
    			{
    				match[v]=u;       //将畜栏v分配给奶牛u
    				return true;
    			}
    		}
    	return false;
    }
    
    int main ()
    {
    	int T,i,j,k,sum;
    	while (~scanf("%d%d",&n,&m))
    	{
    		memset(map,false,sizeof(map));
    		memset(match,0,sizeof(match));
    		for (i=1;i<=n;i++)
    		{
    			scanf("%d",&T);
    			for (j=1;j<=T;j++)
    			{
    				scanf("%d",&k);
    				map[i][k]=1;
    			}
    		}
    		/*求最大匹配*/
    		for (sum=0,i=1;i<=n;i++)
    		{
    			memset(vis,false,sizeof(vis));
    			if (Dfs(i))
    				sum++;
    		}
    		printf("%d\n",sum);
    	}
    	return 0;
    }