「BZOJ1232」 [Usaco2008Nov]安慰奶牛cheer

problem

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 100005
using 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