Tarjan算法 92分Wa on #13 求调
查看原帖
Tarjan算法 92分Wa on #13 求调
1147725
chenyinuo2011楼主2024/7/18 10:16
#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e3 + 5,inf=0x3f3f3f3f;
vector<int> G[maxn];
stack<int> s;
int n, m,p;
int dfn[maxn],low[maxn],Min[maxn],a[maxn],b[maxn]; 
bool used[maxn], vis[maxn];
int num, cnt,ans;
// num为强连通分量的数量
int belong[maxn], in[maxn],In[maxn];
// belong记录属于哪一个强连通分量
void tarjan(int x) {
    dfn[x] = low[x] = ++cnt;
    s.push(x);
    vis[x] = used[x] = true;
    for (auto q : G[x]) {
        if (!dfn[q]) {
            tarjan(q);
            low[x] = min(low[x], low[q]);
        } else if (vis[q])
            low[x] = min(low[x], dfn[q]);
    }
    if (low[x] == dfn[x]) {
        num++;
        while (s.top() != x) {
            int t = s.top();
            belong[t] = num;
            s.pop();
            Min[num]=min(Min[num],a[t]);
            vis[x] = false;  //标记是否在栈中
        }
        s.pop();
        belong[x] = num;
        vis[x] = false;
        Min[num]=min(Min[num],a[x]);
    }
}
int main() {
	memset(a,inf,sizeof(a));
	memset(Min,inf,sizeof(Min));
    cin >> n>>m;
   	for(int i=1;i<=m;i++){
   		int tmp;cin>>tmp;
   		cin>>a[tmp];
	}
	cin>>p;
	for(int i=1;i<=p;i++){
		int x,y;
		cin>>x>>y;
		G[x].push_back(y);
		In[y]++;
	}
    for (int i = 1; i <= n; i++) {
        if (!used[i]&&a[i]!=inf)
            tarjan(i);  //未被访问过
    }
    for(int i=1;i<=n;i++){
    	if(dfn[i]==0){
    		cout<<"NO\n"<<i;
    		return 0;
		}
	}
   	 for (int i = 1; i <= n; i++) {
        for (auto j : G[i]) {
            if (belong[i] != belong[j]) {
        		in[belong[j]]++;
            }
        }
    }
    for(int i=1;i<=num;i++){
    	if(in[i]==0){
    		ans+=Min[i];
		}
	}
	cout<<"YES\n"<<ans;
    return 0;
}
2024/7/18 10:16
加载中...