LOJ 2737 「JOISC 2016 Day 3」电报 —

相连的关系形成若干环 / 内向基环树。如果不是只有一个环的话，就得断开一些边使得图变成若干链。边的边权是以它为出边的点的点权。

基环树的树的部分可以 DP 或者贪心，贪心就是只在分叉处断边。

对于每个环，先做出 f[ i ][ 0/1 ] 表示环上这个点不向下 / 向下延伸链的代价，然后在环上 DP 。

方法就是先指定 tot -> 1 的边不选， DP 一番，再制定 tot -> 1 的边选， DP 一番。

如果指定 tot -> 1 的边选，要注意不能连出一个环。所以不仅有 g[ i ][ 0/1 ] 表示 “可以向右延伸” / “无要求” ，还要有一个 [ 0/1 ] 表示 “之前有没有断过” 。不过不用有 g[ i ][ 1 ][ 1 ] ，因为 “无要求” 就是表示 i -> i+1 得断开，这样就一定 “断过” 了；所以就记 g[ i ][ 2 ] 表示 “之前断过，现在可以向右延伸” 。 g[ tot ][ 2 ] 就是指定 tot -> 1 的边选的时候加给答案的贡献。

#include<cstdio>

#include<cstring>

#include<algorithm>

#define ll long long

using namespace std;

int rdn()

{

  int ret=;bool fx=;char ch=getchar();

  while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}

  while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();

  return fx?ret:-ret;

}

ll Mn(ll a,ll b){return a<b?a:b;}

ll Mx(ll a,ll b){return a>b?a:b;}

const int N=1e5+; const ll INF=1e14+;

int n,hd[N],xnt,to[N<<],nxt[N<<],w[N<<],tp[N],tw[N],tot;

int cd[N],cnt,col[N],tim,dfn[N],low[N],sta[N],top;

ll ans,f[N][],g[N][]; bool vis[N],ins[N];

void add(int x,int y,int z)

{

  to[++xnt]=y;nxt[xnt]=hd[x];hd[x]=xnt;w[xnt]=z;cd[x]++;

}

void tarjan(int cr)

{

  dfn[cr]=low[cr]=++tim; sta[++top]=cr; ins[cr]=;

  for(int i=hd[cr],v;i;i=nxt[i])

    if(!dfn[v=to[i]])tarjan(v),low[cr]=Mn(low[cr],low[v]);

    else if(ins[v])low[cr]=Mn(low[cr],dfn[v]);

  if(dfn[cr]==low[cr])

    {

      cnt++; int siz=;

      do{

    ins[sta[top]]=; col[sta[top]]=cnt; siz++;

      }while(sta[top--]!=cr);

      if(siz==)col[cr]=, cnt--;

    }

}

void dfs(int cr)

{

  ins[cr]=;

  for(int i=hd[cr],v;i;i=nxt[i])

    if(!col[v=to[i]])

      {

    dfs(v=to[i]);

        ll t0=f[cr][]+f[v][]+w[i];

        ll t1=Mn(f[cr][]+f[v][],f[cr][]+f[v][]+w[i]);

    f[cr][]=t0; f[cr][]=t1;

      }

}

void ini_dfs(int cr,int st)

{

  dfs(cr); tp[++tot]=cr;

  for(int i=hd[cr],v;i;i=nxt[i])

    if(col[v=to[i]])

      {tw[tot]=w[i]; if(v!=st)ini_dfs(v,st);}

}

void solve(int cr)

{

  tot=; ini_dfs(cr,cr);

  g[][]=tw[tot]+f[tp[]][]; g[][]=tw[tot]+f[tp[]][];//f[tp[]]!!

  for(int i=;i<=tot;i++)

    {

      int cr=tp[i];//

      g[i][]=Mn(g[i-][],g[i-][]+tw[i-])+f[cr][];

      g[i][]=Mn(g[i-][],g[i-][]+tw[i-])+f[cr][];

    }

  ll ret=g[tot][];

  g[][]=f[tp[]][]; g[][]=f[tp[]][]; g[][]=g[][]=INF;

  for(int i=;i<=tot;i++)

    {

      int cr=tp[i];

      g[i][]=Mn(g[i-][],g[i-][]+tw[i-])+f[cr][];

      g[i][]=Mn(g[i-][],g[i-][]+tw[i-])+f[cr][];

      g[i][]=Mn(g[i-][],g[i-][]+tw[i-])+f[cr][];

    }

  ans+=Mn(ret,g[tot][]);

}

int main()

{

  n=rdn();

  for(int i=,d,z;i<=n;i++)

    { d=rdn(); z=rdn(); add(d,i,z);}

  bool fg=;for(int i=;i<=n;i++)if(cd[i]!=){fg=;break;}

  if(!fg)

    {

      int cr=;while(!vis[cr]){vis[cr]=;cr=to[hd[cr]];}

      for(int i=;i<=n;i++)if(!vis[i]){fg=;break;}

      if(!fg){puts("");return ;}

    }

  for(int i=;i<=n;i++)if(!dfn[i])tarjan(i);

  for(int i=;i<=n;i++)

    if(!ins[i]&&col[i])solve(i);

  printf("%lld\n",ans); return ;

}

巴特西

LOJ 2737 「JOISC 2016 Day 3」电报 ——思路+基环树DP

最新文章

热门文章