求助,不知道哪里错了
查看原帖
求助,不知道哪里错了
223392
Belarus楼主2020/10/15 15:19

rt,fy=fx+szxfi=szi               (x,y)V\mathop{f_y=f_x+sz_x}\limits_{f_i=sz_i\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \exists(x,y)\in V} 中,szxsz_x 代表连通块 xx 中所有点点权之和,但是只有40分,求助:

#include<bits/stdc++.h>
using namespace std;
const int size=1000010;
int ver[size],head[size],nxt[size],dfn[size],low[size];
int stk[size],ins[size],c[size],sz[size],w[size],in[size];
int vc[size],nc[size],hc[size];
int f[size];
int n,m,p,r,tot=1,num,top,cnt,sizemax=0,tc=1,ans=0;
inline void add(int x,int y){
	ver[++tot]=y,nxt[tot]=head[x],head[x]=tot;
}
inline void add_c(int x,int y){
	vc[++tc]=y,nc[tc]=hc[x],hc[x]=tc;
}
void tarjan(int x){
	dfn[x]=low[x]=++num;
	stk[++top]=x;ins[x]=1;
	for(int i=head[x];i;i=nxt[i]){
		int y=ver[i];
		if(!dfn[y]){
			tarjan(y);
			low[x]=min(low[x],low[y]);
		}
		else if(ins[y]) low[x]=min(low[x],dfn[y]);
	}
	if(dfn[x]==low[x]){
		cnt++;int y;
		do{
			y=stk[top--];ins[y]=0;
			c[y]=cnt;
			sz[cnt]+=w[y];
		}while(x!=y);
	}
}
//vector<int> topo_sort;
queue<int> Q;
inline void topo(){
	for(int i=1;i<=cnt;++i) if(!in[i]) Q.push(i);
	while(!Q.empty()){
		int x=Q.front();
		Q.pop();
		//topo_sort.push_back(x);
		for(int i=hc[x];i;i=nc[i]){
			int y=vc[i];
			in[y]--;
			f[y]=max(f[y],f[x]+sz[x]);
			if(!in[y]) Q.push(y);
		}
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin>>n>>m;
	for(int i=1;i<=n;++i) cin>>w[i];
	for(int i=1;i<=m;++i){
		int x,y;
		cin>>x>>y;
		add(x,y);
	}
	for(int i=1;i<=n;++i) if(!dfn[i]) tarjan(i);
	for(int x=1;x<=n;++x) for(int i=head[x];i;i=nxt[i]) if(c[x]!=c[ver[i]]) add_c(c[x],c[ver[i]]),in[c[ver[i]]]++;
	for(int i=1;i<=cnt;++i) f[i]=sz[i];
	topo();
	for(int i=1;i<=cnt;++i) ans=max(ans,f[i]);
	cout<<ans<<endl;
	return 0;
}

给一组错了的数据:

10 20
970 369 910 889 470 106 658 659 916 964 
3 2
3 6
3 4
9 5
8 3
5 8
9 1
9 7
9 8
7 5
3 7
7 8
1 7
10 2
1 10
4 8
2 6
3 1
3 5
8 5
6911
2020/10/15 15:19
加载中...