旅行

题面

题意

满足两点间路径上所有l，r限制的最优解

样例

Example1.in

Example1.out

6
2 3 4 5 6 7

Example2.in

2 2
1 2 1 3
1 2 4 6

Example2.out

3
1 2 3

题解

因为每次只能通过一个虫洞，所以最后的答案一定是一个连续序列。

记录l,r，爆搜是 O(n^3) 的

考虑优化，枚举每个固定的r，再二分l，检查1,n是否连通，是 O(n^2 * log n)的

但其实不用二分每个 l ，连上就好了，O(n^2)

代码

 1 #include<bits/stdc++.h>
 2 #define For(i,a,b) for(register int i=(a);i<=(b);i++)
 3 #define Rof(i,a,b) for(register int i=(a);i>=(b);i--)
 4 using namespace std;
 5 const int maxn=5010;
 6 int n,m,head[maxn],cnt,fa[maxn],l[maxn],r[maxn],ansl,ansr;
 7 struct Edge{
 8     int u,v,l,r;
 9 }edge[maxn];
10 inline bool temp(Edge a,Edge b){return a.r>b.r;}
11 inline int findfa(int x){
12     return x==fa[x]?x:fa[x]=findfa(fa[x]);
13 }
14 inline void uni(int a,int b){
15     int x=findfa(a),y=findfa(b);
16     if(x!=y) fa[x]=y;
17 }
18 signed main(){
19     scanf("%d%d",&n,&m);
20     For(i,1,m){
21         scanf("%d%d%d%d",&edge[i].u,&edge[i].v,&edge[i].l,&edge[i].r);
22         l[i]=edge[i].l,r[i]=edge[i].r;//if(edge[i].u>edge[i].v) swap(edge[i].u,edge[i].v);
23     }
24     sort(edge+1,edge+1+m,temp),sort(l+1,l+1+m),sort(r+1,r+m+1);
25     For(i,1,m){
26         For(j,1,m) fa[j]=j;
27         int pos=1;
28         Rof(j,m,1){
29             if(l[i]>r[j]) break;
30             while(edge[pos].r>=r[j]){
31                 if(edge[pos].l<=l[i]) uni(edge[pos].u,edge[pos].v);
32                 pos++;
33             }
34             if(findfa(1)==findfa(n)){
35                 if(r[j]-l[i]>ansr-ansl) ansl=l[i],ansr=r[j];
36                 break;
37             }
38         }
39     }
40     printf("%d
",ansr-ansl+1);
41     For(i,ansl,ansr) printf("%d ",i);
42 }

View Code

教训

没试过这么降智地调一题：l , r 打混、没重置并查集、把循环条件写成了草稿上的break条件

所以在宿舍不能看打牌，要睡觉