UVALIVE 4654 Tracking Robots 【最小路径覆盖】

学二分图那么久,真是白学了,妥妥的最小路径覆盖都木有看出来。弱爆了。
链接:http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2655

给你一个图,最多有100个点,一开始有很多(不知道多少)个机器人在编号为1的点上,现在机器人开始移动,每当有一个机器人进入一个新点的时候,就会报出新点的编号。现在我们得到了一个长度不超过200的报号序列,想知道一开始最多和最少有几个机器人。注意所谓的新点即“与报号机器人之前所在的点不同”,所以每当一个机器人移动到下一个点时就会发生报号,并且机器人可以往复运动。

对于最多有多少个机器人,可以有一个猜想,即如果所有的报号均为不同的机器人报出的,可能吗?如果不可能,什么样的情况不可能?即,不和1点直接相连的点的编号显然不可能是由新出现的机器人报出的。所以,最大的机器人数量即为报号序列中与1号点相连的点的编号出现的次数。

对于最少有多少个机器人,那么裸的最小路径覆盖模型啊。我个蒟蒻。
模型转化:我们怎样才能使机器人最少呢?即是让尽量少的机器人去报这个报号序列:如果把报号序列抽象成一个有向新图的话,就用尽量的少的路径来覆盖这个新图。最小路径覆盖模型即得。
建图方式:M^2建图,对于序列中的每个点枚举它之后的点列,看在原图中两点是否相连,如果相连,则在新图中连一条有向边。
然后匈牙利,再然后就M-二分图最大匹配即为答案。

(蒻弼,你不打错下标能死啊?你认真点能死啊!)

代码:
#include <iostream>
#include 
<cstdio>
#include 
<cstring>
using namespace std;
#define maxn 205
int mac[maxn];
bool vis[maxn],graph[maxn][maxn],old[maxn][maxn];
int n,m;
int input[maxn];
bool find(int x)
{
    
for(int i = 1;i <= m;i++)
        
if(graph[x][i] && !vis[i])
        {
            vis[i] 
= true;
            
if(!mac[i] || find(mac[i]))
            {
                mac[i] 
= x;
                
return true;
            }
        }
    
return false;
}
int main()
{
    
while(scanf("%d%d",&n,&m) == 2 && (n || m))
    {
        memset(old,
0,sizeof(old));
        memset(graph,
0,sizeof(graph));
        memset(mac,
0,sizeof(mac));
        
for(int i = 1;i <= n;i++)
        {
            
int c;
            scanf(
"%d",&c);
            
for(int j = 1;j <= c;j++)
            {
                
int a;
                scanf(
"%d",&a);
                old[i][a] 
= true;
            }
        }
        
int ans2 = 0;
        
for(int i = 1;i <= m;i++)
        {
            scanf(
"%d",&input[i]);
            
if(old[1][input[i]])
                ans2
++;
        }
        
for(int i = 1;i <= m;i++)
            
for(int j = i + 1;j <= m;j++)
                
if(old[input[i]][input[j]])
                    graph[i][j] 
= true;
        
int ans1 = m;
        
for(int i = 1;i <= m;i++)
        {
            fill(vis,vis 
+ m + 1,0);
            
if(find(i))
                ans1
--;
        }
        printf(
"%d %d\n",ans1,ans2);

    }
}

posted on 2011-08-21 22:35 BUPT-[aswmtjdsj] @ Penalty 阅读(306) 评论(0)  编辑 收藏 引用 所属分类: 图论UVAlive Solution Report


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2011年8月>
31123456
78910111213
14151617181920
21222324252627
28293031123
45678910

导航

统计

常用链接

留言簿(1)

随笔分类(150)

随笔档案(71)

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