Poj 2594 Treasure Exploration + BZOJ 1143 祭祀 river (Floyd+二分图)

小咪咪 2021-11-22 20:40 243阅读 0赞

两道解法一样的题一起总结

**Poj 2594 Treasure Exploration**

题意：派机器人去火星寻宝，给出一个无环的有向图，机器人可以降落在任何一个点上，再沿着路去其他点探索，我们的任务是计算至少派多少机器人就可以访问到所有的点。有的点可以重复去。  
思路： 这是个最小路径覆盖问题，但是因为有的点可以重复访问，所以最小路径是可以相交的，我们就用传递闭包建立新图（G’），转化为一般的路径覆盖，  
最小路径覆盖 = 图的顶点数 – 最大匹配数，

#include <iostream>
    using namespace std;
    
    const int N=505;
    bool map[N][N];
    bool vis[N];
    int match[N];
    int n,m;
    
    bool Dfs (int u)
    {
    	for (int v=1;v<=n;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;
    }
    
    void Floyd ()  
    {  
    	for (int i=1;i<=n;i++)  
    		for (int j=1;j<=n;j++)  
    			for (int k=1;k<=n;k++)
    				if (map[j][i]==true && map[i][k]==true)
    					map[j][k]=true;
    } 
    
    int main ()
    {
    	while (scanf("%d%d",&n,&m),n||m)
    	{
    		memset(map,false,sizeof(map));
    		memset(match,0,sizeof(match));
    		int i,a,b,sum;
    		for (i=1;i<=m;i++)
    		{
    			scanf("%d%d",&a,&b);
    			map[a][b]=true;
    		}
    		Floyd ();
    		/*求最大匹配*/
    		for (sum=0,i=1;i<=n;i++)
    		{
    			memset(vis,false,sizeof(vis));
    			if (Dfs(i))
    				sum++;
    		}
    		printf("%d\n",n-sum);
    	}
    	return 0;
    }

**BZOJ 1143 祭祀 river**

题目链接：http://61.187.179.132/JudgeOnline/problem.php?id=1143

题意：给出一个有向无环图。在其中找出一个最大的点集使得点集中任意两个点之间不可达。

思路：首先在给出图中跑一次floyd，这样g\[i\]\[j\]=1则i可到达j。那么题意就是求最大独立集。最大独立集=|G|-最小顶点覆盖=|G|-二分图最大匹配。

#include <cstring>
    #include <cstdio>
    
    const int N=105;
    bool map[N][N];
    bool vis[N];
    int match[N];
    int n,m;
    
    bool Dfs (int u)
    {
    	for (int v=1;v<=n;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;
    }
    
    void Floyd ()  
    {  
    	for (int i=1;i<=n;i++)  
    		for (int j=1;j<=n;j++)  
    			for (int k=1;k<=n;k++)
    				if (map[j][i]==true && map[i][k]==true)
    					map[j][k]=true;
    } 
    
    int main ()
    {
    	while (~scanf("%d%d",&n,&m))
    	{
    		memset(map,false,sizeof(map));
    		memset(match,0,sizeof(match));
    		int i,a,b,sum;
    		for (i=1;i<=m;i++)
    		{
    			scanf("%d%d",&a,&b);
    			map[a][b]=true;
    		}
    		Floyd ();
    		/*求最大匹配*/
    		for (sum=0,i=1;i<=n;i++)
    		{
    			memset(vis,false,sizeof(vis));
    			if (Dfs(i))
    				sum++;
    		}
    		printf("%d\n",n-sum);
    	}
    	return 0;
    }