题目

“这一切都是命运石之门的选择。”

试图研制时间机器的机关SERN截获了中二科学家伦太郎发往过去的一条短信，并由此得知了伦太郎制作出了电话微波炉（仮）。

为了掌握时间机器的技术，SERN总部必须尽快将这个消息通过地下秘密通讯网络，传达到所有分部。

SERN共有N个部门（总部编号为0），通讯网络有M条单向通讯线路，每条线路有一个固定的通讯花费Ci。

为了保密，消息的传递只能按照固定的方式进行：从一个已知消息的部门向另一个与它有线路的部门传递（可能存在多条通信线路）。我们定义总费用为所有部门传递消息的费用和。

幸运的是，如果两个部门可以直接或间接地相互传递消息（即能按照上述方法将信息由X传递到Y，同时能由Y传递到X），我们就可以忽略它们之间的花费。

由于资金问题（预算都花在粒子对撞机上了），SERN总部的工程师希望知道，达到目标的最小花费是多少。

分析

首先处理忽略划分的情况，如果两个部门可以直接或间接地相互传递消息，那么他们一定在同一个强连通分量之中。就用tarjan缩点。

所点后就变成了个有向无环图，

很容易想到，最小花费的方案数选的路线，一定只有n-1条，也就是说每个强连通分量块的入边只有一个（除了0所在的强连通分量块）。

那么就每个强连通分量块（除了0所在的强连通分量块）选一个最小的入边计入答案。

#include <cmath>

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

#include <queue>

const int maxlongint=2147483647;

const int mo=1000000007;

const int N=50005;

using namespace std;

int next[N*4],last[N*4],to[N*4],v[N*4];

int next1[N*4],last1[N*4],to1[N*4],v1[N*4];

int n,m,tot,dd,d[N],dfn[N],low[N],ddd,part[N],num,ans[N],sum;

bool bz[N];

int bj(int i,int x,int y,int z)

{

	next1[i]=last1[x];

	last1[x]=i;

	to1[i]=y;

	v1[i]=z;

}

int tarjan(int x)

{

	dfn[x]=low[x]=++dd;

	d[++tot]=x;

	bz[x]=false;

	for(int i=last1[x];i;i=next1[i])

	{

		int j=to1[i];

		if(bz[j])

		{

			tarjan(j);

			low[x]=min(low[x],low[j]);

		}

		else

		if(!part[j])

			low[x]=min(low[x],low[j]);

	}

	if(dfn[x]==low[x])

	{

		num++;

		ans[num]=maxlongint;

		while(dfn[d[tot]]>=dfn[x])

		{

			part[d[tot--]]=num;

		}

	}

}

int bj1(int x,int y,int z)

{

	next[++tot]=last[x];

	last[x]=tot;

	to[tot]=y;

	v[tot]=z;

}

int main()

{

	while(1)

	{

		memset(last,0,sizeof(last));

		memset(last1,0,sizeof(last1));

		memset(part,0,sizeof(part));

		scanf("%d%d",&n,&m);

		if(!n && !m) return 0;

		memset(bz,true,sizeof(bz));

		for(int i=1;i<=m;i++)

		{

			int x,y,z;

			scanf("%d%d%d",&x,&y,&z);

			bj(i,x,y,z);

		}

		dd=tot=0;

		num=0;

		tarjan(0);

		tot=0;

		sum=0;

		for(int i=0;i<=n-1;i++)

		{

			for(int j=last1[i];j;j=next1[j])

			{

				int k=to1[j];

				bj1(part[i],part[k],v1[j]);

				if(part[i]!=part[k])

					ans[part[k]]=min(ans[part[k]],v1[j]);

			}

		}

		for(int i=1;i<=num-1;i++)

			sum+=ans[i];

		printf("%d\n",sum);

	}

}

巴特西

【NOIP2016提高A组8.12】通讯

题目

分析

最新文章

热门文章