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;
}
另:烦请大佬帮忙看看哪错了