10.11-16的模拟赛

时间：2010-11-16 来源：LitIce

【问题描述】

有n个炸弹，有些炸弹牵了一根单向引线（也就是说引线只有在这一端能被炸弹点燃），只要引爆了这个炸弹，用引线连接的下一个炸弹也会爆炸。每个炸弹还有个得分，当这个炸弹被引爆后就能得到相应得分。

现在要你引爆k个炸弹，使得分最大。

【输入格式】

第1行两个整数n、k。

接下来n行每行两个整数a[i]、b[i]。a[i]表示这个炸弹用引线连接的下一个炸弹，如果a[i]为0，则表示这个炸弹没连接引线。b[i]表示这个炸弹的得分。

【输出格式】

　　仅一个数，表示最大得分。

【输入样例】bomb.in

8 2

0 1

1 1

2 100

0 1

5 1

6 2

【输出样例】bomb.out

202

【数据规模】

1≤b[i]≤1000000

对于30%的数据，n≤1000 k≤30

对于60%的数据，n≤50000 k≤100

对于100%的数据，n≤200000 k≤500

--------------------------------------------------------------------------------------------

考试的时候没想出来T T。

Algorithm：

先缩环成点，这样就变成了一棵树。（题目特殊可以dfs缩点，代码里还是打了tarjan）

贪心取出一条最大链，删掉后再重复这个过程。（不用真的删除只要Dp时处理一下就可以了）

最后排序所有取出的链，排序取前m大。

代码

  1 #include<iostream>
  2 #include<cstdio>
  3  #define N 300001
  4  #define LL long long
  5 using namespace std;
  6 struct node{
  7        LL y,next;
  8        } E[N];
  9 
 10 LL DFN[N],Low[N],S[N],inS[N],col,color[N],edg[N],f[N];
 11 LL index,Ecnt,n,m,x;
 12 LL a[N],c[N],b[N],aa[N],cc,bo[N],cnt,vis[N],root,ans;
 13 void add_edge(LL x,LL y)
 14 {
 15      ++Ecnt;E[Ecnt].y=y;E[Ecnt].next=edg[x];edg[x]=Ecnt;
 16 }
 17 void tarjan(LL u)
 18 {
 19      DFN[u]=Low[u]=++index;S[++cnt]=u;inS[u]=1;
 20      
 21      LL v;
 22      for (LL j=edg[u];j!=0;j=E[j].next)
 23      {
 24          v=E[j].y;
 25          if (DFN[v]==0) 
 26          {
 27                         tarjan(v);
 28                         if (Low[v]<Low[u]) Low[u]=Low[v];
 29             
 30          }
 31          else
 32          if (inS[v]==1 && Low[v]<Low[u]) Low[u]=Low[v];
 33      }
 34      
 35      if (DFN[u]==Low[u])
 36      {
 37         ++col;
 38         while (cnt>0 && Low[S[cnt]]==DFN[u])
 39         {
 40               color[S[cnt]]=col;
 41               --cnt;
 42         }
 43      }
 44 }
 45 LL dp(LL u)
 46 {
 47     if (bo[u]) return f[u];
 48     bo[u]=1;
 49     
 50     LL v,Big=0,bi;
 51     for (LL j=edg[u];j!=0;j=E[j].next)
 52     {
 53         v=E[j].y;
 54         if (dp(v)>Big) Big=dp(v),bi=v;
 55     }
 56     f[u]=Big+b[u];
 57     for (LL j=edg[u];j!=0;j=E[j].next)
 58     {
 59         if (E[j].y!=bi) vis[E[j].y]=1;
 60     }
 61     return f[u];
 62 }
 63 int main()
 64 {
 65     freopen("bomb.in","r",stdin);
 66     freopen("bomb.out","w",stdout);
 67     scanf("%d%d",&n,&m);
 68     for (LL i=1;i<=n;++i)
 69     {
 70         scanf("%d%d",&x,&c[i]);
 71         a[i]=x;
 72         add_edge(x,i);
 73     }
 74     for (LL i=0;i<=n;++i) 
 75     if (DFN[i]==0) tarjan(i);
 76   //  for (LL i=0;i<=n;++i)
 77    // printf("%d %d\n",i,color[i]);
 78     Ecnt=0;for (LL i=1;i<=col;++i) edg[i]=0;
 79     
 80     for (LL i=1;i<=n;++i)
 81     if (color[a[i]]!=color[i])
 82         add_edge(color[a[i]],color[i]);
 83   
 84     for (LL i=1;i<=n;++i) 
 85         b[color[i]]+=c[i];
 86         
 87         root=color[0];
 88         
 89     for (LL i=1;i<=col;++i) bo[i]=0;
 90     vis[root]=1;
 91     dp(root);
 92     
 93     cc=0;
 94     for (LL i=1;i<=col;++i) if (vis[i])
 95     {
 96         ++cc;
 97         aa[cc]=f[i];
 98     }
 99     sort(aa+1,aa+cc);
100     while (cc>0 && m>0)
101     {
102           ans+=aa[cc];
103           --cc;--m;
104     }
105     cout<<ans<<endl;
106     return 0;
107 }
108