自己做商城网站,做分析仪器推广的网站,网站开发字体的引用,seo技术经理给出一个带权有向图#xff0c;要使整个图连通。SCC中的点之间花费为0#xff0c;所以就先缩点#xff0c;然后缩点后两点之间的权值为最小边的权值#xff0c;把这些权值累加起来就是答案。 1 #include iostream2 #include cstdio3 #include algorith…给出一个带权有向图要使整个图连通。SCC中的点之间花费为0所以就先缩点然后缩点后两点之间的权值为最小边的权值把这些权值累加起来就是答案。 1 #include iostream2 #include cstdio3 #include algorithm4 #include cstring5 #include vector6 #include stack7 using namespace std;8 9 int n, m;
10
11 const int maxn 50000 10;
12
13 vectorint G[maxn], C[maxn];
14
15 stackint S;
16 int pre[maxn], lowlink[maxn], sccno[maxn];
17 int dfs_clock, scc_cnt;
18
19 void dfs(int u)
20 {
21 pre[u] lowlink[u] dfs_clock;
22 S.push(u);
23 for(int i 0; i G[u].size(); i)
24 {
25 int v G[u][i];
26 if(!pre[v])
27 {
28 dfs(v);
29 lowlink[u] min(lowlink[u], lowlink[v]);
30 }
31 else if(!sccno[v]) lowlink[u] min(lowlink[u], pre[v]);
32 }
33
34 if(lowlink[u] pre[u])
35 {
36 scc_cnt;
37 for(;;)
38 {
39 int x S.top(); S.pop();
40 sccno[x] scc_cnt;
41 if(x u) break;
42 }
43 }
44 }
45
46 void find_scc()
47 {
48 dfs_clock scc_cnt 0;
49 memset(pre, 0, sizeof(pre));
50 memset(sccno, 0, sizeof(sccno));
51 for(int i 0; i n; i) if(!pre[i]) dfs(i);
52 }
53
54 int cost[maxn];
55
56 int main()
57 {
58 while(scanf(%d%d, n, m) 2)
59 {
60 for(int i 0; i n; i) { G[i].clear(); C[i].clear(); }
61 while(m--)
62 {
63 int u, v, d; scanf(%d%d%d, u, v, d);
64 G[u].push_back(v); C[u].push_back(d);
65 }
66 find_scc();
67
68 memset(cost, -1, sizeof(cost));
69 for(int i 0; i n; i)
70 for(int j 0; j G[i].size(); j)
71 {
72 int u sccno[i], v sccno[G[i][j]];
73 if(u v) continue;
74 if(cost[v] -1) cost[v] C[i][j];
75 else cost[v] min(cost[v], C[i][j]);
76 }
77
78 int ans 0;
79 for(int i 1; i scc_cnt; i) if(cost[i] ! -1) ans cost[i];
80 printf(%d\n, ans);
81 }
82
83 return 0;
84 } 代码君 转载于:https://www.cnblogs.com/AOQNRMGYXLMV/p/4718315.html
