第一行为N、M，其中 表示顶点的数目， 表示边的数目。顶点的编号为1、2、3、……、N-1、N。接下来的M行，每行三个整数Ui，Vi，Wi，表示顶点Ui与Vi之间有一条边，其权值为Wi。所有的边在输入中会且仅会出现一次。再接着N-1行，每行两个整数Xi、Yi，表示顶点Xi与Yi之间的边是T的一条边。

输出最小权值

 1<=n<=50,1<=m<=800,1<=wi<=1000

n-->点数..m-->边数..wi--->边权

  1 /*by SilverN*/  2 #include<algorithm>  3 #include<iostream>  4 #include<cstring>  5 #include<cstdio>  6 #include<cmath>  7 #include<vector>  8 #include<queue>  9 #define LL long long 10 using namespace std; 11 const int mxn=100010; 12 int read(){ 13     int x=0,f=1;char ch=getchar(); 14     while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 15     while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} 16     return x*f; 17 } 18 vector<int>ve[120]; 19 struct EG{ 20     int x,y,w; 21 }eg[mxn]; 22 struct edge{ 23     int u,v,nxt,f,w; 24 }e[mxn<<2]; 25 int hd[mxn],mct=1; 26 void add_edge(int u,int v,int f,int w){ 27     e[++mct].nxt=hd[u];e[mct].v=v;e[mct].u=u; 28     e[mct].f=f;e[mct].w=w;hd[u]=mct;return; 29 } 30 void insert(int u,int v,int c,int w){ 31     add_edge(u,v,c,w); add_edge(v,u,0,-w); 32     return; 33 } 34 int n,m,S,T; 35 int dis[1010]; 36 int pre[mxn]; 37 bool inq[mxn]; 38 bool SPFA(){ 39     memset(dis,-0x3f,sizeof dis); 40     memset(pre,0,sizeof pre); 41     int dd=dis[0]; 42     dis[S]=0; 43     queue<int>q; 44     q.push(S); 45     while(!q.empty()){ 46         int u=q.front();q.pop(); 47         inq[u]=0; 48         for(int i=hd[u],v;i;i=e[i].nxt){ 49             if(!e[i].f)continue; 50             v=e[i].v; 51             if(dis[v]<dis[u]+e[i].w){ 52                 dis[v]=dis[u]+e[i].w; 53                 pre[v]=i; 54                 if(!inq[v]){ 55                     inq[v]=1; 56                     q.push(v); 57                 } 58             } 59         } 60     } 61     return (dis[T]!=dd); 62 } 63 int MCF(){ 64 //    SPFA(); 65     int res=0; 66     while(SPFA()){ 67         if(dis[T]<=0)break; 68         int tmp=1e9; 69         for(int x=pre[T];x;x=pre[e[x].u]) 70             tmp=min(tmp,e[x].f); 71         res+=tmp*dis[T]; 72         for(int x=pre[T];x;x=pre[e[x].u]){ 73             e[x].f-=tmp; 74             e[x^1].f+=tmp; 75         } 76     } 77     return res; 78 } 79 int mp[120][120],tp[120][120]; 80 int id[120][120]; 81 int fa[mxn]; 82 void DFS(int u,int ff){ 83     fa[u]=ff; 84     for(int i=0;i<ve[u].size();i++){ 85         if(ve[u][i]==ff)continue; 86         DFS(ve[u][i],u); 87     } 88     return; 89 } 90 void Build(){ 91     int i,j; 92     S=0;T=m+1; 93     for(i=1;i<=m;i++){ 94         int x=eg[i].x,y=eg[i].y; 95         if(mp[x][y])continue; 96         DFS(y,0); 97         for(;x!=y;x=fa[x]){ 98             int tmp=mp[x][fa[x]]-eg[i].w; 99             if(tmp>0)insert(id[x][fa[x]],i,1,tmp);100         }101     }102     for(i=1;i<=m;i++){103         if(mp[eg[i].x][eg[i].y])insert(S,i,1,0);104         else insert(i,T,1,0);105     }106     return;107 }108 int main(){109     int i,j;110     n=read();m=read();111     for(i=1;i<=m;i++){112         eg[i].x=read();eg[i].y=read();eg[i].w=read();113         tp[eg[i].x][eg[i].y]=tp[eg[i].y][eg[i].x]=eg[i].w;;114         id[eg[i].x][eg[i].y]=i;115         id[eg[i].y][eg[i].x]=i;//116     }117     int x,y;118     for(i=1;i<n;i++){119         x=read();y=read();120         ve[x].push_back(y);121         ve[y].push_back(x);122         mp[x][y]=mp[y][x]=tp[x][y];123         tp[x][y]=tp[y][x]=0;124     }125     Build();126     int ans=MCF();127     printf("%d\n",ans);128     return 0;129 }