首页 > 代码库 > UVA 10859 Placing Lampposts 树形DP
UVA 10859 Placing Lampposts 树形DP
dfs+记忆化搜索,白书上给了一种很神的存答案的方式,要同时保存两个值,可以将一个值乘以一个大整数加上另外一个。
具体状态转移见注释
#include <cstdio>#include <cstring>#include <iostream>#include <map>#include <set>#include <vector>#include <string>#include <queue>#include <deque>#include <bitset>#include <list>#include <cstdlib>#include <climits>#include <cmath>#include <ctime>#include <algorithm>#include <stack>#include <sstream>#include <numeric>#include <fstream>#include <functional>using namespace std;#define MP make_pair#define PB push_backtypedef long long LL;typedef unsigned long long ULL;typedef vector<int> VI;typedef pair<int,int> pii;const int INF = INT_MAX / 3;const double eps = 1e-8;const LL LINF = 1e17;const double DINF = 1e60;const int maxn = 1005;VI e[maxn];int n, m, vis[maxn][2], note[maxn][2];int dfs(int i, int j, int f) { if(vis[i][j]) return note[i][j]; vis[i][j] = 1; int &ret = note[i][j] = INF; //如果当前节点不放灯(父亲节点必须放灯) //总数为每一个节点的和 × 2000 + 1 //需要对根节点进行特判 int sum = f == -1 ? 0 : 1, mm = e[i].size(); if(j) { for(int nx = 0;nx < mm;nx++) if(e[i][nx] != f) { sum += dfs(e[i][nx], 0, i); } ret = sum; } //当前节点放灯 //总数为每一个节点的和*2000,然后如果父亲节点没有灯,再+1 sum = j == 0 ? 1 : 0; for(int nx = 0;nx < mm;nx++) if(e[i][nx] != f) { sum += dfs(e[i][nx], 1, i); } sum += 2000; ret = min(sum,ret); return ret;}int main() { int T; scanf("%d",&T); while(T--) { memset(vis,0,sizeof(vis)); memset(note,0,sizeof(note)); scanf("%d%d",&n,&m); for(int i = 0;i < n;i++) e[i].clear(); for(int i = 0;i < m;i++) { int a,b; scanf("%d%d",&a,&b); e[a].PB(b); e[b].PB(a); } //当前节点,父节点有没有点亮,父节点编号 //dfs(i,j,k) //枚举森林中的每一棵树 int ans = 0; for(int i = 0;i < n;i++) if(!vis[i][0]) { ans += dfs(i,1,-1); } printf("%d %d %d\n",ans / 2000,m - ans % 2000,ans % 2000); } return 0;}
UVA 10859 Placing Lampposts 树形DP
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。