思路： 一开始想用dfs来做，如果标记会忽略掉很多情况，如果不标记就会超时。 dfs是来模拟这个过程，可以用并查集来枚举，直接判断。
左边界 ， 右边界肯定是一条边或者是两条边来确定，从每一条边开始枚举，按照右边界进行排序，满足条件的第一条边就是答案所需要的边
#include <cstdio> #include <algorithm> #include <iostream> using namespace std; const int N = 1010; int n,m; const int M = 3030; int f[N]; int find( int x ) { if( f[x]==x ) return f[x]; else return f[x] = find(f[x]); } struct node { int l,r,from,to; }; int ans; node edge[M]; bool cmp( node a,node b ) { return a.r>b.r; } int main() { int flag = 0 ; scanf("%d%d",&n,&m); for ( int i=0; i<m; i++ ) scanf("%d%d%d%d",&edge[i].from,&edge[i].to,&edge[i].l,&edge[i].r); sort( edge,edge+m,cmp); for ( int i=0; i<m; i++ ) { for ( int s=1; s<=n; s++ ) f[s] = s; for ( int j=0; j<m; j++ ) { if ( edge[j].l<=edge[i].l ) { int fa = find(edge[j].from); int fb = find(edge[j].to); if ( fa!=fb ) f[fa] = fb; if ( find(1)==find(n) ) { if ( edge[j].r-edge[i].l+1>ans ) ans = edge[j].r-edge[i].l+1; } } } } if ( ans > 0 ) cout<<ans<<endl; else cout<<"Nice work, Dima!"<<endl; return 0; }
