[关闭]
@ysner 2018-08-13T16:35:36.000000Z 字数 1464 阅读 1715

[UVA10859]Placing Lampposts

DP 树形DP


题面

给定一个个点条边的无向无环图,在尽量少的节点上放灯,使得所有边都与灯相邻(被灯照亮)。
在灯的总数最小的前提下,被两盏灯同时照亮的边数应该尽可能大。

题面

有一种套路,如果要同时最小化或最大化两个量,则等价于最小化或最大化
并且,必须大到足以区分。一般来说,
所以本题可以设

但是,题目要求是最小化,最大化???
可以转化一下,把表示为“只被一盏灯照亮的边数”(因为)。

于是设分别表示以为根的子树内,不放灯和放灯对答案()的贡献。
转移时不统计被两盏灯同时照亮的边的贡献。

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstdlib>
  4. #include<cstring>
  5. #include<cmath>
  6. #include<algorithm>
  7. #include<vector>
  8. #define re register
  9. #define il inline
  10. #define ll long long
  11. #define max(a,b) ((a)>(b)?(a):(b))
  12. #define min(a,b) ((a)<(b)?(a):(b))
  13. #define fp(i,a,b) for(re int i=a;i<=b;i++)
  14. #define fq(i,a,b) for(re int i=a;i>=b;i--)
  15. using namespace std;
  16. const int mod=1e9+7,N=2000,M=3000;
  17. struct Edge{int to,nxt;}e[N<<1];
  18. int n,m,h[N],cnt,dp[N][2],vis[N];
  19. il void add(re int u,re int v){e[++cnt]=(Edge){v,h[u]};h[u]=cnt;}
  20. ll ans=0;
  21. il ll gi()
  22. {
  23. re ll x=0,t=1;
  24. re char ch=getchar();
  25. while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  26. if(ch=='-') t=-1,ch=getchar();
  27. while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  28. return x*t;
  29. }
  30. il void dfs(re int u,re int fa)
  31. {
  32. vis[u]=1;dp[u][0]=0;dp[u][1]=M;
  33. for(re int i=h[u];i+1;i=e[i].nxt)
  34. {
  35. re int v=e[i].to;
  36. if(v==fa||vis[v]) continue;
  37. dfs(v,u);
  38. dp[u][0]+=dp[v][1]+1;
  39. dp[u][1]+=min(dp[v][0]+1,dp[v][1]);
  40. }
  41. }
  42. int main()
  43. {
  44. re int T=gi();
  45. while(T--)
  46. {
  47. memset(h,-1,sizeof(h));cnt=0;
  48. n=gi();m=gi();ans=0;
  49. memset(vis,0,sizeof(vis));
  50. fp(i,1,m)
  51. {
  52. re int u=gi()+1,v=gi()+1;
  53. add(u,v);add(v,u);
  54. }
  55. fp(i,1,n)
  56. if(!vis[i]) dfs(i,0),ans+=min(dp[i][0],dp[i][1]);
  57. printf("%lld %lld %lld\n",ans/M,m-ans%M,ans%M);
  58. }
  59. return 0;
  60. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注