关于 P2194 10分WA的问题
  • 板块学术版
  • 楼主ztx__
  • 当前回复0
  • 已保存回复0
  • 发布时间2020/7/28 19:05
  • 上次更新2023/11/6 21:56:27
查看原帖
关于 P2194 10分WA的问题
125018
ztx__楼主2020/7/28 19:05

看了一下题解,好像找不到错,哪位dalaodalao能帮忙找一下错啊qwqqwq

传送门

#include <bits/stdc++.h>
using namespace std;
#define MAXN 100005
#define INF 0x3fffffff
#define MOD 1000000007
int n,m,w[MAXN];
vector<int> g[MAXN];
int step,dfn[MAXN],low[MAXN],tot,belong[MAXN],minn[MAXN],cnt[MAXN];
long long ans,ans2=1;
bool vis[MAXN];
stack<int> stk;
void tarjan(int u){
    dfn[u]=low[u]=++step;
    vis[u]=true;
    stk.push(u);
    for(int i=0;i<g[u].size();i++){
        int v=g[u][i];
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }else if(vis[v]){
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(dfn[u]==low[u]){
        tot++;
        while(stk.top()!=u){
            int v=stk.top();
            stk.pop();
            vis[v]=false;
            belong[v]=tot;
        }
        int v=stk.top();
            stk.pop();
            vis[v]=false;
            belong[v]=tot;
    }
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",w+i);
    }
    scanf("%d",&m);
    for(int i=1;i<=m;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        g[u].push_back(v);
    }
    for(int i=1;i<=n;i++){
        if(!dfn[i]){
            tarjan(i);
        }
    }
    fill(minn+1,minn+1+tot,INF);
    for(int u=1;u<=n;u++){
        minn[belong[u]]=min(minn[belong[u]],w[belong[u]]);
    }
    for(int u=1;u<=n;u++){
        if(w[u]==minn[belong[u]]){
            cnt[belong[u]]++;
        }
    }
    for(int i=1;i<=tot;i++){
        ans+=minn[i];
        ans2*=cnt[i];
        ans2%=MOD;
    }
    printf("%lld %lld\n",ans,ans2);
    return 0;
}
2020/7/28 19:05
加载中...