HDU4126

  1 #include<iostream>
  2 #include<algorithm>
  3 #include<string.h>
  4 #include<vector>
  5 using namespace std;
  6 const int INF=1e9;
  7 struct edge{
  8     int from,to,w;
  9     bool operator < (const edge &a){
 10         return w<a.w;
 11     }
 12 }e[3001*3001];
 13 struct node{
 14     int to,w;
 15 };
 16 vector<node> a[3001];
 17 int n,m,q,mst,f[3001],dp[3001][3001],mp[3001][3001],ins[3001][3001],used[3001][3001];
 18 double ans;
 19 
 20 void ini(){
 21     for (int i=0;i<n;i++) f[i]=i;
 22     for (int i=0;i<n;i++){
 23         for (int j=0;j<n;j++) dp[i][j]=mp[i][j]=INF;
 24     }
 25     for (int i=0;i<n;i++) a[i].clear();
 26     mst=0;
 27     ans=0;
 28     memset(used,0,sizeof used);
 29 }
 30 
 31 int getf(int u){
 32     return f[u]==u?f[u]:f[u]=getf(f[u]);
 33 }
 34 
 35 void merge(int u,int v){
 36     f[getf(u)]=getf(v);
 37 }
 38 
 39 void kruscal(){
 40     sort(e+1,e+1+m);
 41     for (int i=1;i<=m;i++){
 42         edge &now=e[i];
 43         if (getf(now.from)!=getf(now.to)){
 44             mst+=now.w;
 45             merge(now.from,now.to);
 46             a[now.from].push_back({now.to,now.w});
 47             a[now.to].push_back({now.from,now.w});
 48             used[now.to][now.from]=used[now.from][now.to]=1;
 49         }
 50     }
 51 }
 52 
 53 int dfs1(int now,int fa,int root){
 54     for (auto nx:a[now]){
 55         if (nx.to==fa) continue;
 56         dp[root][now]=min(dp[root][now],dfs1(nx.to,now,root));
 57     }
 58     if (fa!=root) dp[root][now]=min(dp[root][now],mp[root][now]);
 59     return dp[root][now];
 60 }
 61 
 62 int dfs2(int now,int fa,int root){
 63     int ret=dp[now][root];
 64     for (auto nx:a[now]){
 65         if (nx.to==fa) continue;
 66         ret=min(ret,dfs2(nx.to,now,root));
 67     }
 68     return ret;
 69 }
 70 
 71 void solve(){
 72     for (int i=0;i<n;i++) dfs1(i,-1,i);
 73     for (int i=0;i<n;i++){
 74         for (auto nx:a[i]){
 75             ins[i][nx.to]=ins[nx.to][i]=dfs2(nx.to,i,i);
 76         }
 77     }
 78     scanf("%d",&q);
 79     for (int i=1;i<=q;i++){
 80         int u,v,w;
 81         scanf("%d %d %d",&u,&v,&w);
 82         if (!used[u][v]) ans+=mst*1.0;
 83         else ans+=mst*1.0-mp[u][v]+min(w,ins[u][v]);
 84     }
 85     printf("%.4f\n",ans/q);
 86 }
 87 
 88 int main(){
 89     while (cin>>n>>m){
 90         if (n==0 && m==0) break;
 91         ini();
 92         for (int i=1;i<=m;i++){
 93             scanf("%d %d %d",&e[i].from,&e[i].to,&e[i].w);
 94             mp[e[i].from][e[i].to]=mp[e[i].to][e[i].from]=e[i].w;
 95         }
 96         kruscal();
 97         solve();
 98     }
 99     return 0;
100 }