[2016-04-16][URAL][2069][Hard Rock]

• 时间:2016-04-16 20:26:11 星期六

• 题目编号:[2016-04-16][URAL][2069][Hard Rock]

• 题目大意:给定一个n*m的格子,每个格子的边带有一定的权值,同行或者同列的边权值一样,问从左上角到右下角的所有路径中,最小边权最大值是多少?

• 分析:

  • 对于起点,要么横着走,要么竖着走,对于终点,要么横着走到,要么竖着走到,所以所有路径如下图
    
  • 对于1,2两条路径很显然,直接取边权的最小值
  • 对于3,4的路径
    • 首先两边的路的一定的,中间的路不确定,
    • 最优的情况,中间的路径只需要选择从最上到最下,边权最大的边即可,因为如果中途又走了其他竖直方向的路,边权只能更小
  • 综上,答案就是4种情况耳朵最大值

• 遇到的问题:

  • 刚开始看题目,直接Dijkstra,写完发现点的数目有105×105${10}^5\times {10}^5$个,然后呵呵,

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 1E5 + 10;
int a[maxn],b[maxn];
int main(){
        int n,m;
        scanf("%d%d",&n,&m);
        int aa =0,bb = 0;
        for(int i = 0 ; i < n ; ++i){
                scanf("%d",&a[i]);
                aa = max(aa, a[i]);
        }
        for(int j = 0 ; j < m ; ++j){
                scanf("%d",&b[j]);
                bb = max(bb,b[j]);
        }
        int t1 = min(min(b[0] , b[m - 1]),aa);
        int t2 = min(min(a[0],a[n - 1]),bb);
        int t3 = min(a[0],b[m - 1]);
        int t4 = min(b[0],a[n - 1]);
        printf("%d\n",max(t1,max(t2,max(t3,t4))));       
        return 0;
}

[2016-04-16][URAL][2069][Hard Rock]

原文：http://www.cnblogs.com/qhy285571052/p/08495e30acae15b137107c4021748a97.html