题目大意:
有一个无向无环图, 现在要选出一些点, 会覆盖和选出的点相连的边. 先要求选出的点最少的情况下, 被覆盖两次的边最多, 输出选出的点数, 被覆盖两次的边数和被覆盖一次的边数.
这个题, 怎么说呢, 很好....
其实题目说的无向无环图就是森林, 而求最小灯数的情况下最大化被覆盖两次的边, 转换一下就是最小灯数的情况下最小化只被覆盖一次的边.
那么我们设灯数是x, 只被覆盖一次的边为b, 那么我们只要最小化w=Mx+b即可, 其中M取一个大一点的数( 比方说2333 ).
答案就是ans/M, m-ans%M, ans%M.
那么就可以树形dp了.
首先刘汝佳设的状态是dp( i , 0/1 ), 即dp到i号点, 它的父亲放灯或者不放灯的最小w, 转移请看隔壁大保健的博客, 用记忆化搜索即可.
代码如下:
//made by Crazy01
#include<queue>
#include<math.h>
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#define inf 1<<30
#define ll long long
#define db double
#define c233 cout<<"233"<<endl
#define mem(s) memset(s,0,sizeof(s))
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define M 2333
const int N=1050;
using namespace std;
bool v[N][2];
int nxt[N<<1],to[N<<1],head[N],dp[N][2];
int n,m,T,maxe,ans;
inline int gi(){
int x=0,res=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')res*=-1;ch=getchar();}
while(ch<='9'&&ch>='0')x=(x<<1)+(x<<3)+ch-48,ch=getchar();
return x*res;
}
void clear(){
mem(v); mem(head); maxe=0; ans=0;
}
void build(int a,int b){
nxt[++maxe]=head[a]; to[maxe]=b; head[a]=maxe;
}
void init(){
n=gi(); m=gi();
for(int i=1;i<=m;i++){
int a=gi(),b=gi();
build(a,b); build(b,a);
}
}
int dfs(int x,int j,int fa){
if(v[x][j])return dp[x][j];
v[x][j]=1;
int ret=M;
for(int i=head[x];i;i=nxt[i]){
int u=to[i]; if(u==fa)continue;
ret+=dfs(u,1,x);
}
if(fa!=-1&&j==0)ret++;
if(j==1||fa==-1){
int tmp=0;
for(int i=head[x];i;i=nxt[i]){
int u=to[i]; if(u==fa)continue;
tmp+=dfs(u,0,x);
}
if(fa!=-1)tmp++;
ret=min(ret,tmp);
}
return dp[x][j]=ret;
}
void work(){
for(int i=0;i<n;i++)
if(!v[i][0])ans+=dfs(i,0,-1);
printf("%d %d %d
",ans/M,m-ans%M,ans%M);
}
int main(){
T=gi();
while(T--){
clear();
init();
work();
}
return 0;
}
然后我看到了一个很棒棒的dp, 和我一开始一样的思路( 没写是因为没想到转移/捂脸 ):
设dp( i , 0/1 )表示第i个点, 放或者不放的最小w.
转移则dp( i , 0 )=Σdp( son , 1 )+1; dp( i , 1 )=Σmin( dp( son , 1 ) , dp( son , 0 )+1 ).
就不用记忆化搜索了, 普通树形dp的dfs就可以了.
是不是很棒棒?
代码如下:
//made by Crazy01
#include<queue>
#include<math.h>
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#define inf 1<<30
#define ll long long
#define db double
#define c233 cout<<"233"<<endl
#define mem(s) memset(s,0,sizeof(s))
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
const int N=1050;
const int M=2333;
using namespace std;
bool v[N];
int nxt[N<<1],to[N<<1],head[N],dp[N][2];
int n,m,T,maxe,ans;
inline int gi(){
int x=0,res=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')res*=-1;ch=getchar();}
while(ch<='9'&&ch>='0')x=(x<<1)+(x<<3)+ch-48,ch=getchar();
return x*res;
}
void clear(){
mem(v); mem(dp); mem(head); maxe=0; ans=0;
}
void build(int a,int b){
nxt[++maxe]=head[a]; to[maxe]=b; head[a]=maxe;
}
void init(){
n=gi(); m=gi();
for(int i=1;i<=m;i++){
int a=gi(),b=gi();
build(a,b); build(b,a);
}
}
void dfs(int x,int fa){
dp[x][1]=M; v[x]=1;
for(int i=head[x];i;i=nxt[i]){
int u=to[i]; if(u==fa)continue;
dfs(u,x);
dp[x][0]+=dp[u][1]+1;
dp[x][1]+=min(dp[u][1],dp[u][0]+1);
}
}
void work(){
for(int i=0;i<n;i++)
if(!v[i]){
dfs(i,-1);
ans+=min(dp[i][0],dp[i][1]);
}
printf("%d %d %d
",ans/M,m-ans%M,ans%M);
}
int main(){
T=gi();
while(T--){
clear();
init();
work();
}
return 0;
}