首页 > 代码库 > UVA 10859 Placing Lampposts
UVA 10859 Placing Lampposts
题解:
一道很基础的树形DP题目
有趣的是需要在点V1最小的情况下,边两点同时亮的条数足够大
边两点同时亮的条数足够大。等价于边一点同时亮的条数最小V2
构造X = M * V1 + V2
当M足够大时,就把2个变量维护成一个变量....interesting
DP方程
dp[ u ][ 0 ] += ( dp[ v ][ 1 ] + 1 );
dp[ u ][ 1 ] += min( dp[ v ][ 0 ] + 1,dp[ v ][ 1 ] );
+1表示边只有一点亮(excited)
代码:
#include<bits/stdc++.h> using namespace std; #define pb push_back #define mp make_pair #define se second #define fs first #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define pii pair<int,int> const int INF = 1000000000; const int maxn = 1050; const int M = 4000; int T, n, m; int cnt; int head[ maxn * 2 ]; int dp[ maxn ][ 2 ], vis[ maxn ]; struct Edge { int u, v, nxt; }edge[ maxn * 2 ]; void init() { cnt = 0; memset( head, -1, sizeof( head ) ); memset( vis, 0, sizeof( vis ) ); } void addEdge( int u, int v ) { edge[ cnt ].u = u; edge[ cnt ].v = v; edge[ cnt ].nxt = head[ u ]; head[ u ] = cnt ++; } void dfs( int u, int fa ) { dp[ u ][ 0 ] = 0; dp[ u ][ 1 ] = M; vis[ u ] = 1; for( int i = head[ u ]; i != -1; i = edge[ i ].nxt ) { int v = edge[ i ]. v; if( v == fa ) continue; dfs( v, u ); dp[ u ][ 0 ] += ( dp[ v ][ 1 ] + 1 ); dp[ u ][ 1 ] += min( dp[ v ][ 0 ] + 1,dp[ v ][ 1 ] ); } } int main() { scanf( "%d", &T ); while( T -- ) { scanf( "%d%d", &n, &m ); init(); for( int i = 1; i <= m; i ++ ) { int x, y; scanf( "%d%d", &x, &y ); addEdge( x, y ); addEdge( y, x ); } int ans = 0; for( int i = 0; i < n; i ++ ) { if( vis[ i ] ) continue; dfs( i, -1 ); ans += min( dp[ i ][ 0 ], dp[ i ][ 1 ] ); } printf( "%d %d %d\n", ans / M, m - ans % M, ans % M ); } return 0; }
UVA 10859 Placing Lampposts
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。