请增加hack数据
查看原帖
请增加hack数据
733569
chensiming_2022楼主2023/1/19 14:41

rt,我在别的地方都没过,就这里过了,麻烦针对我的代码增加hack数据(数据太水了)

代码

//#pragma GCC optimize(1,"Ofast","inline")
//#pragma GCC optimize(2,"Ofast","inline")
//#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
using namespace std;
const int N=8007,M=3007;
int n,m,a,b,x,inl[M],low[M],dfn[M],wei[M],mino[M],ch[M],mina[M],ans;
map<pair<int,int>,int> nst;
struct edg{
    int v,nxt;
}e[N];
int cnt,head[M],zsz,sz;
bool vis[M];
int stk[M],top;
void addE(int a,int b){
    e[++cnt]={b,head[a]};
    head[a]=cnt;
}
struct nedg{
    int v,nxt;
}ne[N];
int ncnt,nhead[M];
void naddE(int a,int b){
    ne[++ncnt]={b,nhead[a]};
    nhead[a]=ncnt;
}
void tarjan(int u){
    vis[u]=1;
    dfn[u]=low[u]=++zsz;
    stk[++top]=u;
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].v;
        if(!dfn[v])
            tarjan(v);
        if(vis[v])
            low[u]=min(low[u],low[v]);
    }
    if(dfn[u]==low[u]){
        wei[u]=++sz;
        mino[sz]=ch[u];
        mina[sz]=u;
        vis[u]=0;
        while(stk[top]!=u){
            wei[stk[top]]=sz;
            mino[sz]=min(mino[sz],ch[stk[top]]);
            mina[sz]=min(mina[sz],stk[top]);
            vis[stk[top]]=0;
            top--;
        }
        top--;
    }
}
void xj(){
    for(int i=1;i<=n;i++)
        for(int j=head[i];j;j=e[j].nxt){
            int v=e[j].v;
            if(wei[v]!=wei[i]){
                pair<int,int> f=make_pair(wei[i],wei[v]);
                if(nst.find(f)==nst.end()){
                    nst[f]=1;
                    naddE(wei[i],wei[v]);
                    inl[wei[v]]++;
                }
            }
        }
}
int dfs(int u){
    int anss=mina[u];
    for(int i=nhead[u];i;i=ne[i].nxt){
        int v=ne[i].v;
        if(mino[v]==0x3f3f3f3f)
            anss=min(anss,dfs(v));
    }
    return anss;
}
int main(){
    scanf("%d",&n);
    scanf("%d",&x);
    memset(ch,0x3f,sizeof ch);
    for(int i=1;i<=x;i++)
        scanf("%d%d",&a,&b),ch[a]=b;
    scanf("%d",&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d",&a,&b);
        addE(a,b);
    }
    for(int i=1;i<=n;i++)
        if(!dfn[i])
            tarjan(i);
    xj();
    bool flg=1;
    for(int i=1;i<=sz;i++)
        if(inl[i]==0){
            if(mino[i]==0x3f3f3f3f){
                flg=0;
                break;
            }
            ans+=mino[i];
        }
    if(flg){
        puts("YES");
        printf("%d",ans);
    }
    else{
        puts("NO");
        ans=0x3f3f3f3f;
        for(int i=1;i<=sz;i++)
            if(inl[i]==0)
                if(mino[i]==0x3f3f3f3f)
                    ans=min(dfs(i),ans);
        printf("%d",ans);
    }
    return 0;
}

record(洛谷)

另:烦请大佬帮忙看看哪错了

2023/1/19 14:41
加载中...