tarjan模板样例过不去求助/kk
查看原帖
tarjan模板样例过不去求助/kk
508316
cyhyyds楼主2021/9/15 21:54

真的不知道哪里错了,调了好久。

两问好像都不过去,已经对题解看了好多遍了!

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 7;
const int M = 3e5 + 7;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;

struct Edge {
	int nxt;
	int to;
}e[M];

int head[M], __ = 0, w[N], n, m;

inline void add_edge (int x, int y) {
	e[++ __].nxt = head[x];
	e[__].to = y;
	head[x] = __;
}

int sum[N], minn[N], low[N], dfn[N], sjc = 0, sta[N], top = 0, col[N], co = 0;

void tarjan (int x) {
	dfn[x] = low[x] = ++ sjc;
	
	sta[++ top] = x;
	
	for (int i = head[x]; i; i = e[i].nxt) {
		int v = e[i].to;
		
		if (dfn[v] == 0) {
			tarjan (v);
			
			low[v] = min (low[v], low[x]);
		}
		
		else if (col[v] == 0) {
			low[v] = min (low[x], low[v]);
		}
	}
	
	if (dfn[x] == low[x]) {
		int y;
		
		co ++;
		
		do {
			y = sta[top --];
			
			col[y] = co;
			
			if (minn[co] > w[y]) {
				minn[co] = w[y];
				
				sum[co] = 1;
			}
			
			else if (minn[co] == w[y]) {
				sum[co] ++;
			}
			
		}while (y != x);
	}
}

int main () {
	memset (minn, inf, sizeof (minn)); 
	
	scanf ("%d", &n);
	
	for (int i = 1; i <= n; i ++) {
		scanf ("%d", &w[i]);
	}
	
	scanf ("%d", &m);
	
	for (int i = 1, x, y; i <= m; i ++) {
		scanf ("%d%d", &x, &y);
		
		add_edge (x, y); 
	}
	
	for (int i = 1; i <= n; i ++) {
		if (dfn[i] == 0) {
			tarjan (i);
		}
	}
	
	int ans1 = 0, ans2 = 1;
	
//	for (int i = 1; i <= co; i ++) {
//		cout << minn[i] << " ";
//	}
	
	for (int i = 1; i <= co; i ++) {
		ans1 += minn[i];
		
		ans1 %= mod;
	}
	
	for (int i = 1; i <= co; i ++) {
		ans2 *= sum[i];
		
		ans2 %= mod;
	}
	
	printf ("%d %d", ans1, ans2);
	
	return 0;
}
2021/9/15 21:54
加载中...