二分图水题整理 Poj 2060 + 1466 + 2771 + hdu 1150 + 1151

快来打我* 2021-11-22 22:00 162阅读 0赞

**Poj 2060 Taxi Cab Scheme**

题意：在一个矩形城市里面，有间出租车公司收到翌日的预订行程M个，每个给出起点、终点坐标，两个地点之间的车程就是那两个点之间的曼哈顿距离，车起码要在一个行程的出发时间前一分钟到起点。求最少要多少出租车才够完成所有预订？

分析：记A，B是两个行程的起点，A'，B'分别是终点，假如由A'到B的时间还在B的规定时间前，那么要走完AA',BB'要用的出租车就只需要一台。添加一条有向边<A',B>，把图建好之后，求出最小路径覆盖就是答案。

#include <cstdio>
    #include <cstring>
    #include <iostream>
    #include <cmath>
    using namespace std;
    
    const int N=505;
    bool map[N][N];
    bool vis[N];
    int match[N];
    int m;
    
    bool Dfs (int u)
    {
    	for (int v=1;v<=m;v++)
    		if (vis[v] == false && map[u][v])
    		{
    			vis[v]=true;
    			if (match[v]==0 || Dfs(match[v]))
    			{
    				match[v]=u;
    				return true;
    			}
    		}
    	return false;
    }
    
    
    struct Point
    {
    	int st,et;
    	int sx,sy,ex,ey,dis,len;
    	void Get ()
    	{
    		scanf("%d:%d %d%d%d%d",&st,&et,&sx,&sy,&ex,&ey);
    		sx++,sy++,ex++,ey++;
    		st=st*60+et;
    		dis=abs(sx-ex)+abs(sy-ey);
    		et=st+dis;
    	}
    	bool Cal (const Point& b) const
    	{
    		int d=abs(ex-b.sx)+abs(ey-b.sy);
    		if (d+et<b.st)    //严格小于,<=,WA
    			return true;
    		return false;
    	}
    }data[N];
    
    int main ()
    {
    	int T;
    	scanf("%d",&T);
    	for (int Cas=1;Cas<=T;Cas++)
    	{
    		memset(map,false,sizeof(map));
    		memset(match,0,sizeof(match));
    		scanf("%d",&m);
    		int i,sum;
    		for (i=1;i<=m;i++)
    			data[i].Get();
    		/*求最大匹配*/
    		for (i=1;i<m;i++)
    			for (int j=i+1;j<=m;j++)
    			{
    				if (data[i].Cal(data[j]))
    					map[i][j]=true;
    			}
    		for (sum=0,i=1;i<=m;i++)
    		{
    			memset(vis,false,sizeof(vis));
    			if (Dfs(i))
    				sum++;
    		}
    		printf("%d\n",m-sum);
    	}
    	return 0;
    }

**Poj 1466 Girls and Boys**

题意：一些人开始研究一种浪漫的关系，这种浪漫的关系被定义在一个男孩和一个女孩之间。  
这项研究给出了，每个学生的该种关系列表已经给出，但他们想知道满足下面条件集合元素的最大个数是多少：该集合中任意两个人都没有上述关系。  
思路：如果将有这种关系的两个人用边连起来，那么最终要求的集合中两两无边，对应图论中最大独立集。  
最大独立集= n - 最小点覆盖。 最小点覆盖 = 二分图最大匹配。  
将每个人拆成两个点，a,b 有关系，就连一条a ->b的有向边。由于在寻找最大匹配时不是枚举其中一边的点，而是枚举两边的所有点，所以得到的ans为最大匹配数的两倍，因为每条匹配的边都算了两遍。

也就是说最终的匹配数应该是该图最大匹配的1/2.那么答案就出来了。

#include <cstdio>
    #include <cstring>
    
    const int N=505;
    bool map[N][N];
    bool vis[N];
    int match[N];
    int n,num;
    
    bool Dfs (int u)
    {
    	for (int v=0;v<n;v++)
    		if (vis[v] == false && map[u][v])
    		{
    			vis[v]=true;
    			if (match[v]==-1 || Dfs(match[v]))
    			{
    				match[v]=u;
    				return true;
    			}
    		}
    	return false;
    }
    
    void Input ()
    {
    	int i,T,u,v;
    	num=0;
    	memset(map,false,sizeof(map));
    	memset(match,-1,sizeof(match));
    	for (i=0;i<n;i++)
    	{
    		scanf("%d: (%d)",&u,&T);
    		while (T--)
    		{
    			scanf("%d",&v);
    			map[u][v]=true;
    		}
    	}
    }
    
    int main ()
    {
    	while (~scanf("%d",&n))
    	{
    		Input ();
    		for (int i=0;i<n;i++)
    		{
    			memset(vis,false,sizeof(vis));
    			if (Dfs(i))
    				num++;
    		}
    		printf("%d\n",n-num/2);
    	}
    	return 0;
    }

**Poj 2771 Guardian of Decency**

题意：人和人之间如果满足4个条件的任意一条就不会成为夫妻，给定一些人，问从中最多能选多少人且保证任意两人不可能成为夫妻。  
分析：由于条件之一是性别相同则不能成为夫妻。我们根据性别把人划分为两个集合，每个人是一个结点构成二分图，若两个人可能成为夫妻则连一条边。（同性之间不能成为夫妻，所以同集合内无边，此图必定为二分图）。题目要求是选出最多的人，且任意两人之间无边。这就是求二分图的最大独立集。只要用总人数－最大匹配数即可。

