cf D. Dima and Trap Graph

http://codeforces.com/contest/366/problem/D

遍历下界,然后用二分求上界,然后用dfs去判断是否可以。

 #include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 10000
using namespace std; int n,m;
int head[maxn];
bool vis[maxn];
int e;
int pl[maxn],pr[maxn];
int ans;
struct node
{
int u,v;
int l,r;
int next;
}p[maxn*]; void inti()
{
memset(vis,false,sizeof(vis));
memset(head,-,sizeof(head));
e=;
} void add(int u,int v,int l,int r)
{
p[e].u=u;
p[e].v=v;
p[e].l=l;
p[e].r=r;
p[e].next=head[u];
head[u]=e++;
} bool dfs(int u,int l,int r)
{
if(l>r) return false;
vis[u]=true;
if(u==n) return true;
for(int i=head[u]; i!=-; i=p[i].next)
{
int v=p[i].v,ll=p[i].l,rr=p[i].r;
if(!vis[v])
{
if(ll<=l&&rr>=r)
{
if(dfs(v,l,r)) return true;
}
}
}
return false;
} int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
inti();
int u,v,l,r;
int cnt=;
for(int i=; i<=m; i++)
{
scanf("%d%d%d%d",&u,&v,&l,&r);
add(u,v,l,r);
add(v,u,l,r);
pl[cnt]=l;
pr[cnt++]=r;
}
ans=-;
sort(pl,pl+cnt);
sort(pr,pr+cnt);
for(int i=; i<cnt; i++)
{
int l1=;
int r1=cnt;
int mid=(l1+r1)>>;
while(l1<r1)
{
memset(vis,false,sizeof(vis));
if(dfs(,pl[i],pr[mid])) l1=mid+;
else r1=mid; mid=(l1+r1)>>;
}
if(pl[i]<=pr[mid-])
{
ans=max(ans,pr[mid-]-pl[i]+);
}
}
if(ans==-) printf("Nice work, Dima!\n");
else printf("%d\n",ans);
}
return ;
}
上一篇:【WPF】UserControl 的 Load事件


下一篇:WPF之路-键盘与鼠标事件 - 简书