TreasureHunting (hdu3468二分匹配+bfs最短路径)

作者:网络    软件教程库   2020-05-21

treasure hunting

time limit: 4000/2000 ms (java/others)memory limit: 131072/65536 k (java/others)
total submission(s): 1509accepted submission(s): 393


problem description

do you like treasure hunting today, with one of his friend, isea is on a venture trip again. as most movie said, they find so many gold hiding in their trip.
now isea’s clever friend has already got the map of the place they are going to hunt, simplify the map, there are three ground types:

● ‘.‘ means blank ground, they can get through it
● ‘#‘ means block, they can’t get through it
● ‘*‘ means gold hiding under ground, also they can just get through it (but you won’t, right)

what makes isea very delighted is the friend with him is extraordinary justice, he would not take away things which doesn’t belong to him, so all the treasure belong to isea oneself!
but his friend has a request, he will set up a number of rally points on the map, namely ‘a‘, ‘b‘ ... ‘z‘, ‘a‘, ‘b‘ ... ‘z‘ (in that order, but may be less than 52), they start in ‘a‘, each time friend reaches to the next rally point in the shortest way, they have to meet here (i.e. isea reaches there earlier than or same as his friend), then start together, but you can choose different paths. initially, isea’s speed is the same with his friend, but to grab treasures, he save one time unit among each part of road, he use the only one unit to get a treasure, after being picked, the treasure’s point change into blank ground.
under the premise of his friend’s rule, how much treasure isea can get at most


input

there are several test cases in the input.

