【強聯通】魔法石

任意門

題目：

幻象群島是由n個孤立的島嶼構成。島嶼之間有一些殘破的石橋，而橋心的石墩上，就有可能鑲嵌着上古魔法石。約翰尼可以通過這些石橋，從一座島跑到另一座島，如果島上恰好有魔法石，他就可以順便收集。但是由于這些石橋實在是太殘破了，約翰尼經過之後，石橋就會崩塌，不能再次通過。（由于約翰尼踩過的部分很快就會崩塌，是以他也不能先跑到橋心，然後原路傳回）。

約翰尼現在處在島a，而島b上則有一個傳送門，隻有在那裡，約翰尼才能安全地離開幻象群島。約翰尼想知道，他能順利地收集到至少一塊上古魔法石，并安全離開嗎？

題解：

縮點+dp

dp 點權+邊權

注意：起點的點權

#include<bits/stdc++.h>
#define BU printf("BUG")
using namespace std;
const int N=3e6+10,M=3e6+10;
int S,T;
int n,m;
int head[N],nex[M*2],to[M*2],val[M*2],tot;
void build(int u,int v,int w){tot++;nex[tot]=head[u];to[tot]=v;val[tot]=w;head[u]=tot;}
void init()
{
	memset(head,0,sizeof(head));
	memset(nex,0,sizeof(nex));
	memset(to,0,sizeof(to));
	memset(val,0,sizeof(val));tot=0;
}
int z[N],p;
int dfn[N],low[N],cnt;
int col[N],color;
void tarjan(int u,int f)
{
	dfn[u]=low[u]=++cnt;
	z[++p]=u;
	for(int i=head[u];i;i=nex[i])
	{
		int v=to[i];
		if(v==f)continue;
		if(!dfn[v])
		{
			tarjan(v,u);
			low[u]=min(low[u],low[v]);
		}
		else if(!col[v])
		low[u]=min(low[u],dfn[v]);
	}
	if(low[u]==dfn[u])
	{
		color++;
		int now=z[p--];col[now]=color;
		while(now!=u)now=z[p--],col[now]=color;
	}
}
int dp[N];
int num[N];
void dfs(int u,int f)
{
	for(int i=head[u];i;i=nex[i])
	{
		int v=to[i];
		if(v==f)continue;
		if(dp[v]<dp[u]+val[i]+num[v])dp[v]=dp[u]+val[i]+num[v];
		dfs(v,u);
	}
}
int u[M],v[M],w[M];
int main()
{
	int TT;
	scanf("%d",&TT);
	while(TT--)
	{
		scanf("%d%d",&n,&m);
		init();
		for(int i=1;i<=m;i++)
		{
			scanf("%d%d%d",&u[i],&v[i],&w[i]);
			build(u[i],v[i],w[i]);
			build(v[i],u[i],w[i]);
		}
		for(int i=1;i<=n;i++)
		if(!dfn[i])tarjan(i,0);
		init();
		for(int i=1;i<=m;i++)
		{
			int x=col[u[i]],y=col[v[i]];
			if(x!=y)build(x,y,w[i]),build(y,x,w[i]);
			else	num[x]+=w[i];
		}
		/*printf("\n-----------\n");
		for(int i=1;i<=n;i++)
		printf("%d(%d) ",col[i],i);
		printf("\n");
		for(int i=1;i<=color;i++)printf("%d(%d) ",num[i],i);
		printf("\n");*/
		scanf("%d%d",&S,&T);
		S=col[S],T=col[T];
		dp[S]=num[S];
		dfs(S,0);
		if(dp[T]>=1||(S==T&&num[S]>=1))printf("YES\n");
		else 		printf("NO\n");
		for(int i=1;i<=n;i++)
		col[i]=low[i]=dfn[i]=dp[i]=num[i]=0;
		color=0;cnt=0;
	}
}