B. 通訊
題目類型：傳統 評測方式：文本比較
記憶體限制：256 MiB 時間限制：1000 ms 标準輸入輸出
題目描述
“這一切都是命運石之門的選擇。”
試圖研制時間機器的機關SERN截獲了中二科學家倫太郎發往過去的一條短 信，并由此得知了倫太郎制作出了電話微波爐（仮）。
為了掌握時間機器的技術，SERN總部必須盡快将這個消息通過地下秘密通訊 網絡，傳達到所有分部。
SERN共有N個部門（總部編号為0），通訊網絡有M條單向通訊線路，每條線 路有一個固定的通訊花費Ci。
為了保密，消息的傳遞隻能按照固定的方式進行：從一個已知消息的部門向 另一個與它有線路的部門傳遞（可能存在多條通信線路）。我們定義總費用為所 有部門傳遞消息的費用和。
幸運的是，如果兩個部門可以直接或間接地互相傳遞消息（即能按照上述方 法将資訊由X傳遞到Y，同時能由Y傳遞到X），我們就可以忽略它們之間的花費。
由于資金問題（預算都花在粒子對撞機上了），SERN總部的工程師希望知道， 達到目标的最小花費是多少。
輸入格式
多組資料，檔案以2個0結尾。
每組資料第一行，一個整數N，表示有N個包括總部的部門（從0開始編号）。 然後是一個整數M，表示有M條單向通訊線路。
接下來M行，每行三個整數,Xi,Yi,Ci，表示第i條線路從Xi連向Yi，花費為 Ci。
輸出格式
每組資料一行，一個整數表示達到目标的最小花費。
樣例
樣例輸入
3 3
0 1 100
1 2 50
0 2 100
3 3
0 1 100
1 2 50
2 1 100
2 2
0 1 50
0 1 100
0 0 樣例輸出
150
100
50 資料範圍與提示
樣例解釋
第一組資料：總部把消息傳給分部1，分部1再傳給分部2.總費用：100+50=150.
第二組資料：總部把消息傳給分部1，由于分部1和分部2可以互相傳遞消息，是以分部1可以無費用把消息傳給2.總費用：100+0=100.
第三組資料：總部把消息傳給分部1，最小費用為50.總費用：50.
資料範圍
對于10%的資料，保證M=N-1
對于另30%的資料，N ≤ 20 ，M ≤ 20
對于100%的資料，N ≤ 50000 ，M ≤ 10^5 ，Ci ≤ 10^5 ，
資料組數 ≤ 5
資料保證一定可以将資訊傳遞到所有部門。
水題
tarjan縮點，貪心找每個點的最小入邊即可（我用dfs實作，本質都是貪心）
1 #include<iostream>
2 #include<cstdio>
3 #include<vector>
4 using namespace std;
5 int n,m,dfn[51000],low[51000],num,st[51000],sp[51000],ins[51000],mi[51000],v[51000],cnt;
6 struct node{
7 int ver,len;
8 };
9 vector<node>to[51000],son[51000];
10 void tarjan(int x){
11 dfn[x]=low[x]=++num;
12 st[++st[0]]=x;
13 ins[x]=1;
14 //sort(to[x].begin(),to[x].end(),cmp);
15 for(int i=0;i<to[x].size();i++){
16 node w=to[x][i];
17 if(!dfn[w.ver]){
18 tarjan(w.ver);
19 low[x]=min(low[x],low[w.ver]);
20 }
21 else if(ins[w.ver]) low[x]=min(low[x],dfn[w.ver]);
22 }
23 if(low[x]==dfn[x]){
24 cnt++;
25 int y;
26 do{
27 y=st[st[0]--];
28 ins[y]=0;
29 sp[y]=cnt;
30 }while(y!=x);
31
32 }
33 }
34 long long dfs(int x){
35 v[x]=1;
36 long long cet=0;
37 //sort(son[x].begin(),son[x].end(),cmp);
38 // cout<<x<<" "<<son[x].size()<<endl;
39 for(int i=0;i<son[x].size();i++){
40 node w=son[x][i];
41 //cout<<w.ver<<" "<<w.len<<endl;
42 if(v[w.ver]){
43 if(mi[w.ver]>w.len){
44 cet-=(mi[w.ver]-w.len);
45 mi[w.ver]=w.len;
46 }
47 continue;
48 }
49 cet+=dfs(w.ver);
50 cet+=w.len;
51
52 mi[w.ver]=w.len;
53 }
54 ///cout<<cet<<endl;
55 return cet;
56
57 }
58 int main(){
59 scanf("%d%d",&n,&m);
60 while(n!=0||m!=0){
61 int x;
62 for(int i=1;i<=m;i++){
63 node w;
64 scanf("%d%d%d",&x,&w.ver,&w.len);
65 w.ver++;
66 to[x+1].push_back(w);
67 }
68 // for(int i=1;i<=n;i++) cout<<i<<" "<<to[i].size()<<endl;
69 for(int i=1;i<=n;i++)
70 if(!dfn[i]) tarjan(i);
71 //for(int i=1;i<=n;i++) cout<<i<<" "<<to[i].size()<<endl;
72 for(int i=1;i<=n;i++){
73 //cout<<i<<" "<<sp[i]<<" "<<to[i].size()<<endl;
74 for(int j=0;j<to[i].size();j++){
75 node w=to[i][j];
76 if(sp[i]!=sp[w.ver]){
77 w.ver=sp[w.ver];
78 son[sp[i]].push_back(w);
79 }
80 }
81 }
82 /*for(int i=1;i<=cnt;i++){
83 cout<<i<<" "<<son[i].size()<<endl;
84 for(int j=0;j<son[i].size();j++){
85 printf("%d %d %d\n",i,son[i][j].ver,son[i][j].len);
86 }
87 }*/
88 long long ans=dfs(sp[1]);
89 printf("%lld\n",ans);
90 for(int i=1;i<=n;i++){
91 dfn[i]=low[i]=v[i]=sp[i]=mi[i]=v[i]=0;
92 to[i].clear();
93 son[i].clear();
94 num=0;
95 cnt=0;
96 }
97 scanf("%d%d",&n,&m);
98 }
99
100 } 我的tarjan+dfs代碼
天皇skyh的貪心找小邊
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #define db(x) cerr<<#x<<"="<<x<<endl
5 #define cl(x) memset(x,0,sizeof(x))
6 using namespace std;
7 const int N=50100,M=501000;
8 int n,m,scc;
9 int tot,head[N],to[M],nxt[M],w[M];
10 int top,stack[N],dfn[N],low[N],num,bl[N];
11 bool instack[N];
12 int imin[N];
13 void tarjan(int x)
14 {
15 dfn[x]=low[x]=++num;
16 stack[++top]=x; instack[x]=1;
17 for(int i=head[x];i;i=nxt[i])
18 {
19 int y=to[i];
20 if(!dfn[y])
21 {
22 tarjan(y);
23 low[x]=min(low[x],low[y]);
24 }
25 else if(instack[y]) low[x]=min(low[x],dfn[y]);
26 }
27 if(dfn[x]==low[x])
28 {
29 ++scc; int y;
30 do{
31 y=stack[top--];
32 bl[y]=scc;
33 instack[y]=0;
34 }while(y!=x);
35 }
36 }
37 int main()
38 {
39 while(scanf("%d%d",&n,&m)==2&&(n||m))
40 {
41 cl(dfn); cl(head);
42 memset(imin,0x3f,sizeof(imin));
43 tot=0; top=0; num=0; scc=0;
44 for(int i=1,a,b,d;i<=m;i++)
45 {
46 scanf("%d%d%d",&a,&b,&d);
47 a++; b++;
48 to[++tot]=b; w[tot]=d;
49 nxt[tot]=head[a]; head[a]=tot;
50 }
51 tarjan(1);
52 //db(scc);
53 for(int i=1;i<=n;i++)
54 for(int j=head[i];j;j=nxt[j])
55 {
56 int y=to[j];
57 if(bl[i]==bl[y]) continue;
58 imin[bl[y]]=min(imin[bl[y]],w[j]);
59 }
60 long long ans=0;
61 for(int i=1;i<=scc;i++)
62 if(imin[i]<=10000000)
63 ans+=imin[i];
64 printf("%lld\n",ans);
65 }
66 return 0;
67 }