「JZOJ4686」通讯 - Tarjan缩点+朱刘算法

题目大意

    “这一切都是命运石之门的选择。”
    试图研制时间机器的机关SERN截获了中二科学家伦太郎发往过去的一条短信，并由此得知了伦太郎制作出了电话微波炉（仮）。
    为了掌握时间机器的技术，SERN总部必须尽快将这个消息通过地下秘密通讯网络，传达到所有分部。
    SERN共有$N$个部门（总部编号为$0$），通讯网络有$M$条单向通讯线路，每条线路有一个固定的通讯花费$C_i$。
    为了保密，消息的传递只能按照固定的方式进行：从一个已知消息的部门向另一个与它有线路的部门传递（可能存在多条通信线路）。我们定义总费用为所有部门传递消息的费用和。
    幸运的是，如果两个部门可以直接或间接地相互传递消息（即能按照上述方法将信息由$X$传递到$Y$，同时能由$Y$传递到$X$），我们就可以忽略它们之间的花费。
    由于资金问题（预算都花在粒子对撞机上了），SERN总部的工程师希望知道，达到目标的最小花费是多少。

---

题目分析

因为环中是没有代价的，很显然可以先使用Tarjan算法进行缩点。
缩点后问题变为求有向图MST，因此可以采用朱刘算法。

因为原图中无环，所以只需要进行朱刘算法的第一步：选出除源点的所有点的最小入边。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}
const int maxn=50005;
int n,m,In[maxn],step=0,Dfn[maxn],Lowlink[maxn],Stack[maxn],top=0,Instack[maxn],Belong[maxn],SCC=0;
long long ans=0;
struct Edge {
	int from,to,dist;
};
vector<Edge>edges[maxn];
void Tarjan(int Now) {
	step++;
	Lowlink[Now]=Dfn[Now]=step;
	Stack[++top]=Now;
	Instack[Now]=1;
	for(int i=0; i<edges[Now].size(); i++) {
		Edge& e=edges[Now][i];
		int Next=e.to;
		if(!Dfn[Next]) {
			Tarjan(Next);
			Lowlink[Now]=min(Lowlink[Now],Lowlink[Next]);
		} else if(Instack[Next])Lowlink[Now]=min(Lowlink[Now],Dfn[Next]);
	}
	if(Lowlink[Now]==Dfn[Now]) {
		SCC++;
		int y;
		do {
			y=Stack[top--];
			Belong[y]=SCC;
			Instack[y]=0;
		} while(y!=Now);
	}
}
void AddEdge(int x,int y,int v) {
	edges[x].push_back((Edge) {
		x,y,v
	});
}
void Clear() {
	for(int i=1; i<=n; i++)edges[i].clear(),In[i]=0x7fffffff/2;
	ans=step=top=SCC=0;
	memset(Dfn,0,sizeof(Dfn));
	memset(Lowlink,0,sizeof(Lowlink));
	memset(Stack,0,sizeof(Stack));
	memset(Instack,0,sizeof(Instack));
	memset(Belong,0,sizeof(Belong));
}
int main() {
	while(true) {
		n=Get_Int();
		m=Get_Int();
		if(n+m==0)break;
		Clear();
		for(int i=1; i<=m; i++) {
			int x=Get_Int()+1,y=Get_Int()+1,v=Get_Int();
			AddEdge(x,y,v);
		}
		for(int i=1; i<=n; i++)
			if(!Dfn[i])Tarjan(i);
		for(int Now=1; Now<=n; Now++)
			for(int i=0; i<edges[Now].size(); i++) {
				Edge& e=edges[Now][i];
				int Next=e.to;
				if(Belong[Now]!=Belong[Next])In[Belong[Next]]=min(In[Belong[Next]],e.dist);
			}
		for(int i=1; i<=SCC; i++)
			if(Belong[1]!=i)ans+=In[i];
		printf("%lld\n",ans);
	}
	return 0;
}