个人做加盟商机网站如何盈利,个人介绍网页设计报告,国内视频网站域名,公司注册类型题意#xff1a;给一个有向图#xff0c;问要从0号点能到达所有点所需要经过路径的最小权值和是多少#xff0c;然而#xff0c;若两点强联通#xff0c;则这两点互相到达不需要花费。保证0号点能到达所有点 tarjan缩点以后直接取每个点入边中花费最小的即可。 1 #include… 题意给一个有向图问要从0号点能到达所有点所需要经过路径的最小权值和是多少然而若两点强联通则这两点互相到达不需要花费。保证0号点能到达所有点 tarjan缩点以后直接取每个点入边中花费最小的即可。 1 #includecstdio2 #includecstring3 #includealgorithm4 #includevector5 #includequeue6 #includecmath7 #includectime8 #define LL long long int9 using namespace std;
10 const int maxn50050,maxm100010;
11
12 LL rd(){
13 LL x0;char cgetchar();int neg1;
14 while(c0||c9){if(c-) neg-1;cgetchar();}
15 while(c0c9) xx*10c-0,cgetchar();
16 return x*neg;
17 }
18
19 struct Edge{
20 int a,b,l,ne;
21 }eg[maxm];
22 int egh[maxn],ect;
23 int N,M;
24 int dfn[maxn],low[maxn],bel[maxn],stk[maxn],tot,pct,sct;
25 bool instk[maxn];
26 int mi[maxn];
27
28 inline void adeg(int a,int b,int l){
29 eg[ect].aa;eg[ect].bb;eg[ect].ll;eg[ect].neegh[a];egh[a]ect;
30 }
31
32 void tarjan(int x){
33 dfn[x]low[x]tot;
34 stk[sct]x;instk[x]1;
35 for(int iegh[x];i!-1;ieg[i].ne){
36 int jeg[i].b;
37 if(instk[j]) low[x]min(low[x],dfn[j]);
38 else if(!dfn[j]){
39 tarjan(j);low[x]min(low[x],low[j]);
40 }
41 }
42 if(low[x]dfn[x]){
43 pct;
44 while(sct){
45 instk[stk[sct]]0;
46 bel[stk[sct]]pct;
47 if(stk[sct--]x) break;
48 }
49 }
50 }
51
52 int main(){
53 int i,j,k;
54 while(~scanf(%d%d,N,M)){
55 memset(egh,-1,sizeof(egh));
56 memset(dfn,0,sizeof(dfn));
57 memset(instk,0,sizeof(instk));
58 ecttotpctsct0;
59 for(i1;iM;i){
60 int ard(),brd(),crd();
61 adeg(a,b,c);
62 }
63
64 for(i0;iN;i) if(!dfn[i]) tarjan(i);
65 memset(mi,127,sizeof(mi));
66 for(i0;iect;i){
67 if(bel[eg[i].a]bel[eg[i].b]) continue;
68 mi[bel[eg[i].b]]min(mi[bel[eg[i].b]],eg[i].l);
69 }int ans0;
70 for(i1;ipct;i){
71 if(i!bel[0]) ansmi[i];
72 }printf(%d\n,ans);
73 }
74 } 转载于:https://www.cnblogs.com/Ressed/p/9409493.html
