本文主要是介绍sicily 1225. 电子眼，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
/图其实是一个树加了一条边，我们找到这个环，然后枚举其中一条边的两端，看是在哪里安装电子眼。剩下的就是普通的树形dp了。。#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
const int MAXN = 101000;
vector<int> g[MAXN];
int p1,p2;准备删除的边
int dp0[MAXN],dp1[MAXN];///dp0[i]以i为根的子树在结点i不安装电子眼的最少数，dp1[i]在i安装
转移方程 dp1[i] = sigma(min(dp0[k],dp1[k])),dp0[i] = sigma(dp1[k]),k为i的后代
int visit[MAXN];
bool loca;///记录是否找到环的一个边
int mymin(int a,int b){
return a<b?a:b;
}
int f1(int n,int father);
int f0(int n,int father){
if(dp0[n]!=-1)return dp0[n];
dp0[n] = 0;
int i;
for(i = 0;i<g[n].size();i++){
if(g[n][i]==father)continue;
if((n==p1 && g[n][i]==p2) || (n==p2 && g[n][i]==p1))continue;
dp0[n]+=f1(g[n][i],n);
}
return dp0[n];
}
int f1(int n,int father){
if(dp1[n]!=-1)return dp1[n];
dp1[n] = 1;
int i;
for(i = 0;i<g[n].size();i++){
if(g[n][i]==father)continue;
if((n==p1 && g[n][i]==p2) || (n==p2 && g[n][i]==p1) )continue;
dp1[n]+=mymin(f1(g[n][i],n),f0(g[n][i],n));
}
return dp1[n];
}
int get(int n){
return f1(n,-1);
}
void dfs(int u,int father){/dfs找环的一条边
visit[u] = 1;
for(int i = 0;i<g[u].size() && !loca;i++){
if(g[u][i]==father)continue;
if(visit[g[u][i]]==true){
loca = true;
p1 = u;
p2 = g[u][i];
return ;
}
dfs(g[u][i],u);
}
}
int main()
{
int n;
scanf("%d",&n);
int u;
for(int i = 1;i<=n;i++){
scanf("%d",&u);
int v;
for(int j = 0;j<u;j++){
scanf("%d",&v);
g[i].push_back(v);
}
}
loca = false;
memset(visit,false,sizeof(visit));
dfs(1,-1);
memset(dp0,-1,sizeof(dp0));
memset(dp1,-1,sizeof(dp1));
int ans1 = get(p1);
memset(dp0,-1,sizeof(dp0));
memset(dp1,-1,sizeof(dp1));
int ans2 = get(p2);
printf("%d\n",ans1<ans2?ans1:ans2);
return 0;
}
这篇关于sicily 1225. 电子眼的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
