社区讨论
题目什么意思,我理解错了吗(贴代码)
P1525[NOIP 2010 提高组] 关押罪犯参与者 3已保存回复 8
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 8 条
- 当前快照
- 1 份
- 快照标识符
- @lo8qketv
- 此快照首次捕获于
- 2023/10/27 22:56 2 年前
- 此快照最后确认于
- 2023/10/27 22:56 2 年前
CPP
#include<bits/stdc++.h>
using namespace std ;
const int Maxs = 500000 , TIL = ( 1 << 28 ) ;
struct NODE { int X , Y ; long long W ; } Sum[Maxs] ;
bool RmQ( NODE X , NODE Y ) { return X.W < Y.W ; }
struct Node { int V , W , Next ; } Tree[Maxs] ;
int Box[Maxs] , Ecnt = 1 ;
long long Size[Maxs] ;
long long Ans = TIL ;
int Fa[Maxs] ;
int N , M ;
int Fin( int X ) {
if( Fa[X] == X ) return X ;
else return Fa[X] = Fin( Fa[X] ) ;
}
int ADD( int u , int v , int w ) {
Tree[Ecnt].V = v ;
Tree[Ecnt].W = w ;
Tree[Ecnt].Next = Box[u] ;
Box[u] = Ecnt ++ ;
}
int DFS( int X , int F ) {
Size[X] = false ;
for(int i = Box[X] ; i ; i = Tree[i].Next ) {
int V = Tree[i].V ; if( V == F ) continue ;
DFS( V , X ) ; Size[X] += Size[V] + Tree[i].W ;
}
}
int BFS( int X , int F ) {
for(int i = Box[X] ; i ; i = Tree[i].Next ) {
int V = Tree[i].V ; if( V == F ) continue ;
Ans = min( Ans , max( Size[V] , Size[1] - Size[V] - Tree[i].W )) ;
BFS( V , X ) ;
}
}
int main( ) {
scanf("%d%d" , &N , &M ) ;
for(int i = 1 ; i <= N ; i ++ ) Fa[i] = i ;
for(int i = 1 ; i <= M ; i ++ )
scanf("%d%d%d" , &Sum[i].X , &Sum[i].Y , &Sum[i].W ) ;
sort( Sum + 1 , Sum + M + 1 , RmQ ) ;
for(int i = 1 ; i <= M ; i ++ ) {
if( M <= N - 1 ) break ;
int A = Fin( Sum[i].X ) , B = Fin( Sum[i].Y ) ;
if( A == B ) continue ;
ADD( Sum[i].X , Sum[i].Y , Sum[i].W ) ;
ADD( Sum[i].Y , Sum[i].X , Sum[i].W ) ;
Fa[A] = B ;
}
DFS( 1 , - 1 ) ;
BFS( 1 , - 1 ) ;
for(int i = 1 ; i <= N ; i ++ ) cout << Size[i] << endl ;
printf("%lld" , ( Ans == TIL ) ? false : Ans ) ;
return false ;
}
//4 3
//1 2 1000
//2 3 10000
//3 4 9000
我的理解,两个监狱分别的和最大值最小
回复
共 8 条回复,欢迎继续交流。
正在加载回复...