T3个点求助
查看原帖
T3个点求助
91381
初云悕楼主2020/7/30 15:58
#include <bits/stdc++.h>
#define int long long
#define mp make_pair
#define panhan using
#define no namespace
#define xm std;
panhan no xm;
inline int read(){
	int sum=0,ff=1; char ch=getchar();
	while(!isdigit(ch)){
		if(ch=='-') ff=-1;
		ch=getchar();
	}
	while(isdigit(ch))
		sum=sum*10+(ch^48),ch=getchar();
	return sum*ff;
}
const int N = 1e6+5;
int times , dfn[N] , low[N] , co[N] , hand[N] , cnt , vis[N] , stk[N] , top , f[N] , stf[N] , tot , n , m , ans , cun1[N] , cun2[N] , dis[N];
struct node {int to , next;}a[N<<1];
void add(int x , int y) {a[++cnt]={y,hand[x]},hand[x]=cnt;}
void Tarjan(int now) {
	low[now]=dfn[now]=++times;
	stk[++top] = now , vis[now] = 1;
	for(int i = hand[now] ; i ; i = a[i].next) 
		if(!dfn[a[i].to]) 	Tarjan(a[i].to),low[now]=min(low[now],low[a[i].to]);
		else if(vis[a[i].to])	low[now]=min(low[now],dfn[a[i].to]);
	if(low[now]==dfn[now]) {
		tot++;
		while(1) {
			co[stk[top]]=tot;
			f[tot]+=stf[stk[top]];
			vis[stk[top]]=0;
			if(stk[top--] == now) break;
		}
	}
}
void doit(int now) {
	for(int i = hand[now] ; i ; i = a[i].next) {
		dis[a[i].to] = max(dis[a[i].to],dis[now]+f[a[i].to]);
		doit(a[i].to);
	}
}
main() {
	n = read() , m = read();
	for(int i = 1 ; i <= m ; i ++) cun1[i] = read() , cun2[i] = read() , add(cun1[i],cun2[i]);
	for(int i = 1 ; i <= n ; i ++) stf[i] = read();
	for(int i = 1 ; i <= n ; i ++) if(!dfn[i]) Tarjan(i);
	memset(hand,0,sizeof(hand));
	cnt=0;
	for(int i = 1 ; i <= m ; i ++) if(co[cun1[i]]!=co[cun2[i]]) add(co[cun1[i]],co[cun2[i]]);
	int st = read();dis[co[st]]=f[co[st]],doit(co[st]);
	int p = read();
	for(int i = 1 ; i <= p ; i ++) ans = max(ans,dis[co[read()]]);
	cout << ans;
}

完全不知道错在哪里了,T了2,3,10,32 ,3, 10, 3个点 求大佬查错...

2020/7/30 15:58
加载中...