题目链接
题意：有n个点m条无向边。初始你需要选择一个整数x，走第i条边的限制为Li <= x <= Ri，假设1-n的一条路径上可以选择的整数x有ans，问你最大的ans。
思路: 这个题好多做法....首先我们可以先明确判断能否从1到达n 可以用并查集或者dfs
那么对于并查集,
我们可以想一下,我们已知区间的左端点,通过维护区间的右端点,就可以找到一个区间,那么我们就以所有路径的为起点,以其左端点为基础去维护右端点找到最大值..
这个过程中用并查集来判断1-n是否连通，并且需要注意的是由于同两个点可能有很多的区间,所以我们要以右端点进行排序,
使得到达n时优先走右端点大的..
#include<bits/stdc++.h> using namespace std; const int maxn=1e3+10; typedef long long ll; int pre[maxn]; int n,m; struct node { int u,v; int l,r; }q[3*maxn]; int cmp(node a,node b) { return a.r>b.r; } void build() { for(int i=1;i<=n;i++) pre[i]=i; return ; } int find(int x) { if(x==pre[x]) return x; return pre[x]=find(pre[x]); } void join(int x,int y) { int f1=find(x); int f2=find(y); if(f1!=f2) pre[f1]=f2; return ; } int main() { int mi,ma=-1; cin>>n>>m; for(int i=1;i<=m;i++) { cin>>q[i].u>>q[i].v>>q[i].l>>q[i].r; } sort(q+1,q+1+m,cmp); for(int i=1;i<=m;i++) { build(); mi=q[i].r; for(int j=1;j<=m;j++) { if(q[j].l>q[i].l||q[j].r<q[i].l) continue; join(q[j].u,q[j].v); mi=min(mi,q[j].r); if(find(1)==find(n)) { ma=max(ma,mi-q[i].l+1); } } } if(ma==-1) { printf("Nice work, Dima!\n"); } else printf("%d\n",ma); return 0; }
dfs +剪枝也可以过这个题
有两个剪枝
1.如果当前已经走过该点,并且上次走过的 rel[v]<=l&&rer[v]>=r 剪枝
2.如果当前的答案小于 维护的ans 剪枝
#include<bits/stdc++.h> #define inf 0x3f3f3f3f using namespace std; const int maxn=1e3+10; typedef long long ll; int n,m; int ans,book[maxn]; struct node { int to; int l; int r; }; vector<node>vt[maxn]; int rel[maxn],rer[maxn]; void dfs(int v,int L,int R) { if(v==n) { ans=max(ans,R-L+1); return ; } for(int i=0;i<vt[v].size();i++) { int x=vt[v][i].to; int le=max(vt[v][i].l,L); int ri=min(vt[v][i].r,R); if(rel[x]<=le&&rer[x]>=ri) continue; if(ans>=ri-le+1) continue; book[x]=1; rel[x]=le; rer[x]=ri; dfs(x,le,ri); book[x]=0; } return ; } int main() { cin>>n>>m; int w,x,y,z; node a; for(int i=1;i<=m;i++) { cin>>w>>x>>y>>z; a.to=x; a.l=y; a.r=z; vt[w].push_back(a); a.to=w; vt[x].push_back(a); } ans=0; dfs(1,-inf,inf);//初始正负无穷 if(ans) cout<<ans<<endl; else cout<<"Nice work, Dima!"<<endl; return 0; } Marcus-Bao 认证博客专家 推荐系统 ACM算法竞赛 机器学习 本科毕业于国内知名四非大学，现中国科学院大学博士生，中国科学院计算技术研究所vipl实验室，老年ACM铁牌退役选手，喜欢算法竞赛，会点数据结构和算法，熟悉c++，python等；现阶段研究方向主要为机器学习与数据挖掘，比较关注推荐系统，发过顶会，炼过丹，平时博客主要记录些关于算法、数据结构，人工智能技术以及平时看的论文总结分享等，欢迎大家关注我，一起多多交流共同进步！
