UVa 10859 Placing Lampposts

题目

UVa 10859 Placing Lampposts

题解

先读清楚题是覆盖边，和最大独立集是有区别的，然后无向无环就是森林！然后，，这题是看了题解的，感觉也不是比较难_ (:зゝ∠) _但是又不是很容易想出来，dp[i][0]表示父节点没放灯，然后应该就懂了。还有就是根节点的父亲是不能放的所以要+dp[root][0]

代码

//QWsin
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int M=2000;
const int INF=(1<<30);
const int maxn=1000+10;
const int maxm=2000+10;int n,m;
struct Edge{
   int u,v;Edge(int u=0,int v=0):u(u),v(v){}}e[maxm];
int First[maxn],Next[maxm],ecnt;
inline void add_edge(int u,int v)
{Next[ecnt]=First[u];First[u]=ecnt;e[ecnt++]=Edge(u,v);Next[ecnt]=First[v];First[v]=ecnt;e[ecnt++]=Edge(v,u);
}int dp[maxn][2],vis[maxn];void dfs(int u,int pre,const int &root)
{vis[u]=1;int sigma0=0,sigma1=0;for(int i=First[u];i!=-1;i=Next[i])if(e[i].v!=pre){dfs(e[i].v,u,root);sigma0+=dp[e[i].v][0];sigma1+=dp[e[i].v][1];}dp[u][0]=sigma1+M+(u!=root);if(u==root) dp[u][0]=min(dp[u][0],sigma0);dp[u][1]=min(sigma0+(u!=root),sigma1+M);
}inline void solve()
{int n,m;cin>>n>>m;ecnt=0;memset(vis,0,sizeof vis);memset(First,-1,sizeof First);for(int i=1,u,v;i<=m;++i)scanf("%d%d",&u,&v),add_edge(++u,++v);int ans=0;for(int i=1;i<=n;++i)if(!vis[i]) dfs(i,i,i),ans+=dp[i][0];//根节点没有父节点不能放 printf("%d %d %d\n",ans/M,m-ans%M,ans%M);
}int main()
{freopen("std.in","r",stdin);int T;cin>>T;while(T--) solve();return 0;
}