UVA 10859 Placing Lampposts

题目大意：给一个森林，让你选择尽可能少的点，使每条边至少有一个端点被选择，同时最大化两端都被选择的边。

一眼题，把最大化两个端点转化最小化一个端点树型DP，没什么好讲的，讲一下从lrj学到的新东西。

"求两个变量a,b，要求在a尽可能小时b尽可能大，可以设x=M*a+b，其中M是一个很大的数，大于b的最大理论值之差。"

“这样在求时，如果a不相同，起决定作用的就是a，b不会影响决策。”

而且还可以防止代码打错，很不错的东西。

#include    <iostream>
#include    <cstdio>
#include    <cstdlib>
#include    <algorithm>
#include    <vector>
#include    <cstring>
#include    <queue>
#include    <complex>
#include    <stack>
#define LL long long int
#define dob double
#define FILE "10859"
using namespace std;

const int N = 2010;
struct Node{int to,next;}E[N];
int n,m,head[N],tot,cnt,f[N][2],g[N][2],vis[N],root[N];

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*10+ch-48,ch=getchar();
  return x*res;
}

inline void link(int u,int v){
  E[++tot]=(Node){v,head[u]};
  head[u]=tot;
}

inline void dfs(int x,int fat){
  f[x][0]=f[x][1]=g[x][0]=g[x][1]=0;vis[x]=++f[x][1];
  for(int e=head[x];e;e=E[e].next){
    int y=E[e].to;if(y==fat)continue;
    dfs(y,x);f[x][0]+=f[y][1];g[x][0]+=(g[y][1]+1);
    if(f[y][0]==f[y][1])f[x][1]+=f[y][0],g[x][1]+=min(g[y][0]+1,g[y][1]);
    else if(f[y][0]<f[y][1])f[x][1]+=f[y][0],g[x][1]+=g[y][0]+1;
    else f[x][1]+=f[y][1],g[x][1]+=g[y][1];
  }
}

inline void solve(int ans1=0,int ans2=0){
  n=gi();m=gi();cnt=tot=0;
  memset(head,0,sizeof(head));
  memset(vis,0,sizeof(vis));
  for(int i=1;i<=m;++i){
    int u=gi()+1,v=gi()+1;
    link(u,v);link(v,u);
  }
  for(int i=1;i<=n;++i)
    if(!vis[i])dfs(i,root[++cnt]=i);
  for(int i=1;i<=cnt;++i){
    int x=root[i];
    if(f[x][0]==f[x][1])ans1+=f[x][0],ans2+=min(g[x][0],g[x][1]);
    else if(f[x][0]<f[x][1])ans1+=f[x][0],ans2+=g[x][0];
    else ans1+=f[x][1],ans2+=g[x][1];
  }
  printf("%d %d %d
",ans1,m-ans2,ans2);
}

int main()
{
  int Case=gi();while(Case--)solve();
  fclose(stdin);fclose(stdout);
  return 0;
}

#include    <iostream>
#include    <cstdio>
#include    <cstdlib>
#include    <algorithm>
#include    <vector>
#include    <cstring>
#include    <queue>
#include    <complex>
#include    <stack>
#define LL long long int
#define dob double
#define FILE "10859"
using namespace std;

const int N = 2010;
struct Node{int to,next;}E[N];
int n,m,head[N],tot,cnt,f[N][2],vis[N],root[N];

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*10+ch-48,ch=getchar();
  return x*res;
}

inline void link(int u,int v){
  E[++tot]=(Node){v,head[u]};
  head[u]=tot;
}

inline void dfs(int x){
  f[x][0]=0;f[x][1]=N;vis[x]=1;
  for(int e=head[x];e;e=E[e].next){
    int y=E[e].to;if(vis[y])continue;dfs(y);
    f[x][0]+=f[y][1]+1;
    if(f[y][1]>f[y][0])
      f[x][1]+=f[y][0]+1;
    else f[x][1]+=f[y][1];
  }
}

inline void solve(int ans=0){
  n=gi();m=gi();tot=0;
  memset(head,0,sizeof(head));
  memset(vis,0,sizeof(vis));
  for(int i=1;i<=m;++i){
    int u=gi()+1,v=gi()+1;
    link(u,v);link(v,u);
  }
  for(int i=1;i<=n;++i)
    if(!vis[i])dfs(i),ans+=min(f[i][0],f[i][1]);
  printf("%d %d %d
",ans/N,m-ans%N,ans%N);
}

int main(){
  int Case=gi();while(Case--)solve();
  fclose(stdin);fclose(stdout);
  return 0;
}