题目大意

给定一个 n 个点m条边的无向图。 保证图中最多只有一个点度数大于2。 现在可以设置不超过 k 个关键点，求最大的每个点到关键点的距离最小是多少。

Data Constraint k≤n≤1000,m≤1500

题解

最大值最小化问题，考虑二分答案。 不妨设那个度数大于2的点为根节点。 再观察题目，发现这个图本质上就是一个根节点套了若干个简单环和若干条链。 只有链的话，显然可以直接贪心地放置关键点。 可以考虑先枚举是哪一个点覆盖了根节点，然后这个图就变成了一堆零散的链了。

时间复杂度： O(n2logn)

SRC

#include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> using namespace std ; #define N 4000 + 10 bool flag[N] ; int Node[2*N] , Next[2*N] , Head[N] , tot ; int D[N] , Q[N] , S[N] , Dist[N] ; int n , m , lim ; int ans , Root , ret ; void link( int u , int v ) { Node[++tot] = v ; Next[tot] = Head[u] ; Head[u] = tot ; } void BFS( int st ) { int i = 0 , j = 1 ; memset( D , 0 , sizeof(D) ) ; Dist[st] = 0 ; D[1] = st ; flag[st] = 1 ; while ( i < j ) { i ++ ; int now = D[i] ; for (int p = Head[now] ; p ; p = Next[p] ) { if ( flag[Node[p]] ) continue ; flag[Node[p]] = 1 ; Dist[Node[p]] = Dist[now] + 1 ; D[++j] = Node[p] ; } } } void Del( int st , int mid ) { int i = 0 , j = 1 ; memset( Q , 0 , sizeof(Q) ) ; memset( flag , 0 , sizeof(flag) ) ; D[1] = st ; Q[st] = 0 ; flag[st] = 1 ; while ( i < j ) { i ++ ; int now = D[i] ; for (int p = Head[now] ; p ; p = Next[p] ) { if ( flag[Node[p]] ) continue ; Q[Node[p]] = Q[now] + 1 ; if ( Q[Node[p]] > mid ) { S[++S[0]] = Node[p] ; continue ; } flag[Node[p]] = 1 ; D[++j] = Node[p] ; } } } void Solve( int st , int mid ) { if ( flag[st] ) return ; memset( Q , 0 , sizeof(Q) ) ; int i = 0 , j = 1 , Len = 0 ; D[1] = st ; Q[st] = 1 ; flag[st] = 1 ; while ( i < j ) { i ++ ; int now = D[i] ; Len = max( Len , Q[now] ) ; for (int p = Head[now] ; p ; p = Next[p] ) { if ( flag[Node[p]] ) continue ; flag[Node[p]] = 1 ; Q[Node[p]] = Q[now] + 1 ; D[++j] = Node[p] ; } } ret += Len / (2 * mid + 1) + ( Len % (2 * mid + 1) != 0 ) ; } bool Check( int mid ) { for (int i = 1 ; i <= n ; i ++ ) { if ( Dist[i] > mid ) continue ; S[0] = 0 ; Del( i , mid ) ; ret = 1 ; for (int j = 1 ; j <= S[0] ; j ++ ) Solve( S[j] , mid ) ; if ( ret <= lim ) return 1 ; } return 0 ; } int main() { freopen( "rabbit.in" , "r" , stdin ) ; freopen( "rabbit.out" , "w" , stdout ) ; scanf( "%d%d%d" , &n , &m , &lim ) ; Root = 1 ; for (int i = 1 ; i <= m ; i ++ ) { int u , v ; scanf( "%d%d" , &u , &v ) ; link( u , v ) ; link( v , u ) ; D[u] ++ , D[v] ++ ; if ( D[u] > 2 ) Root = u ; if ( D[v] > 2 ) Root = v ; } BFS(Root) ; int l = 0 , r = n ; while ( l <= r ) { int mid = (l + r) / 2 ; if ( Check(mid) ) r = mid - 1 , ans = mid ; else l = mid + 1 ; } printf( "%d\n" , ans ) ; return 0 ; }

以上.