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; }