社区讨论

题目什么意思,我理解错了吗(贴代码)

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 条回复,欢迎继续交流。

正在加载回复...