codeforces 366D 求1-n点最大区间长度 枚举区间左端+二分区间右端dfs判可行

题意：

给定n个点m条边的无向图

下面m条边 每条边都有一个区间，只有在该区间内的点可以通过

问从1-n点 最长 的一个区间  长度

枚举左端，二分右端，dfs判断是否可行

#include<iostream>
#include<string.h>
#include<math.h>
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<queue>
#include<set>
using namespace std;
inline int Max(int a,int b){return a>b?a:b;}
inline int Min(int a,int b){return a>b?b:a;}
#define N 1005
struct Edge{
int to, x, y, nex;
}edge[6006];
int head[N], edgenum;
void addedge(int u, int v, int x, int y){
Edge E={v,x,y,head[u]};
edge[edgenum] = E;
head[u] = edgenum++;
}
int n, m, ans;
set<int>myset;
set<int>::iterator p;
bool success;
int vis[N],Time;
void dfs(int u, int l, int r){
if(success)return ;
if(u == n){success = true;return ;}
for(int i = head[u]; ~i; i = edge[i].nex){
int v = edge[i].to;
if(vis[v] == Time || l<edge[i].x ||edge[i].y < r)continue;
vis[v] = Time;
dfs(v, l, r);
}
return ;
}
void solve(){
ans = 0;
for(p = myset.begin(); p!=myset.end(); p++)
{
int now = *p;
int l = now, r = 1000005;
while(l<r)
{
Time++;
success = false;
vis[1] = Time;
int mid = (r+l)>>1;
dfs(1,now,mid);
if(success) l = mid+1;
else r = mid;
}
ans = Max(ans, l - now);
}
}
int main()
{
Time = 1;
memset(vis, 0, sizeof(vis));
while(~scanf("%d %d",&n,&m))
{
memset(head,-1,sizeof(head)); edgenum = 0;
myset.clear();
while(m--){
int u,v,x,y;	scanf("%d%d%d%d",&u,&v,&x,&y);
addedge(u, v, x, y);
addedge(v, u, x, y);
myset.insert(x);
myset.insert(y);
}
solve();
if(ans == 0)
printf("Nice work, Dima!n");
else
printf("%dn",ans);
}
return 0;
}
/*
4 4
1 2 1 10
2 4 3 5
1 3 1 5
2 4 2 7
5 6
1 2 1 10
2 5 11 20
1 4 2 5
1 3 10 11
3 4 12 10000
4 5 6 6
*/

最后

以上就是幽默滑板为你收集整理的codeforces 366D 求1-n点最大区间长度 枚举区间左端+二分区间右端dfs判可行的全部内容，希望文章能够帮你解决codeforces 366D 求1-n点最大区间长度 枚举区间左端+二分区间右端dfs判可行所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。