强连通
学习资料
强连通，又名\(scc\)，即有向图中可以相互到达的子图，如 \(\quad\) 3->4;4->3 3与4即一对\(scc\);
\(Tarjan\)的作用可以将有环图转为有向无环图
既然是有向无环图 拓扑序的优势就体现出来了
更新树中的节点就可以通过拓扑排序进行
最优贸易
题意分析
在一个有向有环图中，求出从\(1\)开始的到达\(n\)的所有路径中，最大的点权差
这时候的数据结构狂魔就拿出了\(Tarjan\),重新建图为\(DAG\)，用\(BFS\)拓扑\(dp\)一下
就\(A\)了这题
点击查看代码
#include<bits/stdc++.h>
#define maxn 100010
#define N 500010
#define int long long
using namespace std;
int head[N],nex[N],ver[N],tot;
int dfs[maxn],low[maxn],vis[maxn],dp[maxn],Gro[maxn],st[maxn];
int cnt,top,group,MaxG[maxn],MinG[maxn],in[maxn];
int n,m,val[maxn];
void add(int u,int v)
{
ver[++tot]=v; nex[tot]=head[u];head[u]=tot;
}
int head2[N],nex2[N],ver2[N],tot2,pre_min[N];
void add2(int u,int v)
{
ver2[++tot2]=v; nex2[tot2]=head2[u]; head2[u]=tot2;
}
void tarjan(int x)
{
dfs[x]=low[x]=++cnt;
st[++top]=x; vis[x]=1;
for(int i=head[x];i;i=nex[i])
{
int v=ver[i];
if(!dfs[v])
{;
tarjan(v);
low[x]=min(low[x],low[v]);
}
else
if(vis[v])
{
low[x]=min(low[x],dfs[v]);
}
}
if(dfs[x]==low[x])
{
int y; group++;
do
{
y=st[top]; top--;
Gro[y]=group; vis[y]=0;
MaxG[group]=max(MaxG[group],val[y]);
MinG[group]=min(MinG[group],val[y]);
}while(x!=y);
}
}
queue<int> q;
void BFS(int x)
{
pre_min[x]=min(pre_min[x],MinG[x]);
dp[x]=max(dp[x],MaxG[x]-pre_min[x]);
while(!q.empty())
{
int x=q.front(); q.pop();
for(int i=head2[x];i;i=nex2[i])
{
int v=ver2[i];
in[v]--;
pre_min[v]=min(pre_min[x],MinG[v]);
dp[v]=max(dp[x],max(dp[v],MaxG[v]-pre_min[v]));
if(!in[v])
{
q.push(v);
}
}
}
}
signed main()
{
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++) scanf("%lld",&val[i]);
for(int i=1,u,v,c;i<=m;i++)
{
scanf("%lld%lld%lld",&u,&v,&c);
if(c==1) add(u,v);
if(c==2) add(u,v),add(v,u);
}
memset(MinG,100,sizeof MinG);
for(int i=1;i<=n;i++) if(!dfs[i]) tarjan(i);
// for(int i=1;i<=n;i++) cout<<Gro[i]<<" ";
for(int i=1;i<=n;i++)
{
for(int j=head[i];j;j=nex[j])
{
int v=ver[j];
if(Gro[v]!=Gro[i])
{
// cout<<i<<" = "<<Gro[i]<<"----"<<v<<" = "<<Gro[v]<<endl;
add2(Gro[i],Gro[v]);
in[Gro[v]]++;
}
}
}
for(int i=1;i<=group;i++)
{
// cout<<i<<" "<<in[i]<<endl;;
if(!in[i])
{
// cout<<"!! "<<i<<endl;
q.push(i);
}
}
memset(pre_min,127,sizeof pre_min);
BFS(Gro[1]);
cout<<dp[Gro[n]];
return 0;
}
/*
5 5
4 3 5 6 1
1 2 1
1 4 1
2 3 2
3 5 1
4 5 2
12 14
100 10 11 10 10 1 1 1 1 1 1 1
1 4 1
4 5 2
1 2 1
2 3 2
5 6 1
6 7 2
7 12 1
3 8 1
2 5 1
8 9 2
3 10 1
10 11 2
11 12 1
9 12 1
*/
但是 这题其实仅用简简单单的\(DFS\)就可以解决\(\quad\) 再次感谢巨佬@HY喵的出其不意的思路
在每次\(DFS\)时，用一个\(Flag\)判断是否可以更新
点击查看代码
void dfs(int x,int minx,int pre) //x表示当前访问的节点编号，minx表示目前为止的最小的商品价格，pre表示上一个节点的编号
{
int flag=1; //用于判断是否已被访问过，需要终止
minx=min(c[x],minx); //判断本次的商品价格是否是最小值
if (mi[x]>minx) mi[x]=minx,flag=0; //判断mi数组（记录了每次的最小值）并更新，在更新的同时把flag设为0（不用退出了）
做动态规划； //别着急flag还会继续更新的
if (flag) return; //退出，千万不能露，不然程序就会放飞自我，堆栈溢出->完美MLE只有10分。
for (int i=0;i<g[x].size();i++) dfs(g[x][i],minx,x); //继续进行递归调用，访问目前节点能访问到的节点。
}