莫名错误求助
  • 板块P1262 间谍网络
  • 楼主Veranda
  • 当前回复3
  • 已保存回复3
  • 发布时间2022/11/13 15:16
  • 上次更新2023/10/27 03:06:30
查看原帖
莫名错误求助
231800
Veranda楼主2022/11/13 15:16
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <stack>
#include <vector>

using namespace std;

const int N = 3010;
const int M = 8010;

int n,m,p;
int w[N];
int h[N],e[M],ne[M],idx;
int scc_cnt;
int id[N];
int dfn[N],low[N];
int timestamp;
bool st[N];
int Size[N];
stack<int> q;
int rout[N];
queue<int> Scc[N];

void add(int a,int b) {
	e[idx] = b,ne[idx] = h[a],h[a] = idx ++;
}

void tarjan(int u) {
	dfn[u] = low[u] = ++ timestamp;
	q.push(u);
	st[u] = 1;

	for(int i = h[u]; ~i; i = ne[i]) {
		int j = e[i];

		if(!dfn[j]) {
			tarjan(j);
			low[u] = min(low[u],low[j]);
		}

		else if(st[i]) low[u] = min(low[u],low[j]);
	}

	if(dfn[u] == low[u]) {
		scc_cnt ++;
		int y = 0;
		do {
			y = q.top();
			q.pop();
			id[y] = scc_cnt;
			Size[scc_cnt] ++;
			st[y] = 0;
			Scc[scc_cnt].push(y);
		} while(y != u);
	}
}

int main() {
	memset(h,-1,sizeof h);

	cin >> n;
	cin >> p;
	for(int i = 1; i <= p; i ++) {
		int ind,val;
		cin >> ind >> val;
		w[ind] = val;
	}
	cin >> m;
	for(int i = 1; i <= m; i ++) {
		int a,b;
		cin >> a >> b;
		add(a,b);
	}

	for(int i = 1; i <= n; i ++) {
		if(!dfn[i]) tarjan(i);
	}

	for(int i = 1; i <= n; i ++) {
		for(int j = h[i]; ~j; j = ne[j]) {
			int b = id[e[j]],a = id[i];
			if(a != b) rout[b] ++;
		}
	}

	int res = 0,min_idx = 0x3f3f3f3f;
	bool flg = 0;
	for(int i = 1; i <= scc_cnt; i ++) {
		if(rout[i] == 0) {
			bool f = 0;
			int minn = 0x3f3f3f3f;
			int Min = 0x3f3f3f3f;
			while(!Scc[i].empty()) {
				int t = Scc[i].front();
				Scc[i].pop();
				Min = min(Min,t);
				if(w[t]) {
					minn = min(minn,w[t]);
					f = 1;
				}
			}
			if(f) res += minn;
			else {
				flg = 1;
				min_idx = min(min_idx,Min);
			}
		}
	}
	if(flg) {
		cout << "NO" << endl << min_idx;
	} else {
		cout << "YES" << endl << res;
	}
}

tarjan 缩点,实在调不出来了,萌新求助

2022/11/13 15:16
加载中...