1 BZOJ1592  2   3 #include<iostream>  4 #include<algorithm>  5 #include<cstring>  6 #include<cstdio>  7 #include<cmath>  8 #define N 3005  9 #define inf 0x7fffffff 10 using namespace std; 11 int n,m,ans,a[N],c[N],f[N][N]; 12 int read() 13 { 14   int x=0,f=1; char ch; 15   while (ch=getchar(),ch<‘0‘||ch>‘9‘) if (ch==‘-‘) f=-1; 16   while (x=x*10+ch-‘0‘,ch=getchar(),ch>=‘0‘ && ch<=‘9‘); 17   return x*f; 18 } 19 void solve() 20 { 21   sort(c+1,c+n+1); 22   m=unique(c+1,c+n+1)-(c+1); 23   for (int i=1; i<=n; i++) f[i][0]=inf/2; 24   for (int i=1; i<=n; i++) 25     { 26       for (int j=1; j<=m; j++) 27     { 28       f[i][j]=min(f[i-1][j]+abs(a[i]-c[j]),f[i][j-1]); 29     } 30     } 31   ans=f[n][m]; 32   for (int i=1; i<=n; i++) f[i][m+1]=inf/2; 33   for (int i=1; i<=n; i++) 34     { 35       for (int j=m; j>=1; j--) 36     { 37       f[i][j]=min(f[i-1][j]+abs(a[i]-c[j]),f[i][j+1]); 38     } 39     } 40   ans=min(ans,f[n][1]); 41 } 42 int main() 43 { 44   n=read(); 45   for (int i=1; i<=n; i++)  c[i]=a[i]=read(); 46   solve(); 47   printf("%d\n",ans); 48   return 0; 49 } 50  51 BZOJ1051 52  53 #include<iostream> 54 #include<cstring> 55 #include<algorithm> 56 #include<cmath> 57 #include<cstdio> 58 #define ll long long 59 #define N 10005 60 #define M 50005 61 using namespace std; 62 int n,m,ans,u[M],V[M]; 63 int now[N],pre[M],v[M],tot; 64 int ind,top,total,z[N],dfn[N],low[N],num[N],in[N],out[N],belong[N]; 65 bool vis[N],inq[N]; 66 int read() 67 { 68     int x=0,f=1; char ch; 69     while (ch=getchar(),ch<‘0‘||ch>‘9‘) if (ch==‘-‘) f=-1; 70     while (x=x*10+ch-‘0‘,ch=getchar(),ch>=‘0‘&&ch<=‘9‘); 71     return x*f; 72 } 73 void ins(int a,int b){ 74     ++tot; pre[tot]=now[a]; now[a]=tot; v[tot]=b; 75 } 76 void dfs(int x) 77 { 78      79     dfn[x]=low[x]=++ind; 80     vis[x]=inq[x]=1; z[++top]=x; 81     for (int p=now[x]; p; p=pre[p]) 82     { 83         int son=v[p]; 84         if (!dfn[son]) {dfs(son); low[x]=min(low[x],low[son]);} 85         else if (inq[son]) low[x]=min(low[x],dfn[son]); 86     } 87     if (low[x]==dfn[x]) 88     { 89         ++total; 90         belong[x]=total; inq[x]=0; num[total]=1; 91         while (z[top]!=x) 92         { 93             int son=z[top]; 94             belong[son]=total; inq[son]=0; num[total]++; 95             top--; 96         } 97         top--; 98     } 99 }100 int main()101 {102     n=read(); m=read();103     for (int i=1; i<=m; i++)104     {105         int x=read(),y=read();106         u[i]=x; V[i]=y;107         ins(x,y); 108     }109     for (int i=1; i<=n; i++) if (!dfn[i]) dfs(i);110     for (int i=1; i<=m; i++) if (belong[u[i]]!=belong[V[i]])111     {112     //    cout<<" "<<belong[u[i]]<<" "<<belong[V[i]]<<endl;113         ++out[belong[u[i]]]; ++in[belong[V[i]]];114     }115 //    for (int i=1; i<=total; i++) cout<<num[i]<<endl;116     int sum=0;117     for (int i=1; i<=total; i++)118     {119         if (!out[i]) {ans=num[i]; sum++; if (sum>=2) break;}120     }121 //    cout<<ans<<endl;122     if (sum>1) ans=0; printf("%d\n",ans);123     return 0;124 }125 126 BZOJ 2442127 128 #include<iostream>129 #include<cstring>130 #include<algorithm>131 #include<cmath>132 #include<cstdio>133 #define ll long long134 #define N 100005135 using namespace std;136 int n,k,head,tail;137 ll ans,sum,f[N];138 int a[N],pos[N];139 int read()140 {141     int x=0,f=1; char ch;142     while (ch=getchar(),ch<‘0‘||ch>‘9‘) if (ch==‘-‘) f=-1;143     while (x=x*10+ch-‘0‘,ch=getchar(),ch>=‘0‘&&ch<=‘9‘);144     return x*f;145 }146 int main()147 {148     n=read(); k=read(); 149     for (int i=1; i<=n; i++) a[i]=read(),sum+=a[i];150     for (int i=1; i<=n; i++)151     {152         while (head<=tail && pos[head]<i-k-1) head++;153         f[i]=f[pos[head]]+a[i];154         while (head<=tail && f[pos[tail]]>=f[i]) tail--;155         ++tail; pos[tail]=i; 156     }157     ans=100000000000000;158     for (int i=n-k; i<=n; i++) ans=min(ans,f[i]);159     printf("%lld\n",sum-ans);160     return 0;161 }162 163 BZOJ3890164 165 #include<iostream>166 #include<cstring>167 #include<algorithm>168 #include<cmath>169 #include<cstdio>170 #define N 105171 #define M (N*(N+1))172 #define ll long long173 using namespace std;174 int pre[M],v[M],val1[M],val2[M],now[N],n,m,tot;175 bool f[N][M],g[N][M];176 int read()177 {178     int x=0,f=1; char ch;179     while (ch=getchar(),ch<‘0‘||ch>‘9‘) if (ch==‘-‘) f=-1;180     while (x=x*10+ch-‘0‘,ch=getchar(),ch>=‘0‘&&ch<=‘9‘);181     return x*f;182 }183 void ins(int a,int b,int c,int d)184 {185     ++tot; pre[tot]=now[a]; now[a]=tot; v[tot]=b; val1[tot]=c; val2[tot]=d; 186 }187 int main()188 {189     n=read(); m=read();190     for (int i=1; i<=m; i++)191     {192         int u=read(),v=read(),a=read(),b=read();193         ins(u,v,a,b);194     }195     f[1][0]=g[1][0]=1;196     for (int i=1; i<=n-1; i++)197     {198         for (int p=now[i]; p; p=pre[p])199         {200             int son=v[p];201             for (int j=val1[p]; j<=10000; j++) f[son][j]|=f[i][j-val1[p]];202             for (int j=val2[p]; j<=10000; j++) g[son][j]|=g[i][j-val2[p]];203         }204     }205     bool bo=false;206     for (int i=0; i<=10000; i++)207     if (g[n][i] && f[n][i])208     {209         bo=true;210         printf("%d\n",i);211         break;212     }213     if (!bo) printf("IMPOSSIBLE\n"); 214     return 0;215  } 216 217 BZOJ4390218 219 #include<iostream>220 #include<cstring>221 #include<algorithm>222 #include<cmath>223 #include<cstdio>224 #define N 60005225 #define M N*2226 #define ll long long227 using namespace std;228 int pre[M],v[M],now[N],tot,n,k,ans;229 int f[N][25],bin[25],deep[N],val[N];230 int read()231 {232     int x=0,f=1; char ch;233     while (ch=getchar(),ch<‘0‘||ch>‘9‘) if (ch==‘-‘) f=-1;234     while (x=x*10+ch-‘0‘,ch=getchar(),ch>=‘0‘&&ch<=‘9‘);235     return x*f;236 }237 void ins(int a,int b){++tot; pre[tot]=now[a]; now[a]=tot; v[tot]=b; 238 }239 void dfs(int x)240 {241      for (int i=1; i<=19 && bin[i]<=deep[x]; i++) f[x][i]=f[f[x][i-1]][i-1];242      for (int p=now[x]; p; p=pre[p])243      {244          int son=v[p]; if (son==f[x][0]) continue;245          deep[son]=deep[x]+1; f[son][0]=x;246          dfs(son);247      }248 }249 int lca(int x,int y)250 {251     if (deep[x]<deep[y]) swap(x,y);252     int t=deep[x]-deep[y];253     for (int i=0; bin[i]<=t; i++)254     {255         if (t&bin[i]) x=f[x][i];256     }257     for (int i=19; i>=0; i--) if (f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];258     if (x==y) return x;259     return f[x][0];260 }261 void dfs2(int x,int fa)262 {263     for (int p=now[x]; p; p=pre[p])264     {265         int son=v[p]; if (son==fa) continue;266         dfs2(son,x); val[x]+=val[son];267     }268     ans=max(ans,val[x]);269 }270 int main()271 {272     n=read(); k=read();273     for (int i=1; i<n; i++)274     {275         int x=read(),y=read();276         ins(x,y); ins(y,x);277     }278     bin[0]=1; for (int i=1; i<=20; i++) bin[i]=bin[i-1]*2;279     deep[1]=1; dfs(1);280     for (int i=1; i<=k; i++)281     {282         int x=read(),y=read();283         int t=lca(x,y);284         val[x]++; val[y]++; val[t]--; val[f[t][0]]--;285     }286     dfs2(1,0);287     printf("%d\n",ans);288     return 0;289 }290 291 292 BZOJ4525293 294 #include<iostream>295 #include<cstring>296 #include<algorithm>297 #include<cmath>298 #include<cstdio>299 #define ll long long300 #define inf 0x7ffffff301 using namespace std;302 int n,k,ans;303 int a[50005];304 int read()305 {306     int x=0,f=1; char ch;307     while (ch=getchar(),ch<‘0‘||ch>‘9‘) if (ch==‘-‘) f=-1;308     while (x=x*10+ch-‘0‘,ch=getchar(),ch>=‘0‘&&ch<=‘9‘);309     return x*f;310 }311 bool pd(int mid)312 {313     int l=0;314     for (int i=1; i<=k; i++)315     {316         int pos=a[l+1];317         while (l+1<=n && ((a[l+1]-pos)<=2*mid)) l++;318     }319     if (l>=n) return true;320     return false;321 }322 int main()323 {324     n=read(); k=read();325     for (int i=1; i<=n; i++) a[i]=read();326     sort(a+1,a+n+1);327     int l=0,r=inf-2;328     while (l<=r)329     {330         int mid=(l+r)>>1;331         if (pd(mid)) ans=mid,r=mid-1; else l=mid+1;332     }333     printf("%d\n",ans);334     return 0;335 }336 337 BZOJ4511338 339 340 #include<iostream>341 #include<cstring>342 #include<algorithm>343 #include<cmath>344 #include<cstdio>345 #define ll long long346 #define N 50005347 using namespace std;348 int ans,n,a[N],f[N][8];349 int read()350 {351     int x=0,f=1; char ch;352     while (ch=getchar(),ch<‘0‘||ch>‘9‘) if (ch==‘-‘) f=-1;353     while (x=x*10+ch-‘0‘,ch=getchar(),ch>=‘0‘&&ch<=‘9‘);354     return x*f;355 }356 int main()357 {358     n=read();359     for (int i=1; i<=n; i++) a[i]=read()%7;360     memset(f,-1,sizeof(f));361     f[0][0]=0; for (int i=1; i<=n; i++) f[i][a[i]]=1;362     for (int i=1; i<=n; i++)363         for (int j=0; j<=6; j++)364         if (f[i-1][j]!=-1) f[i][(j+a[i])%7]=max(f[i][(j+a[i])%7],f[i-1][j]+1);365     for (int i=1; i<=n; i++) ans=max(ans,f[i][0]);366     printf("%d\n",ans);367     return 0;368 }

  1 BZOJ1711  2   3 #include<iostream>  4 #include<cstring>  5 #include<algorithm>  6 #include<cmath>  7 #include<cstdio>  8 #include<queue>  9 #define inf 0x7fffffff 10 #define ll long long 11 #define N 505 12 #define M 50005 13 using namespace std; 14 int n,F,D,head,tail,list[N<<2],tot=1,S,T,ans=0; 15 int pre[M],v[M],cap[M],now[N],deep[N]; 16 queue<int>q; 17 int read() 18 { 19     int x=0,f=1; char ch; 20     while (ch=getchar(),ch<‘0‘||ch>‘9‘) if (ch==‘-‘) f=-1; 21     while (x=x*10+ch-‘0‘,ch=getchar(),ch>=‘0‘&&ch<=‘9‘); 22     return x*f; 23 } 24 void ins(int a,int b,int c){ 25     ++tot; pre[tot]=now[a]; now[a]=tot; v[tot]=b; cap[tot]=c; 26     ++tot; pre[tot]=now[b]; now[b]=tot; v[tot]=a; cap[tot]=0; 27 } 28 void init_build() 29 { 30     n=read(); F=read(); D=read(); 31     S=0; T=n*2+F+D+1; 32     for (int i=1; i<=F; i++) ins(S,i,1); 33     for (int i=F+n*2+1; i<=F+n*2+D; i++) ins(i,T,1); 34     for (int i=1; i<=n; i++) 35     { 36         int A=read(),B=read(); 37         for (int j=1; j<=A; j++) {int x=read(); ins(x,F+i,1);} 38         for (int j=1; j<=B; j++) {int x=read(); ins(F+n+i,F+n*2+x,1);} 39     } 40     for (int i=1;i<=n;i++) ins(F+i,F+i+n,1); 41 } 42 bool bfs() 43 { 44     for (int i=S;i<=T;i++) deep[i]=-1;  45     deep[S]=0; head=0,tail=1,list[1]=S; 46     while (head<tail) 47     { 48         int x=list[++head]; 49         for (int p=now[x]; p; p=pre[p]) 50         { 51             int son=v[p]; 52             if (cap[p] && deep[son]==-1) 53             { 54                 deep[son]=deep[x]+1; 55                 if (son==T) return 1; 56                 list[++tail]=son; 57             } 58         } 59     } 60     return 0; 61 } 62 int find(int x,int tmpflow) 63 { 64     int temp,re; 65     if (x==T) return tmpflow; 66     re=temp=0; 67     for (int p=now[x]; p; p=pre[p]) 68     { 69         int son=v[p];  70         if (cap[p] && deep[son]==deep[x]+1) 71         { 72             temp=find(son,min(tmpflow,cap[p])); 73             cap[p]-=temp; 74             cap[p^1]+=temp; 75             re+=temp; 76             tmpflow-=temp; 77             if (tmpflow==0) break; 78         } 79     } 80     deep[x]=-1; 81     return re; 82 } 83 void dinic() 84 { 85     ans=0; 86     while (bfs()) 87     { 88         ans+=find(S,inf); 89     } 90 } 91 int main() 92 { 93     tot=1; 94     init_build(); 95     dinic(); 96     printf("%d\n",ans); 97     return 0; 98 } 99 100 BZOJ 1642101 102 #include<iostream>103 #include<cstring>104 #include<cmath>105 #include<cstdio>106 #include<algorithm>107 using namespace std;108 int n,m,r,ans=0;109 int read(){110   int x=0,f=1; char ch;111   while (ch=getchar(),ch<‘0‘||ch>‘9‘) if (ch==‘-‘) f=-1;112   while (x=x*10+ch-‘0‘,ch=getchar(),ch>=‘0‘&&ch<=‘9‘);113   return x*f;114 }115 struct data{116   int l,r,val;117 }a[1005];118 int f[1005];119 bool cmp(data a,data b)120 {121   return a.l==b.l?a.r<b.r:a.l<b.l;122 }123 int main()124 {125   n=read(); m=read()+1; r=read();126   a[1].l=a[1].r=-100; a[1].val=0;127   for (int i=2; i<=m; i++)128     {129       a[i].l=read(),a[i].r=read()-1,a[i].val=read();130     }131   sort(a+1,a+m+1,cmp);132   for (int i=2; i<=m; i++)133     {134       for (int j=1; j<=i-1; j++)135     {136       if (a[j].r+r<a[i].l)137         {138           f[i]=max(f[i],f[j]+a[i].val);139           ans=max(ans,f[i]);140         }141     }142     }143   printf("%d\n",ans);144   return 0;145 }

  1 BZOJ 1708  2   3 #include<iostream>  4 #include<cstring>  5 #include<algorithm>  6 #include<cmath>  7 #include<cstdio>  8 #define ll long long  9 using namespace std; 10 int n,m; 11 ll f[10005]; 12 int read() 13 { 14     int x=0,f=1; char ch; 15     while (ch=getchar(),ch<‘0‘||ch>‘9‘) if (ch==‘-‘) f=-1; 16     while (x=x*10+ch-‘0‘,ch=getchar(),ch>=‘0‘&&ch<=‘9‘); 17     return x*f; 18 } 19 int main() 20 { 21     n=read(); m=read(); f[0]=1; 22     for (int i=1; i<=n; i++) 23     { 24         int x=read(); 25         for (int i=x; i<=m; i++) f[i]+=f[i-x]; 26     } 27     printf("%lld\n",f[m]); 28     return 0; 29 } 30  31  32 BZOJ1690 33 #include<iostream> 34 #include<cstring> 35 #include<algorithm> 36 #include<cmath> 37 #include<cstdio> 38 #define ll long long 39 #define N 1005 40 #define M 5005 41 using namespace std; 42 int n,m,tot; 43 int a[N],now[N],pre[M],v[M]; 44 double ans,mid,val[M],value[N],dis[N]; 45 bool vis[N]; 46 int read() 47 { 48     int x=0,f=1; char ch; 49     while (ch=getchar(),ch<‘0‘||ch>‘9‘) if (ch==‘-‘) f=-1; 50     while (x=x*10+ch-‘0‘,ch=getchar(),ch>=‘0‘&&ch<=‘9‘); 51     return x*f; 52 } 53 void ins(int a,int b,int c){++tot; pre[tot]=now[a]; now[a]=tot; v[tot]=b; val[tot]=c; 54 } 55 bool spfa(int x) 56 { 57     vis[x]=1; 58     for (int p=now[x]; p; p=pre[p]) 59     { 60         int son=v[p]; 61         if (dis[son]<dis[x]+value[son]-mid*val[p]) 62         { 63             if (!vis[son]) 64             { 65                 dis[son]=dis[x]+value[son]-mid*val[p]; 66                 if (spfa(son)) return 1; 67              } 68             else return 1; 69         } 70     } 71     return vis[x]=0; 72 } 73 int main() 74 { 75     n=read(); m=read(); 76     for (int i=1; i<=n; i++) value[i]=read(); 77     for (int i=1; i<=m; i++) 78     { 79         int a=read(),b=read(),c=read(); ins(a,b,c); 80     } 81     double l=0,r=1000,eps=1e-3; 82     while (r-l>eps) 83     { 84         memset(dis,254,sizeof(dis)); 85         memset(vis,0,sizeof(vis)); 86         mid=(l+r)/2.0; dis[1]=0.0; 87         if (spfa(1)) ans=mid,l=mid; else r=mid; 88      }  89      printf("%0.2lf\n",ans);  90     return 0; 91 } 92  93  94 BZOJ1669 95  96 #include<iostream> 97 #include<cstring> 98 #include<algorithm> 99 #include<cmath>100 #include<cstdio>101 #define N 5005102 #define ll long long103 using namespace std;104 int n,tot;105 int b[N];106 int read()107 {108     int x=0,f=1; char ch;109     while (ch=getchar(),ch<‘0‘||ch>‘9‘) if (ch==‘-‘) f=-1;110     while (x=x*10+ch-‘0‘,ch=getchar(),ch>=‘0‘&&ch<=‘9‘);111     return x*f;112 }113 int main()114 {115     int n=read(),tot=0;116     for (int i=1; i<=n; i++)117     {118         int x=read();119         if (x>b[tot]) 120         {121             tot++; b[tot]=x; 122         }123         else124         {125             int l=tot;126             while (l>=1 && b[l]>=x) l--;127             //cout<<" "<<l<<endl;128             b[l+1]=x;129         }130     }131     printf("%d\n",tot);132     return 0;133 }

  1 BZOJ3298  2   3   4 #include<iostream>  5 #include<cstring>  6 #include<algorithm>  7 #include<cmath>  8 #include<cstdio>  9 #define ll long long 10 #define N 1000005 11 using namespace std; 12 int n,m,f[N]; 13 int read() 14 { 15     int x=0,f=1; char ch; 16     while (ch=getchar(),ch<‘0‘||ch>‘9‘) if (ch==‘-‘) f=-1; 17     while (x=x*10+ch-‘0‘,ch=getchar(),ch>=‘0‘&&ch<=‘9‘); 18     return x*f; 19 } 20 int main() 21 { 22     n=read()+1; m=read()+1; 23     f[1]=1; int t=0; 24     for (int i=2; i<=m; i++) 25     { 26         if (f[i]) continue; 27         t++; f[i]=i+t; if (i+t<=m) f[i+t]=i; 28      }  29      int T=read(); 30      while (T--) 31      { 32          int x=read()+1,y=read()+1; 33          if (f[x]==y) printf("Farmer John\n"); else printf("Bessie\n"); 34      } 35     return 0; 36  }  37  38  39 BZOJ3296 40  41 #include<iostream> 42 #include<cstring> 43 #include<algorithm> 44 #include<cmath> 45 #include<cstdio> 46 #define ll long long 47 #define N 40005 48 using namespace std; 49 int fa[N],id[N],n,m,ans; 50 int read() 51 { 52     int x=0,f=1; char ch; 53     while (ch=getchar(),ch<‘0‘||ch>‘9‘) if (ch==‘-‘) f=-1; 54     while (x=x*10+ch-‘0‘,ch=getchar(),ch>=‘0‘&&ch<=‘9‘); 55     return x*f; 56 } 57 int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]); 58 } 59 int main() 60 { 61     n=read(); m=read(); 62     for (int i=1; i<=n; i++) fa[i]=i; 63     for (int i=1; i<=n; i++) 64     { 65         int k=read(); 66         for (int j=1; j<=k; j++){int x=read(); if (!id[x]) id[x]=i; else {fa[find(id[x])]=find(i); id[x]=i;}} 67     } 68     for (int i=1; i<=n; i++) if (find(i)==i) ans++; 69     printf("%d\n",ans-1); 70     return 0; 71 } 72  73  74 BZOJ1599 75  76 #include<iostream> 77 #include<cstring> 78 #include<algorithm> 79 #include<cmath> 80 #include<cstdio> 81 #define ll long long 82 using namespace std; 83 int sum[105],ans; 84 int read() 85 { 86     int x=0,f=1; char ch; 87     while (ch=getchar(),ch<‘0‘||ch>‘9‘) if (ch==‘-‘) f=-1; 88     while (x=x*10+ch-‘0‘,ch=getchar(),ch>=‘0‘&&ch<=‘9‘); 89     return x*f; 90 } 91 int main() 92 {     93     int a=read(),b=read(),c=read(); 94     for (int i=1; i<=a; i++) 95         for (int j=1; j<=b; j++) 96             for (int k=1; k<=c; k++) sum[i+j+k]++; 97     sum[0]=0; ans=0; for (int i=3; i<=a+b+c; i++) if (sum[i]>sum[ans]) ans=i; 98     printf("%d\n",ans); 99     return 0;100 }101 102 103 BZOJ1232104 105 #include<iostream>106 #include<cstring>107 #include<algorithm>108 #include<cmath>109 #include<cstdio>110 #define ll long long111 #define N 100005112 using namespace std;113 int n,m;114 struct data{115     int u,v,val;116 }a[N];117 int c[N],Min=0x7fffffff,ans=0,fa[N],cnt=0;118 int read()119 {120     int x=0,f=1; char ch;121     while (ch=getchar(),ch<‘0‘||ch>‘9‘) if (ch==‘-‘) f=-1;122     while (x=x*10+ch-‘0‘,ch=getchar(),ch>=‘0‘&&ch<=‘9‘);123     return x*f;124 }125 bool cmp(data a,data b){return a.val<b.val;126 }127 int find(int x) {return x==fa[x]?x:fa[x]=find(fa[x]);}128 int main()129 {130     n=read(); m=read();131     for (int i=1; i<=n; i++) fa[i]=i;132     for (int i=1; i<=n; i++) c[i]=read();133     for (int i=1; i<=m; i++) a[i].u=read(),a[i].v=read(),a[i].val=read()*2+c[a[i].u]+c[a[i].v];134     sort(a+1,a+m+1,cmp);135     for (int i=1; i<=m; i++)136     {137         int u=a[i].u,v=a[i].v,val=a[i].val;138         int fu=find(u),fv=find(v);139         if (fv!=fu)140         {141             fa[fv]=fu; Min=min(Min,min(c[u],c[v])); 142             ans+=val; cnt++; if (cnt==n-1) break;143         }144     }145     printf("%d\n",ans+Min);146     return 0;147 }