#include <cmath>
    #include <cstdio>
    #include <cstring>
    
    const int N=505;
    bool map[N][N];
    bool vis[N];
    int match[N];
    int n,num,m,f;
    
    struct Point
    {
    	int h;
    	char m[105],s[105];
    }male[N],female[N];
    
    bool Dfs (int u)
    {
    	for (int v=1;v<=f;v++)
    		if (vis[v] == false && map[u][v])
    		{
    			vis[v]=true;
    			if (match[v]==-1 || Dfs(match[v]))
    			{
    				match[v]=u;
    				return true;
    			}
    		}
    	return false;
    }
    
    bool Judge (Point a,Point b)
    {
    	if (fabs(a.h-b.h)>40)
    		return false;
    	if (strcmp(a.m,b.m))
    		return false;
    	if (strcmp(a.s,b.s)==0)
    		return false;
    	return true;
    }
    
    void Input ()
    {
    	int i,a;
    	char s[5];
    	memset(map,false,sizeof(map));
    	memset(match,-1,sizeof(match));
    	for (i=1;i<=n;i++)
    	{
    		scanf("%d%s",&a,s);
    		if (s[0]=='M')
    		{
    			male[++m].h=a;
    			scanf("%s%s",male[m].m,male[m].s);
    		}
    		else
    		{
    			female[++f].h=a;
    			scanf("%s%s",female[f].m,female[f].s);
    		}
    	}
    	for (i=1;i<=m;i++)
    		for (int j=1;j<=f;j++)
    		{
    			if (Judge(male[i],female[j]))
    				map[i][j]=true;
    		}
    
    }
    
    int main ()
    {
    #ifdef ONLINE_JUDGE
    #else
    	freopen("read.txt","r",stdin);
    #endif
    	int T;
    	scanf("%d",&T);
    	for (int Cas=1;Cas<=T;Cas++)
    	{
    		scanf("%d",&n);
    		num=m=f=0;
    		Input ();
    		for (int i=1;i<=m;i++)
    		{
    			memset(vis,false,sizeof(vis));
    			if (Dfs(i))
    				num++;
    		}
    		printf("%d\n",n-num);
    	}
    	return 0;
    }

**hdu 1150 Machine Schedule**

##     ##

题意：机器调度问题，有两台机器，分别有n和m种工作状态，现有k个任务，需要用这两种机器来完成，由于每更换一次机器的工作状态都需重启，怎样安排这些任务，使得机器的重启次数最少

思路：由于每个任务都可以用A或B机器的某种工作状态来完成，因此，对于每个任务，

可以把A，B的工作状态作为顶点，在对应的Ａ和Ｂ的工作状态间连线，则对于每条边的两个顶点，  
因为每个任务都要完成，故至少要有一个顶点（某个机器的一种状态）存在，  
这样这个问题就转化成了在这些顶点中选取尽量少的顶点（尽量少的工作状态，尽量少的重启次数），  
使得每一条边都至少和其中一个点相关联，即最小点覆盖问题。二分图的最小点覆盖数=最大匹配数

#include <iostream>
    using namespace std;
    
    const int N=105;
    bool map[N][N];
    bool vis[N];
    int match[N];
    int n,m,k;
    
    bool Dfs (int u)
    {
    	for (int v=1;v<=m;v++)
    		if (vis[v] == false && map[u][v])
    		{
    			vis[v]=true;
    			if (match[v]==0 || Dfs(match[v]))
    			{
    				match[v]=u;
    				return true;
    			}
    		}
    	return false;
    }
    
    int main ()
    {
    	while (scanf("%d",&n),n)
    	{
    		scanf("%d%d",&m,&k);
    		memset(map,false,sizeof(map));
    		memset(match,0,sizeof(match));
    		int i,a,b,sum;
    		for (i=1;i<=k;i++)
    		{
    			scanf("%*d%d%d",&a,&b);
    			if (a==0 || b==0)   //初始状态为0,不用记录在改变次数中
    				continue;
    			map[a+1][b+1]=true;
    		}
    		/*求最大匹配*/
    		for (sum=0,i=1;i<=n;i++)
    		{
    			memset(vis,false,sizeof(vis));
    			if (Dfs(i))
    				sum++;
    		}
    		printf("%d\n",sum);
    	}
    	return 0;
    }

**Hdu 1151 Air Raid**

最小边覆盖=N-二分图最大匹配

#include <stdio.h>
    #include <string.h>
    
    const int N=125;
    bool map[N][N];
    bool vis[N];
    int match[N];
    int ni,ns;
    
    bool DFS (int u)
    {
        for (int v=1;v<=ni;v++)
            if (vis[v] == false && map[u][v])
            {
                vis[v]=true;
                if (match[v]==0 || DFS(match[v]))
                {
                    match[v]=u;
                    return true;
                }
            }
        return false;
    }
    
    int main()
    {
        int T,i,temp1,temp2,ans;
        scanf("%d",&T);
        while (T--)
        {
            ans=0;
            memset(map,false,sizeof(map));
            memset(match,0,sizeof(match));
            scanf("%d%d",&ni,&ns);
            for (i=1;i<=ns;i++)
            {
                scanf("%d%d",&temp1,&temp2);
                map[temp1][temp2]=true;
            }
            for (i=1;i<=ni;i++)
            {
                memset(vis,false,sizeof(vis));
                if (DFS(i))
                    ans++;
            }
            printf("%d\n",ni-ans);
        }
        return 0;
    }