博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
uva 10099 The Tourist Guide
阅读量:5858 次
发布时间:2019-06-19

本文共 1284 字,大约阅读时间需要 4 分钟。

DP(仿照Floyd)

  一样的题目啊

这次是要找s到t的所有路径中,最小边的最大值,还是仿照Floyd,不过状态转移方程改一下,而且建图初始化也改一下就可以了(题目说了每条边的权都大于1)

建图邻接矩阵初始化为,d[i][j]=g[i][j],不存在的边用0表示

状态转移方程

d[i][j]=min( d[i][j] , max(d[i][k] , d[k][j]) );

题目有一个很隐晦的地方就是,每次送旅客过去,导游也是要过去的(然后他自己再回来),所以没一趟导游都占了一个位置,如果大家觉得sample不对的话,那就是一个小问题了

 

#include 
#include
#define N 110int d[N][N];int n,m,s,t,num;int min(int a ,int b){ return a
b?a:b; }void DP(){ for(int k=1; k<=n; k++) for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) d[i][j]=max(d[i][j] , min(d[i][k],d[k][j]));}int main(){ int T=0; while(scanf("%d%d",&n,&m)!=EOF) { if(!n && !m) break; memset(d,0,sizeof(d)); for(int i=1; i<=m; i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); d[u][v]=d[v][u]=w; } scanf("%d%d%d",&s,&t,&num); DP(); T++; printf("Scenario #%d\n",T); d[s][t]--; //导游占了一个位置,实际上每次送过去的游客人数要少一位 if((num%d[s][t]) == 0) printf("Minimum Number of Trips = %d\n",num/d[s][t]); else printf("Minimum Number of Trips = %d\n",(num/d[s][t])+1); printf("\n"); } return 0;}

 

转载于:https://www.cnblogs.com/scau20110726/archive/2012/12/09/2810328.html

你可能感兴趣的文章
VDI序曲十四 使用 RemoteFX 安装和配置 USB 重定向
查看>>
使用海蜘蛛HSpider模拟防火墙搭建网络案例说明v1.0
查看>>
使用组策略实现文件复制
查看>>
提升团队战斗力的要点
查看>>
019 应该把管理部分放到哪儿?
查看>>
深入浅出MFC“文档/视图”架构(5)――框架
查看>>
【JSP 随笔之一】JSP常用语法和使用总括&&JSP服务器端和客户端代码互相调用
查看>>
通过TMG发布Office Web Apps服务器到外部
查看>>
Munin监控的安装与配置
查看>>
Linq==数据访问层?
查看>>
js html 事件冒泡
查看>>
Spring 3 整合Apache CXF WebService
查看>>
.Net Attribute详解(上)-Attribute本质以及一个简单示例
查看>>
cassandra cpp driver中bind list——用cass_statement_bind_collection函数
查看>>
使用 Task 简化异步编程
查看>>
C# 中LinkLabel的简单使用
查看>>
Oracle笔记 四、增删改、事务
查看>>
《算法设计手册》面试题解答 第五章:图的遍历 附:DFS应用之找挂接点
查看>>
ElasticSearch入门 第一篇:Windows下安装ElasticSearch
查看>>
python 多线程笔记(1)-- 概念
查看>>