洛谷 P3627 [APIO2009]抢掠计划

这题一看就是缩点，但是缩完点怎么办呢？首先我们把所有的包含酒吧的缩点找出来，打上标记，然后建立一张新图，

每个缩点上的点权就是他所包含的所有点的点权和。但是建图的时候要注意，每一对缩点之间可能有多条边，所以我们可以先把重边去除一下，在建立新图，具体操作如下：

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

     {

         if(vis[i]==) continue;

         for(int j=last[i];j;j=g[j].next)

         {

             int v=g[j].to;

             if(g[i].co!=g[v].co&&vis[v]==)

             {

                 e[++cnt].a=g[i].co;

                 e[cnt].b=g[v].co;

             }

         }

     }

     sort(e+,e+cnt+,cmp);

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

     {

         if(e[i].a!=e[i-].a||e[i].b!=e[i-].b)

         {

             add1(e[i].a,e[i].b);

         }

     }

具体思路就是先枚举所有点和所有边，如果两个点不属于同一个强联通分量，那么就用e来把边存一下，然后对e进行排序

，去重，再建图。

建完图之后就好办了，可以跑spfa单源最长路，也可以dp，因为最后一定会终止在酒吧，所以就取所有打过标记的节点的最大值就好了。

最后附上代码：

 #include<iostream>

 #include<cmath>

 #include<cstdio>

 #include<string>

 #include<cstring>

 #include<algorithm>

 #define maxn 500005

 using namespace std;

 struct edge

 {

     int next;

     int to;

     int co;

 }g[maxn];

 struct edge1

 {

     int next;

     int to;

 }g1[maxn];

 struct edhe

 {

     int a,b;

 }e[maxn];

 inline int read()

 {

     char c=getchar();

     int res=,x=;

     while(c<''||c>'')

     {

         if(c=='-')

         x=-;

         c=getchar();

     }

     while(c>=''&&c<='')

     {

         res=res*+(c-'');

         c=getchar();

     }

     return x*res;

 }

 int n,m,aa,bb,num,s,p,tot,top,col,num1,ans,ae,cnt;

 int last[maxn],a[maxn],b[maxn],dfn[maxn],st[maxn],low[maxn];

 int shu[maxn],d[maxn],last1[maxn],sum[maxn],vis[maxn];

 inline void add(int from,int to)

 {

     g[++num].next=last[from];

     g[num].to=to;

     last[from]=num;

 }

 inline void add1(int from,int to)

 {

     g1[++num1].next=last1[from];

     g1[num1].to=to;

     last1[from]=num1;

 }

 inline void tarjan(int u)

 {

     low[u]=dfn[u]=++tot;

     st[++top]=u;

     for(int i=last[u];i;i=g[i].next)

     {

         int v=g[i].to;

         if(!dfn[v])

         {

             tarjan(v);

             if(low[v]<low[u])

             low[u]=low[v];

         }

         else if(!g[v].co)

         {

             if(dfn[v]<low[u])

             low[u]=dfn[v];

         }

     }

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

     {

         g[u].co=++col;

         while(st[top]!=u)

         {

             g[st[top]].co=col;

             top--;

         }

         top--;

     }

 }

 void dfs(int x)

 {

     for(int i=last1[x];i;i=g1[i].next)

     {

         int v=g1[i].to;

         if(sum[x]+shu[v]>sum[v])

         {

             sum[v]=sum[x]+shu[v];

             dfs(v);

         }

     }

 }

 bool cmp(edhe a,edhe b)

 {

     if(a.a==b.a)

     {

         return a.b<b.b;

     }

     else return a.a<b.a;

 }

 int main()

 {

     n=read();

     m=read();

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

     {

         aa=read();bb=read();

         add(aa,bb);

     }

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

     {

         a[i]=read();

     }

     s=read();p=read();

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

     {

         aa=read();

         b[aa]=;

     }

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

     {

         if(!dfn[i])

         tarjan(i);

     }

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

     {

         shu[g[i].co]+=a[i];

         if(b[i]==)

         {

             d[g[i].co]=;

         }

     }

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

     {

         if(vis[i]==) continue;

         for(int j=last[i];j;j=g[j].next)

         {

             int v=g[j].to;

             if(g[i].co!=g[v].co)

             {

                 e[++cnt].a=g[i].co;

                 e[cnt].b=g[v].co;

             }

         }

     }

     sort(e+,e+cnt+,cmp);

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

     {

         if(e[i].a!=e[i-].a||e[i].b!=e[i-].b)

         {

             add1(e[i].a,e[i].b);

         }

     }

     sum[g[s].co]=shu[g[s].co];

     dfs(g[s].co);

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

     {

         if(d[i]==)

         {

             if(ans<sum[i])

             ans=sum[i];

         }

     }

     printf("%d",ans);

     return ;

 }

巴特西

洛谷 P3627 [APIO2009]抢掠计划

最新文章

热门文章