• 杨小辉
    了解作者
  • C/C++
    开发工具
  • 4KB
    文件大小
  • zip
    文件格式
  • 0
    收藏次数
  • 1 积分
    下载积分
  • 0
    下载次数
  • 2020-12-12 11:10
    上传日期
信息学奥林匹克竞赛源码包含7个例子,C++平台
code.zip
  • code
  • CXorto.cpp
    524B
  • 【ZJOI2007】报表统计.cpp
    1.3KB
  • A. 哪吒闹海(sea).cpp
    632B
  • B序列.cpp
    1.3KB
  • A游戏.cpp
    616B
  • APYB的CSPer.cpp
    616B
  • BPYB的夜市.cpp
    1.8KB
内容介绍
#include<stdio.h> #include<algorithm rel='nofollow' onclick='return false;'> #define ll long long using namespace std; int n,m,ans,sum,ans2,maxx; int val[220000],rd[220000],valc[220000]; int head[220000],head2[220000],cnt=1,cntb=1; int valmax[220000]; struct note { int to; int nxt; }a[550000],b[550000]; void add(int x,int y) { a[cnt].to=y; a[cnt].nxt=head[x]; head[x]=cnt++; } void add_c(int x,int y) { b[cntb].to=y; b[cntb].nxt=head2[x]; head2[x]=cntb++; rd[y]++; } int dfn[220000],low[220000],js; int stack[330000],top,inx[220000]; int color,c[220000],ins[220000]; void tarjan(int x) { int i,j; dfn[x]=low[x]=++js; stack[++top]=x; ins[x]=1; for(i=head[x];i;i=a[i].nxt) { int to=a[i].to; if(!dfn[to]) { tarjan(to); low[x]=min(low[x],low[to]); } else if(ins[to]) { low[x]=min(low[x],dfn[to]); } } if(dfn[x]==low[x]) { color++;int y; do { y=stack[top--],ins[y]=0; c[y]=color, valc[color]+=val[y]; valmax[color]=max(valmax[color],val[y]); }while(x!=y); } } void dfs(int x) { int i,j; sum+=valc[x]; maxx=max(valmax[x],maxx); for(i=head2[x];i;i=b[i].nxt) { int to=b[i].to; dfs(to); } } int main() { int i,j,u,v; scanf("%d%d",&n,&m); for(i=1;i<=n;i++) { scanf("%d",&val[i]); } for(i=1;i<=m;i++) { scanf("%d%d",&u,&v); add(u,v); } for(i=1;i<=n;i++) { if(!dfn[i]) tarjan(i); } for(i=1;i<=n;i++) { for(j=head[i];j;j=a[j].nxt) { int to=a[j].to; if(c[to]==c[i]) continue; add_c(c[i],c[to]); } } for(i=1;i<=color;i++) { sum=0,maxx=0; if(rd[i]==0) { for(j=head2[i];j;j=b[j].nxt) { sum+=valc[i]; maxx=valmax[i]; dfs(b[j].to); if(sum>ans) { ans=sum; ans2=maxx; } sum=0,maxx=0; } } } printf("%d %d\n",ans,ans2); return 0; }
评论
    相关推荐