有向图，每个点有点权，找出途中的所有路径中，路径上最大值和最小值的差值 的最大值
20%，N<=50
40%，N<=100
60%，N<=1000
另外20%，图中无环
100%，N<=100 000，M<=500 000
点权均为int型正整数
60分算法：
当然是练习暴力啦，不过这暴力我wa了好多次，
最高得分60
学到一个方法：枚举路径，可以直接全部枚举起终点
#include<cstdio> #include<cstdlib> #include<vector> using namespace std; int n,m; const int N=1003; vector <int> g[N]; int d[N],ans; bool vis[N]; void dfs(int u,int ed,int mx,int mn) { if(u==ed) { ans=max(ans,mx-mn); return ; } int sz=g[u].size() ; for(int i=0;i<sz;i++) { int v=g[u][i]; if(vis[v]) continue; vis[v]=true; dfs(v,ed,max(mx,d[v]),min(mn,d[v])); vis[v]=false; } } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&d[i]); int x,y; while(m--) { scanf("%d%d",&x,&y); g[x].push_back(y); } for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(i==j) continue; vis[i]=true; dfs(i,j,d[i],d[i]); vis[i]=false; } } printf("%d\n",ans); return 0; }
然后我改良了一下，
找所有路径，我只枚举起点
速度30ms->4ms（前6个点）
然后6个点->8个点
ヽ(￣▽￣)?
void dfs(int u,int mx,int mn) { int sz=g[u].size() ; bool conti=false; for(int i=0;i<sz;i++) { int v=g[u][i]; if(vis[v]) continue; conti=true; vis[v]=true; dfs(v,max(mx,d[v]),min(mn,d[v])); vis[v]=false; } if(!conti) ans=max(ans,mx-mn); } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&d[i]); int x,y; while(m--) { scanf("%d%d",&x,&y); g[x].push_back(y); } for(int i=1;i<=n;i++) { vis[i]=true; dfs(i,d[i],d[i]); vis[i]=false; } printf("%d\n",ans); return 0; }
那么再来想想，是什么的重复运算，导致的超时？
大概是一条路径的多次访问，比如5->4->3->2->1
按着程序来说，那是要dfs进入5次
所以其实从5进入最好，
但是题目说数据有环啊，怎么办
所以我们要tarjan缩点
明天再写
原文：https://www.cnblogs.com/xwww666666/p/11410101.html