Description

 

Input

Output

 

Sample Input

4 41 2 1 102 4 3 51 3 1 52 4 2 7

Sample Output

62 3 4 5 6 7 

 

 

题解

• 显然可以发现，答案的l和r一定是某条路径的l和r
• 那么可以把r进行排序，然后二分l
• 判断是否所有的边都符合，合法的用并查集连起来
• 如果1和n在同一个并查集内，说明可以相互到达，那么就是合法的
• 再考虑另一种做法，可以把r从大到小排序
• 枚举l和r，然后来个最优性剪枝，如果当前枚举的l和r小于ans，直接break
• 同样的可以用并查集维护，这样实测会快很多

代码

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #define N 1010 5 #define M 3010 6 using namespace std; 7 struct edge {
   int x,y,l,r;}a[M]; 8 int n,m,ans,num,fa[N]; 9 bool cmp(edge a,edge b) { return a.r>b.r; }10 int getfather(int x) { return fa[x]==x?x:fa[x]=getfather(fa[x]); }11 int main()12 {13     scanf("%d%d",&n,&m);14     for (int i=1;i<=m;i++) scanf("%d%d%d%d",&a[i].x,&a[i].y,&a[i].l,&a[i].r);15     sort(a+1,a+m+1,cmp);16     for (int i=1;i<=m;i++)17     {18         for (int j=1;j<=n;j++) fa[j]=j;19         for (int j=1;j<=m;j++)20             if (a[j].l<=a[i].l)21             {22                 int p=a[j].r-a[i].l+1;23                 if (p
        
         num)) break;24                 int u=getfather(a[j].x),v=getfather(a[j].y);25                 if (u!=v) fa[u]=v;26                 if (getfather(1)==getfather(n)) { ans=p,num=a[i].l; break; }27             }28     }29     printf("%d\n",ans);30     for (int i=num;i<=num+ans-1;i++) printf("%d ",i);31 }