5 条题解
-
0
// 外向基环树 树形DP O(n) #include<bits/stdc++.h> using namespace std; #define int long long const int N=1000010; int n,w[N]; vector<int> e[N]; int r1,r2,vis[N],f[N][2],sum; void dfs(int u,int rt){ vis[u]=1; for(int v:e[u]){ if(v==rt){r1=u,r2=v;return;} if(!vis[v]) dfs(v,rt); } } int DP(int u,int rt){ f[u][0]=0; f[u][1]=w[u]; for(int v:e[u])if(v!=rt){ DP(v,rt); f[u][0]+=max(f[v][0],f[v][1]); f[u][1]+=f[v][0]; } return f[u][0]; //保证r1,r2不会同时选 } signed main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin>>n; for(int i=1,j;i<=n;i++){ cin>>w[i]>>j; e[j].push_back(i); //多人厌恶j，建成外向基环树 } for(int i=1;i<=n;i++){ if(!vis[i]){ r1=r2=0; dfs(i,i); if(r1) sum+=max(DP(r1,r1),DP(r2,r2)); } } cout<<sum; } -
0
#include<bits/stdc++.h> using namespace std; typedef long long LL; const int N = 1e6 + 10; struct node { int x, y; }; LL w[N]; vector<int> G[N]; vector<node> roots; int fa[N]; LL f[N][2]; int findfa(int x) { if (fa[x] == x) { return x; } return fa[x] = findfa(fa[x]); } LL dfs(int x, int fa) { f[x][1] = w[x]; f[x][0] = 0; for (int y : G[x]) if (y != fa) { LL t = dfs(y, x); f[x][0] += max(f[y][0], f[y][1]); f[x][1] += f[y][0]; } return f[x][0]; } int main () { ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; for (int i = 1; i <= n; i ++) { fa[i] = i; } for (int i = 1; i <= n; i ++) { int x; cin >> w[i] >> x; int tx = findfa(x), ty = findfa(i); if(tx != ty) { fa[tx] = ty; G[i].push_back(x); G[x].push_back(i); } else { roots.push_back({x, i}); } } LL ans = 0; memset(f, 0, sizeof(f)); for (node i : roots) { ans += max(dfs(i.x, 0), dfs(i.y, 0)); } cout << ans << "\n"; return 0; } -
0
huangzheng
LV 6
@ 2025-10-8 17:02:45
20250104:
#include<bits/stdc++.h> using namespace std; const int N=1e6+10; vector<pair<int, int>> G[N]; int tsp, dfn[N], low[N]; int fa[N]; long long w[N], f[N][2], ff[N][2]; void dp(int x, int y) { int cnt; cnt=0; for(int i=y; i!=fa[x]; i=fa[i]){ cnt++; ff[cnt][0]=f[i][0]; ff[cnt][1]=f[i][1]; } for(int i=2; i<=cnt; i++){ ff[i][0]+=max(ff[i-1][0], ff[i-1][1]); ff[i][1]+=ff[i-1][0]; } f[x][0]=ff[cnt][0]; cnt=0; for(int i=y; i!=fa[x]; i=fa[i]){ cnt++; ff[cnt][0]=f[i][0]; ff[cnt][1]=f[i][1]; } ff[1][1]=-0x3f3f3f3f3f3f3f3fll; for(int i=2; i<=cnt; i++){ ff[i][0]+=max(ff[i-1][0], ff[i-1][1]); ff[i][1]+=ff[i-1][0]; } f[x][1]=ff[cnt][1]; } void tarjan(int x, int in_id) { dfn[x]=low[x]=++tsp; f[x][1]=w[x]; f[x][0]=0; for(auto i:G[x])if(i.second!=in_id){ int y=i.first, id=i.second; if(!dfn[y]){ fa[y]=x; tarjan(y, id); low[x]=min(low[x], low[y]); }else{ low[x]=min(low[x], dfn[y]); } if(dfn[x]<low[y]){ f[x][1]+=f[y][0]; f[x][0]+=max(f[y][0], f[y][1]); } } for(auto i:G[x])if(i.second!=in_id){ int y=i.first; if(fa[y]!=x&&dfn[x]<dfn[y]){ dp(x, y); } } } int main() { int n;scanf("%d", &n); map<pair<int, int>, bool> mp; for(int i=1, x, y; i<=n; i++){ scanf("%lld%d", &w[i], &x); y=i;if(x>y)swap(x,y); if(mp[{x,y}]==0){ G[x].push_back({y,i}); G[y].push_back({x,i}); mp[{x,y}]=1; } } tsp=0;memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low)); long long ans=0; for(int i=1; i<=n; i++)if(dfn[i]==0)tarjan(i,0),ans+=max(f[i][0],f[i][1]); printf("%lld", ans); return 0; }旧代码：
#include<bits/stdc++.h> using namespace std; typedef long long LL; const int N=1e6+10; vector<int> G[N]; LL w[N], f[N][2]; int fa[N]; int findfa(int x){ return (fa[x]==x)?fa[x]:fa[x]=findfa(fa[x]);} void dfs(int x, int ff){ f[x][1]=w[x];f[x][0]=0; for(int y:G[x]) if(y!=ff){ dfs(y, x); f[x][0]+=max(f[y][1],f[y][0]); f[x][1]+=f[y][0]; } } vector<pair<int, int>> roots; int main() { int n;scanf("%d", &n); for(int i=1; i<=n; i++) fa[i]=i; for(int i=1, x; i<=n; i++){ scanf("%lld%d", &w[i], &x); int fx=findfa(i), fy=findfa(x); if(fx==fy) roots.push_back({x,i}); else{ fa[fx]=fy; G[i].emplace_back(x); G[x].emplace_back(i); } } LL ans=0; for(auto t:roots){ int x=t.first, y=t.second; dfs(x,0);LL tx=f[x][0]; dfs(y,0);LL ty=f[y][0]; ans+=max(tx,ty); } printf("%lld\n", ans); return 0; } -
0
huangzheng
LV 6
@ 2025-10-8 17:02:11
20250104:
#include<bits/stdc++.h> using namespace std; const int N=1e6+10; vector<pair<int,int>>G[N]; int tsp,dfn[N],low[N]; int fa[N]; long long w[N],f[N][2],ff[N][2]; void dp(int x,int y) { int cnt; cnt=0; for(int i=y;i!=fa[x];i=fa[i]){cnt++;ff[cnt][0]=f[i][0];ff[cnt][1]=f[i][1];} for(int i=2;i<=cnt;i++) { ff[i][0]+=max(ff[i-1][0],ff[i-1][1]); ff[i][1]+=ff[i-1][0]; } f[x][0]=ff[cnt][0]; cnt=0; for(int i=y;i!=fa[x];i=fa[i]){cnt++;ff[cnt][0]=f[i][0];ff[cnt][1]=f[i][1];} ff[1][1]=-0x3f3f3f3f3f3f3f3fll;//相当于选y点的状态是坏的，不会被后来的状态所继承 for(int i=2;i<=cnt;i++) { ff[i][0]+=max(ff[i-1][0],ff[i-1][1]); ff[i][1]+=ff[i-1][0]; } f[x][1]=ff[cnt][1]; } void tarjan(int x,int in_id) { dfn[x]=low[x]=++tsp; f[x][1]=w[x],f[x][0]=0; for(auto i:G[x])if(i.second!=in_id) { int y=i.first,id=i.second; if(!dfn[y]) { fa[y]=x; tarjan(y,id); low[x]=min(low[x],low[y]); } else low[x]=min(low[x],dfn[y]); if(dfn[x]<low[y]) { f[x][1]+=f[y][0]; f[x][0]+=max(f[y][0],f[y][1]); } } for(auto i:G[x])if(i.second!=in_id) { int y=i.first; if(fa[y]!=x&&dfn[x]<dfn[y]) { dp(x,y); } } } int main() { int n;scanf("%d",&n); map< pair<int,int>,bool >mp; for(int i=1,x,y;i<=n;i++) { scanf("%lld%d",&w[i],&x); y=i;if(x>y)swap(x,y); if(mp[{x,y}]==0) { G[x].push_back({y,i}); G[y].push_back({x,i}); mp[{x,y}]=1; } } tsp=0;memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low)); long long ans=0; for(int i=1;i<=n;i++)if(dfn[i]==0)tarjan(i,0),ans+=max(f[i][0],f[i][1]); printf("%lld",ans); return 0; }
旧代码：
#include<bits/stdc++.h> using namespace std; typedef long long LL; const int N=1e6+10; vector<int>G[N]; LL w[N],f[N][2]; int fa[N]; int findfa(int x){ return (fa[x]x)?fa[x]:fa[x]=findfa(fa[x]);} void dfs(int x,int ff) { f[x][1]=w[x];f[x][0]=0; for(int y:G[x]) if(y!=ff) { dfs(y,x); f[x][0]+=max(f[y][1],f[y][0]); f[x][1]+=f[y][0]; } } vector< pair<int,int> >roots; int main() { int n;scanf("%d",&n); for(int i=1;i<=n;i++) fa[i]=i; for(int i=1,x;i<=n;i++) { scanf("%lld%d",&w[i],&x); int fx=findfa(i),fy=findfa(x); if(fxfy) roots.push_back({x,i}); else { fa[fx]=fy; G[i].emplace_back(x); G[x].emplace_back(i); } } LL ans=0; for(auto t:roots)//auto就是自动变量,会自动推断后面的变量类型，创建时必须初始化 { int x=t.first,y=t.second; dfs(x,0);LL tx=f[x][0]; dfs(y,0);LL ty=f[y][0]; ans+=max(tx,ty); } printf("%lld\n",ans); return 0; }
- 1
