说在前面
感觉me变得颓废了… 闲得去看别人的NOI游记了… 以前总是觉得「和别人比高低、被催促着学习、不学就会落后」这样的感觉差极了 然而me现在才慢慢的感受到…竞争才能跑得更快
题目
BZOJ1937传送门 看题可戳传送门
解法
me记得me曾经用单纯形法水过了这道题emmmm
首先一个显然的事实：树边的权值只会减少，非树边的权值只会增加 然后我们相当于是要满足这个条件：任何一条非树边与这个树构成的环，非树边的权值最大
记
wi
w
i
为第
i
i
条边的权值，didi 为改变量 然后就是要
wi−di≤wj+dj
w
i
−
d
i
≤
w
j
+
d
j
，其中
i
i
是树边，jj 是非树边。我们的目的是要最小化：
∑dk
∑
d
k
移项变成了：
wi−wj≤di+dj
w
i
−
w
j
≤
d
i
+
d
j
然后这就是一个线性规划的式子，直接单纯形暴力做就好了 然后我们发现，这个式子很像KM算法中对于顶标的定义，要求的东西也正好是KM算法的意义 所以直接用KM算法解决这道题
题外话：其实不难发现，最大权匹配也是线性规划的一种
下面是代码
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;
int N , M , ide[
55][
55] , head[
55] , tp ;
struct Edge{
int u , v , w ;
bool intree ;
} e[
855] ;
struct Path{
int pre , to ;
} p[
1655] ;
template <
typename T >
void smax( T &x , T y ){
if( x < y ) x = y ; }
template <
typename T >
void smin( T &x , T y ){
if( x > y ) x = y ; }
void In(
int t1 ,
int t2 ){
p[++tp] = ( Path ){ head[t1] , t2 } ; head[t1] = tp ;
p[++tp] = ( Path ){ head[t2] , t1 } ; head[t2] = tp ;
}
bool vy[
805] , vx[
805] ;
int macy[
805] , macx[
805] , que[
805] , fr , ba , lac[
805] , pre[
805] ;
int dep[
805] , fa[
805] , w[
805][
805] , lx[
805] , ly[
805] ;
void dfs(
int u ,
int f ){
for(
int i = head[u] ; i ; i = p[i].pre ){
int v = p[i].to ;
if( v == f )
continue ;
dep[v] = dep[u] +
1 ;
fa[v] = u , dfs( v , u ) ;
}
}
void Jump(
int u ,
int v ,
int id ){
while( u != v ){
if( dep[u] < dep[v] ) swap( u , v ) ;
int id2 = ide[ fa[u] ][u] ;
w[id2][id] = e[id2].w - e[id].w ;
u = fa[u] ;
}
}
void preWork(){
dfs(
1 ,
1 ) ;
for(
int i =
1 ; i <= M ; i ++ )
if( !e[i].intree ) Jump( e[i].u , e[i].v , i ) ;
for(
int i =
1 ; i <= M ; i ++ )
for(
int j =
1 ; j <= M ; j ++ )
smax( lx[i] , w[i][j] ) ;
}
void match(
int v ){
while( v ){
macy[v] = pre[v] ;
swap( v , macx[ pre[v] ] ) ;
}
}
void BFS(
int St ){
fr =
1 , que[ ba =
1 ] = St , vx[St] =
true ;
while(
true ){
while( ba >= fr ){
int u = que[fr++] , tmp ;
for(
int v =
1 ; v <= M ; v ++ ){
tmp = lx[u] + ly[v] - w[u][v] ;
if( vy[v] || tmp >= lac[v] )
continue ;
pre[v] = u ;
if( !tmp ){
if( !macy[v] )
return match( v ) ;
vy[v] = vx[ macy[v] ] =
true ;
que[++ba] = macy[v] ;
}
else lac[v] = tmp ;
}
}
int rem =
0x3f3f3f3f , v ;
for(
int i =
1 ; i <= M ; i ++ )
if( !vy[i] && rem > lac[i] ) rem = lac[i] , v = i ;
if( rem ==
0x3f3f3f3f )
return ;
for(
int i =
1 ; i <= M ; i ++ ){
if( vx[i] ) lx[i] -= rem ;
if( vy[i] ) ly[i] += rem ;
else lac[i] -= rem ;
}
if( !macy[v] )
return match( v ) ;
vy[v] = vx[ macy[v] ] =
true , que[++ba] = macy[v] ;
}
}
void solve(){
for(
int i =
1 ; i <= M ; i ++ )
if( !macx[i] ){
memset( vx ,
0 ,
sizeof( vx ) ) ;
memset( vy ,
0 ,
sizeof( vy ) ) ;
memset( lac ,
0x3f ,
sizeof( lac ) ) ;
BFS( i ) ;
}
long long ans =
0 ;
for(
int i =
1 ; i <= M ; i ++ )
ans += lx[i] + ly[i] ;
printf(
"%lld\n" , ans ) ;
}
int main(){
scanf(
"%d%d" , &N , &M ) ;
for(
int i =
1 , u , v , w ; i <= M ; i ++ ){
scanf(
"%d%d%d" , &u , &v , &w ) ;
e[i] = ( Edge ){ u , v , w ,
0 } ;
ide[u][v] = ide[v][u] = i ;
}
for(
int i =
1 , u , v ; i < N ; i ++ ){
scanf(
"%d%d" , &u , &v ) , In( u , v ) ;
e[ ide[u][v] ].intree =
true ;
} preWork() ; solve() ;
}
