题意：
给出节点i->n的权值区间，找到一个从1-》N的权值个数最大的连续区间。
思路；
将 l i 从小到大排序，贪心思想，假设我们拿到的当前节点的右侧值是结果的最右侧值，所以我们只需要维护所有r[j]>=r[i] 并且 l[j]<=r[i]的节点。
#include <iostream> #include <stdio.h> #include <algorithm> #include <cstring> using namespace std; int father[30005]; struct node { int u,v,l,r; }edge[30005]; void init() { for(int i=1;i<=30000;i++) father[i]=i; } int find(int x) { if(father[x]!=x) father[x]=find(father[x]); return father[x]; } int cmp(node a,node b) { return a.l<b.l; } int main() { int n,m; cin>>n>>m; for(int i=1;i<=m;i++) { scanf("%d%d%d%d",&edge[i].u,&edge[i].v,&edge[i].l,&edge[i].r); } sort(edge+1,edge+1+m,cmp); int ans=0; for(int i=1;i<=m;i++) { init(); for(int j=1;j<=m;j++) { if( edge[i].r<edge[j].l ) break; if( edge[i].r<=edge[j].r) { int rx=find(edge[j].u); int ry=find(edge[j].v); if(rx!=ry) { father[rx]=ry; } if(find(1)==find(n)) { ans=max(ans,edge[i].r-edge[j].l+1); break; } } } } if(ans==0) { cout<<"Nice work, Dima!"<<endl; } else cout<<ans<<endl; return 0; }
