洛谷P3387缩点

传送门

有向图。。
代码中有两种方法，拓扑排序和记忆化搜索
#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <queue>

#define re register

using namespace std ;

const int maxn = 1e5 + 4 ;

inline int read () {

	int f = 1 , x = 0 ;

	char ch = getchar () ;

	while(ch > '9' || ch < '0')  {if(ch == '-')  f = -1 ; ch = getchar () ;}

	while(ch >= '0' && ch <= '9')  {x = (x << 1) +(x << 3) + ch - '0' ; ch = getchar () ;}

	return x * f;

}

int n , m , a[maxn] , u , v , ans ;

int head[maxn] , tot , head2[maxn] , tot2 ;

struct Edge {

	int from , to , next ;

}edge[maxn << 1] , edge2[maxn] ;

inline void add(int u , int v) {

	edge[++tot].from = u ;

	edge[tot].to = v ;

	edge[tot].next =head[u] ;

	head[u] = tot ;

}

inline void add2(int u , int v) {

	edge2[++tot2].from = u ;

	edge2[tot2].to = v;

	edge2[tot2].next = head2[u];

	head2[u] = tot2;

}

int stack[maxn] , belong[maxn] , top , cnt , num[maxn] ;

int low[maxn] , dfn[maxn] , ind , dis[maxn] ;

bool ins[maxn] ;

inline void tarjan(int x) {

    dfn[x] = low[x] = ++ind;

    stack[++top] = x ;

    ins[x] = true ;

    for(re int i = head[x] ; i; i = edge[i].next) {

        int v = edge[i].to ;

        if(!dfn[v]) {

            tarjan(v) ;

            low[x] = min(low[x] , low[v]);

        }

        if(ins[v]) {

            low[x] = min(low[x] , dfn[v]);

        }

    }

    int k = 0;

    if(dfn[x] == low[x]) {

        ++cnt;

        do{

            k = stack[top];

            top--;

            ins[k] = false;

            num[cnt]++;

            dis[cnt] += a[k];

            belong[k] = cnt;

        }while (k != x);

    }

}

queue<int> q;

int dis2[maxn] , in[maxn] ;

inline int topo() {

    for(re int i = 1 ; i <= cnt ; ++ i)

    	if(!in[i]) {

    		q.push(i);

    		dis2[i] = dis[i];

    	}

    while(!q.empty()) {

    	int cur = q.front();

    	q.pop() ;

    	for(re int i = head2[cur] ; i ; i = edge2[i].next) {

    		int v = edge2[i].to ;

    		dis2[v] = max(dis2[v] , dis2[cur] + dis[v]) ;

    		in[edge2[i].to]-- ;

    		if(!in[edge2[i].to])

    			q.push(edge2[i].to) ;

    	}

    }

    for(re int i = 1 ; i <= n ; ++ i)

    	ans = max(ans , dis2[i]) ;

    return ans;

}

int main () {

	n = read () ; m =read() ;

	for(re int i = 1 ; i <= n ; ++ i)

		a[i] = read () ;

	for(re int i = 1 ; i <= m ; ++ i) {

		u = read () ; v = read () ;

		add(u , v) ;

	}

	for(re int i = 1 ; i <= n ; ++ i)

		if(!dfn[i])  tarjan(i) ;

	for(re int i = 1 ; i <= tot ; ++ i) {

        if(belong[edge[i].from] != belong[edge[i].to]) {

            add2(belong[edge[i].from] , belong[edge[i].to]) ;

            in[belong[edge[i].to]]++ ;

        }

    }

	printf("%d\n" , topo()) ;

	return 0 ;

}
巴特西

洛谷P3387缩点

传送门

最新文章

热门文章
