题目
UVa 10859 Placing Lampposts
题解
先读清楚题是覆盖边,和最大独立集是有区别的,然后无向无环就是森林!然后,,这题是看了题解的,感觉也不是比较难_ (:зゝ∠) _但是又不是很容易想出来,dp[i][0]表示父节点没放灯,然后应该就懂了。还有就是根节点的父亲是不能放的所以要+dp[root][0]
代码
#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;
}
转载请注明原文地址: https://ju.6miu.com/read-1000282.html