hack WA 了求调 qwq
查看原帖
hack WA 了求调 qwq
750535
Trubiacy_楼主2024/8/27 16:58
#include <bits/stdc++.h>
#define int long long
#define x first
#define y second
#define INF 0x3f3f3f3f
using namespace std;
typedef pair<int,int> pii;
const int N=3e3+29;

int _,n,m,p,w[N];
vector<int> a[N];
int dfn[N],low[N],ts,id[N],scc_cnt,ned[N],minn[N],ind[N];
bool st[N];
stack<int> s;

void tarjan(int u){
    dfn[u]=low[u]=++ts;
    s.push(u);st[u]=true;
    for(auto v:a[u]){
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(st[v]) low[u]=min(low[u],dfn[v]);
    }
    if(dfn[u]==low[u]){
        int t;
        scc_cnt++;
        do{
            t=s.top();s.pop();
            st[t]=false;
            id[t]=scc_cnt;
            ned[scc_cnt]=min(ned[scc_cnt],w[t]);
            minn[scc_cnt]=min(minn[scc_cnt],t);
        }while(t^u);
    }
}

void tbcsolve(){
    memset(minn,0x3f,sizeof minn);
    memset(w,0x3f,sizeof w);
    memset(ned,0x3f,sizeof ned);
    cin>>n>>p;
    for(int i=1;i<=p;i++){
        int x,y;
        cin>>x>>y;
        w[x]=y;
    }
    cin>>m;
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        a[u].push_back(v);
    }
    for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);
    for(int i=1;i<=n;i++){
        for(auto j:a[i]){
            int ti=id[i],tj=id[j];
            if(ti^tj) ind[tj]++;
        }
    }
    bool f=true;
    int ans1=0,ans2=INF;
    for(int i=1;i<=scc_cnt;i++){
        if(ind[i]) continue;
        if(ned[i]>=INF){
            f=false;
            ans2=min(ans2,minn[i]);
        }
        else if(f) ans1+=ned[i];
    }
    if(f) cout<<"YES"<<endl<<ans1;
    else cout<<"NO"<<endl<<ans2;
}

void tbcclear(){
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int SHENSELF=1;
    // cin>>SHENSELF;
    for(_=1;_<=SHENSELF;_++) {
        tbcsolve();
        if(_<SHENSELF) tbcclear();
    }
    return 0;
}
2024/8/27 16:58
加载中...