2 条题解
-
0
#include<bits/stdc++.h> using namespace std; const int N=3e3+10; vector<int>G[N]; int c[N],cc[N]; int tsp,cnt,dfn[N],low[N],scc[N]; stack<int> stk;bool instk[N]; void tarjan(int x) { dfn[x]=low[x]=++tsp; stk.push(x);instk[x]=1; for(int y:G[x]) { if(!dfn[y]) { tarjan(y); low[x]=min(low[x],low[y]); } else if(instk[y]) low[x]=min(low[x],dfn[y]); } if(dfn[x]==low[x]) { cnt++; for(int z=-1;z!=x;) { z=stk.top();stk.pop();instk[z]=0; scc[z]=cnt; cc[cnt]=min(c[z],cc[cnt]); } } } int main() { int n,m,p;scanf("%d%d",&n,&p); memset(c,0x3f,sizeof(c)); for(int i=1,x;i<=p;i++){scanf("%d",&x);scanf("%d",&c[x]);} scanf("%d",&m); memset(G,0,sizeof(G)); for(int i=1,x,y;i<=m;i++)scanf("%d%d",&x,&y),G[x].push_back(y); tsp=cnt=0;memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low)); memset(scc,0,sizeof(scc));memset(instk,false,sizeof(instk)); memset(cc,0x3f,sizeof(cc)); for(int i=1;i<=n;i++) if(!dfn[i] && c[i]!=0x3f3f3f3f) tarjan(i); vector<int>rd(cnt+1); for(int i=1,x,y;i<=n;i++)for(int j:G[i])if(scc[i]!=scc[j]) rd[scc[j]]++; for(int i=1;i<=n;i++)if(scc[i]==0){printf("NO\n%d",i);return 0;} int ans=0;for(int i=1;i<=cnt;i++)if(rd[i]==0)ans+=cc[i]; printf("YES\n%d",ans); return 0; } -
0
#include<bits/stdc++.h> using namespace std; const int N=3e3+10; vector<int>G[N]; int c[N],cc[N]; int tsp,cnt,dfn[N],low[N],scc[N]; stack<int> stk;bool instk[N]; void tarjan(int x) { dfn[x]=low[x]=++tsp; stk.push(x);instk[x]=1; for(int y:G[x]) { if(!dfn[y]) { tarjan(y); low[x]=min(low[x],low[y]); } else if(instk[y]) low[x]=min(low[x],dfn[y]); } if(dfn[x]==low[x]) { cnt++; for(int z=-1;z!=x;) { z=stk.top();stk.pop();instk[z]=0; scc[z]=cnt; cc[cnt]=min(c[z],cc[cnt]); } } } int main() { int n,m,p;scanf("%d%d",&n,&p); memset(c,0x3f,sizeof(c)); for(int i=1,x;i<=p;i++){scanf("%d",&x);scanf("%d",&c[x]);} scanf("%d",&m); memset(G,0,sizeof(G)); for(int i=1,x,y;i<=m;i++)scanf("%d%d",&x,&y),G[x].push_back(y); tsp=cnt=0;memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low)); memset(scc,0,sizeof(scc));memset(instk,False,sizeof(instk)); memset(cc,0x3f,sizeof(cc)); for(int i=1;i<=n;i++) if(!dfn[i] && c[i]!=0x3f3f3f3f) tarjan(i); vector<int>rd(cnt+1); for(int i=1,x,y;i<=n;i++)for(int j:G[i])if(scc[i]!=scc[j]) rd[scc[j]]++; for(int i=1;i<=n;i++)if(scc[i]==0){printf("NO\n%d",i);return 0;} int ans=0;for(int i=1;i<=cnt;i++)if(rd[i]==0)ans+=cc[i]; printf("YES\n%d",ans); return 0; }
- 1
信息
- ID
- 1878
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 7
- 标签
- 递交数
- 76
- 已通过
- 19
- 上传者