each test case begin with two integers r, c (2 ≤ r, c ≤ 100), indicating the row number and the column number.
then r strings follow, each string has c characters (must be ‘a’ – ‘z’ or ‘a’ – ‘z’ or ‘.’ or ‘#’ or ‘*’), indicating the type in the coordinate.

the input terminates by end of file marker.


output

for each test case, output one integer, indicating maximum gold number isea can get, if they can’t meet at one or more rally points, just output -1.


sample input

2 4 a.b. ***c 2 4 a#b. ***c


sample output

1 2


author

isea @ whu


source

2010 acm-icpc multi-university training contest(3)——host by whu


recommend

zhouzeyong|we have carefully selected several similar problems for you:34673461346234643465



题意:在一个r*c的地图内,字母表示集合点,‘*’表示宝藏,‘.’表示空地,现在沿着a-....-z-a-....-z的方向走,途中从一个集合点到下一个集合点之间只能捡一个宝藏,问最后最多能捡多少宝藏。

思路:将集合点和宝藏分别看成两个集合,若在集合点x到y的最短路径上有‘*’,那么就在x和‘*’之间连边。bfs求出所有集合点到下一个集合点的最短路径。

代码:

#include iostream
#include cstdio
#include cstring
#include algorithm
#include cmath
#include string
#include map
#include stack
#include vector
#include set
#include queue
#pragma comment (linker,/stack:102400000,102400000)
#define maxn 1005
#define maxn 2005
#define mod 1000000009
#define inf 0x3f3f3f3f
#define pi acos(-1.0)
#define eps 1e-6
#define lson rt1,l,mid
#define rson rt1|1,mid+1,r
#define fre(i,a,b)  for(i = a; i = b; i++)
#define free(i,a,b) for(i = a; i = b; i--)
#define frl(i,a,b)  for(i = a; i  b; i++)
#define frll(i,a,b) for(i = a; i  b; i--)
#define mem(t, v)   memset ((t) , v, sizeof(t))
#define sf(n)       scanf(%d, n)
#define sff(a,b)    scanf(%d %d, a, b)
#define sfff(a,b,c) scanf(%d %d %d, a, b, c)
#define pf          printf
#define dbg         pf(hi\n)
typedef long long ll;
using namespace std;

struct node
{
    int x,y;
    int step;
};

int dir[4][2]={1,0,-1,0,0,1,0,-1};
int g[60][10005];
int linker[10005];
char mp[105][105];
int id1[105][105],id2[105][105];
int dist1[60][10005],dist2[60][60];
int r,c,un,vn;
bool used[10005];
bool vis[105][105];

bool dfs(int u)
{
    for (int v=1;v=vn;v++)
    {
        if (g[u][v]!used[v])
        {
            used[v]=true;
            if (linker[v]==-1||dfs(linker[v]))
            {
                linker[v]=u;
                return true;
            }
        }
    }
    return false;
}

int hungary()
{
    int res=0;
    memset(linker,-1,sizeof(linker));
    for (int u=1;u=un;u++)
    {
        memset(used,false,sizeof(used));
        if (dfs(u)) res++;
    }
    return res;
}

bool isok(node a)
{
    if (a.x=0a.xra.y=0a.yc) return true;
    return false;
}

void bfs(int sx,int sy)
{
    int minn=inf;
    queuenodeq;
    node st,now;
    while (!q.empty()) q.pop();
    st.x=sx;st.y=sy;
    st.step=0;
    memset(vis,false,sizeof(vis));
    vis[sx][sy]=true;
    q.push(st);
//    printf(%d %d+\n,sx,sy);
    while (!q.empty())
    {
        st=q.front(); q.pop();
        for (int i=0;i4;i++)
        {
            now.x=st.x+dir[i][0];
            now.y=st.y+dir[i][1];
            now.step=st.step+1;
            if (isok(now)mp[now.x][now.y]!=#39;##39;!vis[now.x][now.y])
            {
//                printf(%d %d\n,now.x,now.y);
                vis[now.x][now.y]=true;
                q.push(now);
                if (mp[now.x][now.y]==#39;*#39;)
                    dist1[id1[sx][sy]][id2[now.x][now.y]]=now.step;
                if (id1[now.x][now.y]==id1[sx][sy]+1)
                    dist2[id1[sx][sy]][id1[now.x][now.y]]=now.step;
            }
        }
    }
}

int main()
{
//    freopen(c:/users/asus1/desktop/in.txt,r,stdin);
    int i,j;
    while (~scanf(%d%d,r,c))
    {
        int cnt1=0,cnt2=1;
        int have[60];
        memset(have,0,sizeof(have));
        memset(id1,0,sizeof(id1));
        memset(g,0,sizeof(g));
        memset(id2,0,sizeof(id2));
        for (i=0;ir;i++)
        {
            scanf(%s,mp[i]);
            for (j=0;jc;j++)
            {
                if (mp[i][j]=#39;a#39;mp[i][j]=#39;z#39;)
                {
                    id1[i][j]=mp[i][j]-#39;a#39;+1; //给集合点标号
                    cnt1++;
                    have[id1[i][j]]=1;
                }
                else if (mp[i][j]=#39;a#39;mp[i][j]=#39;z#39;)
                {
                    id1[i][j]=mp[i][j]-#39;a#39;+27;  //给集合点标号
                    cnt1++;
                    have[id1[i][j]]=1;
                }
                else if (mp[i][j]==#39;*#39;)
                    id2[i][j]=cnt2++;   //给宝藏标号
            }
        }
        for (i=1;i=cnt1;i++)  //若集合点中间断层了直接输出-1
            if (!have[i]) break;
        if (i=cnt1){
            printf(-1\n);
            continue;
        }
        for (i=0;icnt1+10;i++)
            for (j=0;jcnt1+10;j++)
                dist2[i][j]=-1;  //dist2[i][[j]表示集合点i到集合点j的最短距离
        for (i=0;icnt1+10;i++)
            for (j=0;jcnt2+10;j++)
                dist1[i][j]=-1; //dist1[i][j]表示集合点i到宝藏j的最短距离
        int flag=1;
        for (i=0;ir;i++)
        {
            for (j=0;jc;j++)
            {
                if (id1[i][j])
                    bfs(i,j);
            }
        }
        for (i=1;icnt1;i++) //若有两个集合点之间不可到达直接输出-1
            if (dist2[i][i+1]==-1){ 
                flag=0;
                break;
            }
        if (!flag)
        {
//            dbg;
            printf(-1\n);
            continue;
        }
//        dbg;
        for (i=0;ir;i++)//建图
        {
            for (j=0;jc;j++)
            {
                if (id1[i][j])
                {
                    for (int k=1;kcnt2;k++)
                    {
                        if (dist1[id1[i][j]][k]+dist1[id1[i][j]+1][k]==dist2[id1[i][j]][id1[i][j]+1])
                            g[id1[i][j]][k]=1;
                    }
                }
            }
        }
        un=cnt1;vn=cnt2-1;
        printf(%d\n,hungary());
    }
    return 0;
}


treasure hunting (hdu 3468 二分匹配+bfs最短路径)

原文地址:http://blog.csdn.net/u014422052/article/details/45421661

软件教程库 该篇文章地址:https://www.itjcku.com/9999/1091545.html

阅读全部内容


Tags:二分匹配路径

返回首页



推荐内容

【ThinkingInJava】19、控制框架的实现

/** * 书本:《thinking in java》 * 功能:控制框架的实现 * 文件:event.java * 时 ...

【ThinkingInJava】20、控制框架的使用(初始化系统使用)

/** * 书本:《thinking in java》 * 功能:控制框架的实现,1、控制框架的完整实现是由单个的类创建 ...

最小汉密尔顿回路问题状态压缩dp

给定n个顶点做成的图,要求从顶点0出发经过所有点一次然后回到0点的一条权#20540;之和最小的一条路的权#20540; ...

POJ1966.CableTVNetwork——无向图的点连通度

http://poj.org/problemid=1966 题目描述: 有线电视网络中,中继器的连接是双向的。如果网 ...

Oracle备忘录1

数据库管理员:安装升级oracle数据库建库,表空间,表,视图,索引。。。制定并实施备份和修复计划数据库权限管理,调优, ...

FileStream文件流

使用文件流拷贝一个较大的多媒体文件: public static void copyfile(string soucr ...

C语言BFS(5)___TT与魔法师(swustoj2464)

description tt生活在一个充满魔法的国度,为了便于管理,国王请魔法师在一些重要的城市之间造出 ...

进程类Process与多线程Thread

进程类(process)的基本操作: //通过进程类查询系统所有进程 process[] pr ...

Xml解析方式之Pull解析器的使用

xml有多种解析的方式,这篇文章只介绍用pull解析器来解析xml文件,接下来我会说明使用pull解析器来读取xml文件 ...

enum,EnumMap,EnumSet

enum基本使用 : package com.enumtest; enum shrubbery { gr ...

Hibernate乱码问题解决

乱码问题其实归根接地就是两端的字符集不统一。 解决思路也有两种: 1. 修改两端字符集统一。 2. 通过代码进行转 ...

eclipse集成struts2.3.20

需要强调的是,这里介绍的是在eclipse工具下集成struts2.3.20而不是myeclipse添加对struts2 ...

ubi文件系统制作,还是"-c"选项的问题

以下是分析记录: --------------------------------------------------- ...

如何把事情做到最好读书笔记1

开篇语: 每个人生来都具备足够的潜力,每个人都能做到别人#30524;中难以企及的事情。请永远保持初学之心,勇敢面对 ...

如何把事情做到最好读书笔记2

第二章 认清自己:你属于哪种类型的人 你必须足够了解你自己,下面有三种类型的人、 (1)浅尝辄止者 浅尝辄止者对一切 ...

如何把事情做到最好读书笔记3

第三章 一份耕耘才能一份收获 当你决定踏上精益求精之路时,你会突然发现周围的一切都与你所追求的#26684;#2668 ...

如何把事情做到最好读书笔记4

第四章 热爱平台期 从小,我们接受的教育就是好好学习,这样才能上好的大学,上好的大学才能找到好工作,有好工作才能有钱买 ...

习题10-21二项式系数UVa1649

1.题目描述:点击打开链接 2.解题思路:本题利用枚举#43;二分解决。问题的关键是选对枚举对象,因为要找c(n,k)= ...

mysql小技巧

selectnow(),user(),version(),database(); #最后输入\c是放弃的意思 des ...

Java学习笔记——面试常客:写出一个死锁的例子

现在的面试挺蛋疼,为了考察大家的语言掌握水平,类#20284;这样的题特别多,不过在某个角度来说确实能看出一个人对某个知 ...

UVA-10396VampireNumbers暴力+打表

题目大意:给出n,要求你输出所有符合规则的n位数 规则如下,这个n位数由两个n/2位数相乘得到,并且满足 1.这n位 ...

CF148D.Bagofmice[概率dp]

题目链接:http://codeforces.com/problemset/problem/148/d 题目大意:一袋子 ...

HDU-1846-BraveGame(巴什博弈)

题目传送:brave game 介绍: 巴什博奕(bash game): 首先我们来玩一个比较古老的报数游戏。a ...

HDU-2149-PublicSale(巴什博弈)

题目传送:public sale 思路:巴什博弈 ac代码: #include lt;cstdiogt; # ...

enum实现售卖机

首先 推荐一下google的代码风格 :https://google-styleguide.googlecode ...

批量添加用户

a、创建用户文件,因为添加的用户比较多,因此编写脚本创建一个用户文件user.txt #!/bin/ba ...

解决侧滑中ViewPager和SlidingMenu的滑动冲突

当我们在使用开源框架slidingmenu时,如果要是使用到viewpager,就会出现滑动冲突。 解决方案: }/** ...

shell打乱文件行

思路,产生一个随机数组,然后按按照数组的元素将文件中行的重新输出 1、随机数组的生成 看书的时候感觉很是简单。第 ...

编程之美2015初赛第二场AB

题目1 : 扑克牌 时间限制:2000ms 单点时限:1000ms 内存限制:256mb 描述 一副不含王的扑 ...

Java设计模式之单例模式(恶汉式和懒汉式)

/* * 单例模式: * 饿汉式:类一加载就创建对象 * 懒汉式:用的时候,才去创建对象 * 面试题:单例模式的 ...


本网站部分内容来自互联网,版权归原作者所有,文章内容仅代表原作者个人观点。如有侵权请联系我们删除 电子邮件 itjcku@foxmail.com