HIHO #1185 : 连通性·三

2024-08-30 20:08

文章标签 连通性 hiho 1185

本文主要是介绍HIHO #1185 : 连通性·三，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接

先使用tarjan算法，计算强连通分量，进行缩点成DAG，然后在使用拓扑排序计算

tarjan中，我们只需要从1号节点计算，因为开始时在1号点。
建立新图的过程中，1号点不能到达的点也不用建立到新图里面

#include<bits/stdc++.h>
using namespace std;
#define cl(a,b) memset(a,b,sizeof(a))
#define LL long long
#define pb push_back
#define gcd __gcd#define For(i,j,k) for(int i=(j);i<k;i++)
#define lowbit(i) (i&(-i))
#define _(x) printf("%d\n",x)const int maxn = 2e5+2000;
const int inf  = 1 << 28;int n,m;vector<int> G[maxn];
int w[maxn],w1[maxn];int counter,top;
int stk[maxn],ins[maxn],dfn[maxn],low[maxn];int belong[maxn],cnt;void dfs(int u){low[u]=dfn[u]= ++counter;stk[top++] = u;ins[u] = true;for(int i=0;i<G[u].size();i++){int v = G[u][i];if(!dfn[v]){dfs(v);low[u]=min(low[u],low[v]);}else if(ins[v]){low[u]=min(low[u],dfn[v]);}}if(low[u]==dfn[u]){++cnt;do{int x = stk[--top];ins[x] = false;belong[x] = cnt;w1[cnt]+=w[x];}while(stk[top]!=u);}
}vector<int> G2[maxn];
int deg[maxn];void init(int n){counter=top=cnt=0;for(int i=0;i<=n;i++){w[i]=w1[i]=dfn[i]=low[i]=ins[i]=0;G2[i].clear();G[i].clear();deg[i]=0;}
}int dp[maxn],ans;
void t_sort(){stack<int> s;cl(dp,0);s.push(belong[1]);//开始在原图1位置dp[belong[1]]=w1[belong[1]];while(!s.empty()){int u = s.top();s.pop();for(int i=0;i<G2[u].size();i++){int v = G2[u][i];dp[v] =  max(dp[v],dp[u]+w1[v]);if(--deg[v]==0){s.push(v);}}}
}int main(){cin>>n>>m;init(n);for(int i=1;i<=n;i++)cin>>w[i];for(int i=0;i<m;i++){int x,y;cin>>x>>y;G[x].pb(y);}dfs(1);//缩点，连通分量的编号从1到cnt的闭区间for(int u=1;u<=n;u++){for(int i=0;i<G[u].size();i++){int v = G[u][i];int x = belong[u];int y = belong[v];if(x==y||x==0||y==0)continue;//自环和不能到达的边不要G2[x].pb(y);//printf("%d --> %d\n",x,y);deg[y]++;}}//printf("cnt = %d\n",cnt);
//for(int i=1;i<=n;i++){
//    printf("i = %d, bi = %d\n",i,belong[i]);
//}t_sort();for(int i=1;i<=cnt;i++){if(dp[i]>ans)ans=dp[i];}cout<<ans<<endl;return 0;
}