题解 U534156 【赛艇表演】

发表于 2020-11-28 更新于 2025-02-11 分类于 OI ，题解阅读次数：本文字数： 1.2k 阅读时长 ≈ 4 分钟

题目链接：赛艇表演。

关于题目：作为 T3，小小的思维题。

应用算法：图论，割点，图的建立，最短路。

\(\qquad\!\!\)这道题的题意还是很明确的，我们直接开始。

\(\qquad\!\!\)首先，第一问是一个裸的模板：P3388 【模板】割点（割顶），它存在的价值也只是为了第二问服务，在这里就不进行讲解了。（如果有不会该模板的请自行学习。）

\(\qquad\!\!\)其次，我们来看第二问。显然，第二问求一个 边权+点权 的最小花费，暴力做肯定超时，我们考虑把权都建在一张固定的图上跑最短路：

一、先不考虑拓荒出的道路：

\(\qquad\!\!\)由于从每个枢纽点出发去看表演都有一定的花费，我们不妨假设存在一个 零号城市，表演只在其中举行，而由每个枢纽点 \(u\) 均向零号城市连接一条边权为 \(c_u\) 的边，即可方便地将 点权转化为边权。此时，只要以 \(s\) 为起点跑单源最短路，\(dis_0\) 即为答案。

二、考虑拓荒出的道路：

\(\qquad\!\!\)由于拓荒出的道路是不固定两个端点的，我们没有办法一边跑最短路一边判断什么时候拓荒，所以只能想办法将其固定下来。

\(\qquad\!\!\)怎么固定呢？一个很自然的想法就是把所有可能的情况都连上吧，即对于一对非起点也非枢纽点的点对 \(u,v\) 均连接上边权为 \(val\) 的双向边。不过这样不仅很容易超出空间限制，而且由于 拓荒能力只能使用一次 而在此时跑最短路可能走过多条新边而不正确。

\(\qquad\!\!\)回想一下解决 不考虑拓荒出的道路 的方法，我们此时可不可以通过多建立一个虚拟节点来实现呢？有了这个思路之后就很简单了，我们建立一个虚拟节点 \(n+1\) 号城市，将每个非起点也非枢纽点的点对它连接一条边权为 \(0\) 的单向边，再从它向每个非起点也非枢纽点的点连接一条边权为 \(val\) 的单向边。这样，不仅连边的数量很少不会超过空间限制，并且由于所有边权为 \(val\) 的边都存在一个公共的节点 \(n+1\)，所以这些边中只能走一条边，也就保证了拓荒能力只能使用一次。

\(\qquad\!\!\)没错，就是这样。一个模板+两个虚拟节点+一些新建边+一个单源最短路。这道题就这样完美地解决了！

\(\qquad\!\!\)最后，上代码。（码风不喜勿喷）：

#include<bits/stdc++.h>
#define in inline
#define re register
#define int long long
const int N=1000010;
const int M=6000010;
using namespace std;
int n,m,s,val; 
int cnt,head[N],c[N];
struct edge
{
    int to,nxt,val;
};
edge e[M];
int dfn[N],low[N],tim;
int f[N],tot,g[N];
int dis[N];
bool vis[N];
int b[N];
struct node
{
	int pos,dis;
	bool operator <(const node &x)const
	{
		return dis>x.dis;
	}
};
priority_queue<node> q;
in int qread()
//快读 
{
    int x=0,y=1;
    int ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
        {
            y=-1;
        }
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*y;
}
in void qwrite(re int x)
//快写 
{
    if(x<0)
    {
        putchar('-');
        qwrite(-x);
    }
    else
    {
        if(x>9)
        {
            qwrite(x/10);
        }
        putchar(x%10+'0');
    }
    return ;
}
in void mr(re int u,re int v,re int w)
//建边 
{
    e[++cnt].to=v;
    e[cnt].nxt=head[u];
    e[cnt].val=w;
    head[u]=cnt;
    return ;
}
in void tarjan(re int u,re int fa)
//tarjan 求割点 
{
	int sum=0;
	low[u]=dfn[u]=++tim;
	for(re int i=head[u];i;i=e[i].nxt)
	{
		int v=e[i].to;
		if(v==fa)
		{
			continue;
		}
		if(!dfn[v])
		{
			sum++;
			tarjan(v,u);
			low[u]=min(low[u],low[v]);
			if(fa&&low[v]>=dfn[u]&&!f[u])
			{
				f[u]=1;
				g[++tot]=u;
			} 
		}
		else
		{
			low[u]=min(low[u],dfn[v]);
		}
	}
	if(!fa&&sum>1&&!f[u])
	{
		f[u]=1;
		g[++tot]=u;
	}
	return ;
}
in void dij()
//dij 求最短路 
{
	memset(dis,0x3f,sizeof(dis));
	dis[s]=0;
	q.push({s,0});
	while(!q.empty())
	{
		int u=q.top().pos;
		q.pop();
		if(vis[u])
		{
			continue;
		}
		vis[u]=1;
		for(re int i=head[u];i;i=e[i].nxt)
		{
			int v=e[i].to;
			if(!vis[v]&&dis[u]+e[i].val<dis[v])
			{
				dis[v]=dis[u]+e[i].val;
				b[v]=u;
				q.push({v,dis[v]});
			}
		}
	}
}
signed main()
{
	n=qread();
	m=qread();
	s=qread();
	val=qread();
	for(re int i=1;i<=m;i++)
	{
		int u=qread();
		int v=qread();
		int w=qread();
		mr(u,v,w);
		mr(v,u,w);
	}
	for(re int i=1;i<=n;i++)
	{
		c[i]=qread();
	}
	//读入 
	for(re int i=1;i<=n;i++)
	{
		if(!dfn[i])
		{
			tarjan(i,0);
		}
	}
	//求割点 
	sort(g+1,g+tot+1);
	for(re int i=1;i<=tot;i++)
	{
		mr(g[i],0,c[g[i]]);
		//对于 0 号节点连边 
		qwrite(g[i]);
		putchar(' ');
	}
	putchar('\n');
	//输出一下 
	for(re int i=1;i<=n;i++)
	{
		if(!f[i]&&i^s)
		{
			mr(n+1,i,val);
			mr(i,n+1,0);
		}
		//对于 n+1 号节点连边 
	}
	dij();
	//最短路 
	qwrite(dis[0]);
	putchar('\n');
	//再输出一下 
    return 0;
}