首页 > 代码库 > UVa 10859 Placing Lampposts
UVa 10859 Placing Lampposts
这种深层递归的题还是要多多体会，只看一遍是不够的
题意:有一个森林，在若干个节点处放一盏灯，灯能照亮与节点邻接的边。要求：符合要求的放置的灯最少为多少，在灯数最少的前提下，一条边同时被两盏灯照亮的边数最多是多少。
因为边数为m，所以被两盏灯照亮的边数最多就等价于被一盏灯照亮的边数最少
因为题目中要求两个最优解，将x = Ma + c 作为最小化的目标，其中a为灯数，c为被一盏灯照亮的边数，M则是一个比较大的值，到底有多大呢？M要比c的理论上的最大值与最小值之差还要大。这样在比较x1 和 x1时，如果a1 > a2，则x1一定＞x2，这样就的好处就是将两个变量的最优解变成了一个变量的最优解，而且保证了灯数最少的前提下再求边数的最优解。
书上的两种决策说的很清楚了，我不就再啰嗦了。
我感觉我有点消化不良，认真体会，认真体会。。
1 //#define LOCAL 2 #include <vector> 3 #include <cstdio> 4 #include <cstring> 5 #include <algorithm> 6 using namespace std; 7 8 const int maxn = 1000 + 10; 9 vector<int> adj[maxn];10 int vis[maxn][2], d[maxn][2], n, m;11 12 int dp(int i, int j, int f)13 {14 if(vis[i][j]) return d[i][j];15 vis[i][j] = 1;16 int& ans = d[i][j];17 //放灯总是没有问题的18 ans = 2000;19 for(int k = 0; k < adj[i].size(); ++k)20 if(adj[i][k] != f)21 ans += dp(adj[i][k], 1, i);22 if(f >= 0 && j == 0) ++ans;23 //考虑没放灯时的情况24 if(f < 0 || j == 1)25 {26 int sum = 0;27 for(int k = 0; k < adj[i].size(); ++k)28 if(adj[i][k] != f)29 sum += dp(adj[i][k], 0, i);30 if(f >= 0) ++sum;31 ans = min(ans, sum);32 }33 return ans;34 }35 36 int main(void)37 {38 #ifdef LOCAL39 freopen("10859in.txt", "r", stdin);40 #endif41 42 int T;43 scanf("%d", &T);44 while(T--)45 {46 scanf("%d%d", &n, &m);47 for(int i = 0; i < n; ++i) adj[i].clear();48 for(int i = 0; i < m; ++i)49 {50 int a, b;51 scanf("%d%d", &a, &b);52 adj[a].push_back(b);53 adj[b].push_back(a);54 }55 memset(vis, 0, sizeof(vis));56 int ans = 0;57 for(int i = 0; i < n; ++i)58 if(!vis[i][0])59 ans += dp(i, 0, -1);60 printf("%d %d %d\n", ans/2000, m-(ans%2000), ans%2000);61 }62 return 0;63 }
UVa 10859 Placing Lampposts
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。