隐藏
「JZOJ4686」通讯 - Tarjan缩点+朱刘算法 | Bill Yang's Blog

路终会有尽头,但视野总能看到更远的地方。

0%

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

题目大意

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


题目分析

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

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


代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#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;
}
姥爷们赏瓶冰阔落吧~