hihocoder二分·二分答案【二分搜索，最大化最小值】(bfs)

题目

这道题做了几个小时了都没有做出来&＃xff0c;首先是题意搞了半天都没有弄懂&＃xff0c;难道真的是因为我不打游戏所以连题都读不懂了&＃xff1f;

反正今天是弄不懂了&＃xff0c;过几天再来看看。。。

题意&＃xff1a;一个人从1点出发到T点去打boss&＃xff0c;这个人有两个属性值&＃xff0c;防御值和战斗值&＃xff0c;这两个值成反比&＃xff0c;为了打赢boss我们要使战斗值最大&＃xff0c;于是乎防御值就要最低&＃xff0c;但是也不能太低&＃xff0c;于是乎这个界限在哪&＃xff0c;这就是我们要求的。每条路上都有一个索敌值&＃xff0c;防御值必须>&＃61;索敌值 才能通过。从1点到T点有很多条通路&＃xff0c;我们要找的是&＃xff1a;这每一条通路中索敌值最大的中索敌值最小的&＃xff0c;感觉这句话有点绕&＃xff0c;具体解释看下图&＃xff1a;

1号节点是起点&＃xff0c;5号是终点&＃xff0c;从1到5有三条通路&＃xff1a;1->2->5; 1->3->5; 1->4->5; 对应路径中最长的路段长度分别是&＃xff1a;3&＃xff1b;5&＃xff1b;4&＃xff1b;因此在{3,5,4}中最小值3是正确值。

所以这道题是用二分求&＃xff0c;最大化最小值。

#include
using namespace std;int n,m,k,t;
const int Max &＃61; 10005;
int vis[Max];struct edge{int x,w;
};
vector v[Max];int bfs(int dis)
{memset(vis,0,sizeof(vis));queue q;q.push(1);while(!q.empty()){int cur &＃61; q.front();q.pop();if(cur&＃61;&＃61;t) return true;if(vis[cur]&＃61;&＃61;k)continue;int l &＃61; v[cur].size();for(int i&＃61;0;idis)continue;vis[tmp]&＃61;vis[cur]&＃43;1;q.push(tmp);}}return false;
}int main()
{int a,b,c;while(~scanf("%d%d%d%d",&n,&m,&k,&t)){int a,b,c,maxn&＃61;0;for(int i&＃61;0;i}