有向图，每个点有点权，找出途中的所有路径中，路径上最大值和最小值的差值 的最大值
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 ",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 ",ans); return 0; }
那么再来想想，是什么的重复运算，导致的超时？
大概是一条路径的多次访问，比如5->4->3->2->1
按着程序来说，那是要dfs进入5次
所以其实从5进入最好，
但是题目说数据有环啊，怎么办
所以我们要tarjan缩点
然后我缩完了点，
把每个点的fa重置，作为新节点，然后边全部重新装入了新的gg中
呃，我为什么还是80？？？
#include<cstdio> #include<cstdlib> #include<stack> #include<vector> #include<algorithm> #include<cstring> using namespace std; int n,m; const int N=100003; int d[N]; vector <int> g[N]; int fa[N],mn[N],mx[N]; int dfn[N],low[N],tt; bool in_s[N]; stack <int> s; void tarjan(int x) { dfn[x]=low[x]=++tt; in_s[x]=true,s.push(x); int sz=g[x].size() ; for(int i=0;i<sz;i++) { int v=g[x][i]; if(!dfn[v]) { tarjan(v); low[x]=min(low[x],low[v]); } else if(in_s[v]) low[x]=min(low[x],low[v]); } if(low[x]==dfn[x]) { mn[x]=mx[x]=d[x]; while(s.top() !=x) { in_s[s.top() ]=false,fa[s.top() ]=x; mn[x]=min(mn[x],d[s.top() ]),mx[x]=max(mx[x],d[s.top() ]); s.pop() ; } in_s[x]=false,s.pop() ; fa[x]=x; } } vector <int> gg[N]; int ans; bool vis[N],have[N]; void dfs(int x,int nw_mn,int nw_mx) { bool ok=false; int sz=gg[x].size() ; for(int i=0;i<sz;i++) { int v=gg[x][i]; if(vis[v] ) continue; ok=true; vis[v]=true; dfs(v,min(nw_mn,mn[v]),max(nw_mx,mx[v])); } if(!ok) ans=max(ans,nw_mx-nw_mn); }
//超时的罪魁祸首！！！！！ int in[N]; 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++) if(!dfn[i]) tarjan(i); for(int i=1;i<=n;i++) { int t=fa[i]; int sz=g[i].size() ; for(int j=0;j<sz;j++) { int v=fa[g[i][j]]; if(v!=t) in[v]++,gg[t].push_back(v) ; } } for(int i=1;i<=n;i++) { if(fa[i]!=i) continue; if(in[i]) continue; memset(vis,false,sizeof(vis)); dfs(i,mn[i],mx[i]); } printf("%d ",ans); return 0; }
看了半天然后发现
虽然缩了点，解决了有环的问题，
但是环只有20分，并且不是最大点，
！！！！！最后的点关键在解决点数是1e5的情况！！！！！
然后我就用上了拓扑序
ac不易啊
未完待续。。。