Java教程

P1453 城市环路

本文主要是介绍P1453 城市环路,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

P1453 城市环路

树形DP。

考虑到有环不太好处理,显然只能删除环上面的边。。。

一开始我想的是tarjan缩点判环,后面我还枚举了环上的任意一条边来断。。。其实这样就很没有必要,在一个环上随便断哪条边其实是无所谓的对吧。。。。

在输入的时候如果两个点在一个联通块里面再加一条边不就是环了吗。。。把这条边记录下来直接以 \(from\) 和 \(to\) 为 \(root\) 树形DP 就好了啊。。。

#include <bits/stdc++.h>
#define ll long long
#define maxn 100001
using namespace std;
ll n,p[maxn],u,v,w,root;
ll cnt=1,hd[maxn];
ll fa[maxn];
ll rto,rtt;
double k,ans,dp[maxn][3];
struct Node{
    ll nx,to,fm;
}e[maxn<<1];

inline ll read(){
    ll x=0,f=0;char c=getchar();
    while(!isdigit(c))  f|=c=='-',c=getchar();
    while(isdigit(c))   x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return f?-x:x;
}

inline void add(ll x,ll y){
    e[++cnt].to=y;
    e[cnt].fm=x;
    e[cnt].nx=hd[x];
    hd[x]=cnt;
}

inline ll find(ll x) { return (x==fa[x])?x:fa[x]=find(fa[x]); }

inline void work(ll x,ll fa){
    dp[x][1]=p[x]*k;
    dp[x][0]=0;
    for(register int i=hd[x];i;i=e[i].nx){
        ll to=e[i].to;
        if(to==fa)   continue;
        work(to,x);
        dp[x][0]+=max(dp[to][0],dp[to][1]);
        dp[x][1]+=dp[to][0];
    }
}

int main(){
    n=read();
    for(register int i=1;i<=n;++i)   p[i]=read(),fa[i]=i;
    for(register int i=0;i<n;++i){
        u=read();v=read();
        ++u;++v;
        if(find(u)==find(v)) { rto=u,rtt=v;continue; }
        add(u,v);
        add(v,u);
        fa[find(u)]=find(v);
    }
    cin>>k;
    work(rto,0);ans=dp[rto][0];
    work(rtt,0);ans=max(ans,dp[rtt][0]);
    cout<<fixed<<setprecision(1)<<ans;
    return 0;
}

呃呃呃,经过我漫长的调试,\(tarjan\) 也是可以的。。。

#include <bits/stdc++.h>
#define ll long long
#define maxn 100001
using namespace std;
ll n,p[maxn],u,v,w,root;
ll cnt=1,hd[maxn];
ll c[maxn],dfn[maxn],tim,low[maxn],stac[maxn],top;
ll vit[maxn],scc,num[maxn];
ll kut[maxn][3];
double k,ans,dp[maxn][3];
struct Node{
    ll nx,to,fm;
}e[maxn<<1];

inline ll read(){
    ll x=0,f=0;char c=getchar();
    while(!isdigit(c))  f|=c=='-',c=getchar();
    while(isdigit(c))   x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return f?-x:x;
}

inline void add(ll x,ll y){
    e[++cnt].to=y;
    e[cnt].fm=x;
    e[cnt].nx=hd[x];
    hd[x]=cnt;
}

inline void work(ll x,ll fa,ll no){
    dp[x][1]=p[x]*k;dp[x][0]=0;
    for(register int i=hd[x];i;i=e[i].nx){
        ll to=e[i].to;
        if(to==fa)   continue;
        if(vit[to])  continue;
        if(x==kut[root][no]&&to==kut[root][(((no-1)^1)+1)]) continue;
        if(to==kut[root][no]&&x==kut[root][(((no-1)^1)+1)]) continue;
        vit[to]=1;
        work(to,x,no);
        dp[x][0]+=max(dp[to][0],dp[to][1]);
        dp[x][1]+=dp[to][0];
    }
}

inline void tarjan(ll x,ll fa){
    stac[++top]=x;
    dfn[x]=low[x]=++tim;
    vit[x]=1;
    for(register int i=hd[x];i;i=e[i].nx){
        ll to=e[i].to;
        if(to==fa)  continue;
        if(!dfn[to]){
            tarjan(to,x);
            low[x]=min(low[x],low[to]);
        }
        else
            low[x]=min(low[x],dfn[to]);
        }
    if(dfn[x]==low[x]){
        ++scc;
        ll tp=0;
        while(tp!=x){
            tp=stac[top];
            stac[top]=0;
            --top;
            c[tp]=scc;
            if(kut[scc][0]<2)
                kut[scc][++kut[scc][0]]=tp;
            vit[tp]=0;
            ++num[scc];
        }
    }
}

int main(){
    n=read();
    for(register int i=1;i<=n;++i)   p[i]=read();
    for(register int i=0;i<n;++i){
        u=read();v=read();
        ++u;++v;
        add(u,v);
        add(v,u);
    }
    cin>>k;
    for(register int i=1;i<=n;++i)
        if(!dfn[i])
            tim=0,tarjan(i,0);
    for(register int i=1;i<=scc;++i)
        if(num[i]>1){
            root=i;
            break;
        }
    for(register int i=1;i<=n;++i)  vit[i]=0;
    work(kut[root][1],0,1);ans=dp[kut[root][1]][0];
    for(register int i=1;i<=n;++i)  vit[i]=0;
    work(kut[root][2],0,2);ans=max(ans,dp[kut[root][2]][0]);
    cout<<fixed<<setprecision(1)<<ans;
    return 0;
}
这篇关于P1453 城市环路的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!