Drivers Dissatisfaction 最小生成树+LCA

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <queue>
  4 #include <cmath>
  5 #include <algorithm>
  6 #include <set>
  7 #include <iostream>
  8 #include <map>
  9 #include <stack>
 10 #include <string>
 11 #include <vector>
 12 #define  pi acos(-1.0)
 13 #define  eps 1e-6
 14 #define  fi first
 15 #define  se second
 16 #define  rtl   rt<<1
 17 #define  rtr   rt<<1|1
 18 #define  bug         printf("******n")
 19 #define  mem(a,b)    memset(a,b,sizeof(a))
 20 #define  name2str(x) #x
 21 #define  fuck(x)     cout<<#x" = "<<x<<endl
 22 #define  f(a)        a*a
 23 #define  sf(n)       scanf("%d",&n)
 24 #define  sff(a,b)    scanf("%d %d",&a,&b)
 25 #define  sfff(a,c) scanf("%d %d %d",&b,&c)
 26 #define  sffff(a,c,d) scanf("%d %d %d %d",&c,&d)
 27 #define  pf          printf
 28 #define  FRE(i,a,b)  for(i = a; i <= b; i++)
 29 #define  FREE(i,b) for(i = a; i >= b; i--)
 30 #define  FRL(i,b)  for(i = a; i < b; i++)+
 31 #define  FRLL(i,b) for(i = a; i > b; i--)
 32 #define  FIN         freopen("data.txt","r",stdin)
 33 #define  gcd(a,b)    __gcd(a,b)
 34 #define  lowbit(x)   x&-x
 35 using namespace std;
 36 typedef long long  LL;
 37 typedef unsigned long long ULL;
 38 const int mod = 1e9 + 7;
 39 const int maxn = 2e5 + 10;
 40 const int INF = 0x3f3f3f3f;
 41 const LL INFLL = 0x3f3f3f3f3f3f3f3fLL;
 42 int n,m,c[maxn],w[maxn],fa[maxn],vis[maxn];
 43 int dep[maxn],p[maxn][21],maxx[maxn][21];
 44 struct Edge {
 45     int u,v,w,id;
 46 } edge[maxn];
 47 int cmp ( Edge a,Edge b ) {
 48     return a.w < b.w;
 49 }
 50 struct xxx {
 51     int v,id;
 52     xxx ( int v,int id ) : v ( v ),id ( id ) {}
 53 };
 54 vector<xxx>mp[maxn];
 55 int Find ( int x ) {
 56     return fa[x] == x ? x : fa[x] = Find ( fa[x] );
 57 }
 58 void dfs ( int u,int f,int id ) {
 59     dep[u] = dep[f] + 1,p[u][0] = f,maxx[u][0] = id;
 60     for ( int i = 1 ; i <= 20 ; i++ ) {
 61         if ( dep[u] - ( 1 << i ) <= 0 ) break;
 62         int v = p[u][i - 1];
 63         p[u][i] = p[v][i - 1];
 64         if ( w[maxx[u][i - 1]] < w[maxx[v][i - 1]] ) maxx[u][i] = maxx[v][i - 1];
 65         else maxx[u][i] = maxx[u][i - 1];
 66     }
 67     for ( int i = 0 ; i < mp[u].size() ; i++ ) {
 68         int v = mp[u][i].v,id = mp[u][i].id;
 69         if ( v != f ) dfs ( v,u,id );
 70     }
 71 }
 72 int get_max ( int x,int y ) {
 73     if ( dep[x] < dep[y] ) swap ( x,y );
 74     int temp = 0,ans = 0;
 75     for ( int i = 20 ; i >= 0 ; i-- ) {
 76         if ( dep[x] - ( 1 << i ) >= dep[y] ) {
 77             if ( w[maxx[x][i]] > temp ) ans = maxx[x][i],temp = w[ans];
 78             x = p[x][i];
 79         }
 80     }
 81     if ( x == y ) return ans;
 82     for ( int i = 20 ; i >= 0 ; i-- ) {
 83         if ( dep[x] - ( 1 << i ) > 0 && p[x][i] != p[y][i] ) {
 84             if ( w[maxx[x][i]] > temp ) ans = maxx[x][i],temp = w[ans];
 85             if ( w[maxx[y][i]] > temp ) ans = maxx[y][i],temp = w[ans];
 86             x = p[x][i],y = p[y][i];
 87             if ( x == y ) break;
 88         }
 89     }
 90     if ( w[maxx[x][0]] > temp ) ans = maxx[x][0],temp = w[ans];
 91     if ( w[maxx[y][0]] > temp ) ans = maxx[y][0],temp = w[ans];
 92     return ans;
 93 }
 94 int main() {
 95     sff ( n,m );
 96     for ( int i = 1 ; i <= m ; i++ ) sf ( w[i] );
 97     for ( int i = 1 ; i <= m ; i++ ) sf ( c[i] );
 98     for ( int i = 1 ; i <= m ; i++ ) {
 99         sff ( edge[i].u,edge[i].v );
100         edge[i].w = w[i],edge[i].id = i;
101     }
102     sort ( edge + 1,edge + 1 + m,cmp );
103     LL sum = 0,s,minn = INF,idx = 0,k = 0;
104     scanf ( "%lld",&s );
105     for ( int i = 1 ; i <= n ; i++ ) fa[i] = i;
106     for ( int i = 1 ; i <= m ; i++ ) {
107         int nx = Find ( edge[i].v ),ny = Find ( edge[i].u );
108         if ( nx == ny ) continue;
109         fa[nx] = ny;
110         sum += edge[i].w;
111         vis[edge[i].id] = 1,k++;
112         if ( c[edge[i].id] < minn )  idx = edge[i].id,minn = c[edge[i].id];
113         mp[edge[i].u].push_back ( xxx ( edge[i].v,edge[i].id ) );
114         mp[edge[i].v].push_back ( xxx ( edge[i].u,edge[i].id ) );
115         if ( k == n - 1 ) break;
116     }
117     LL ans = sum - s / minn;
118     dep[0] = 0;
119     dfs ( 1,0,0 );
120     int del = 0;
121     for ( int i = 1 ; i <= m ; i++ ) {
122         if ( vis[edge[i].id]  ) continue;
123         int cnt = get_max ( edge[i].u,edge[i].v );
124         if ( cnt == 0 ) continue;
125         LL temp = sum - w[cnt] + w[edge[i].id] - s / c[edge[i].id];
126         if ( temp < ans ) ans = temp,idx = edge[i].id,del = cnt;
127     }
128     if ( del ) vis[del] = 0,vis[idx] = 1;
129     printf ( "%lldn",ans );
130     w[idx] -= s / c[idx];
131     for ( int i = 1 ; i <= m ; i++ ) if ( vis[i] ) printf ( "%d %dn",i,w[i] );
132     return 0;
133 }