「BZOJ1232」 [Usaco2008Nov]安慰奶牛cheer

Solution

最终的图显然是一棵树

把每条边视作两条有向边。在树的情况下，一定需要走完所有的有向边。除了出发点以外，走一条有向边\((u,v)\)对答案的贡献为\(w(u,v)+c[v]\)，亦即每条无向边对答案的贡献为\(w(u,v)*2+c[u]+c[v]\)，将其作为边权跑最小生成树。生成树的权值加上最小的点权即为答案

Code

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #define maxn 10005#define maxm 100005using namespace std;typedef long long ll; int n,m;int c[maxn];int ans; struct edge{ int u,v,w;}g[maxm]; int prt[maxn]; int getroot(int u){ return prt[u]==u?u:prt[u]=getroot(prt[u]);} bool cmp(const edge &a,const edge &b){ return a.w