网站怎么做引流呢,如何把建设银行网站下载到桌面,wordpress 无法翻页,那个网站的系统好给出一个带权有向图#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
