首页 > > 程序设计 > C/C++ >

2019年7月训练（壹）

2019-08-16 07:53:15来源：博客园阅读 ()

2019年7月训练（壹）

2019-07-25

luogu P3627 [APIO2009]抢掠计划

卡了三个小时，看了题解才作出来的（菜）

前驱知识：

壹~邻接表存储/遍历

贰~SPFA跑最长路（<改>就行了）

叄~Tarjan缩点

壹.邻接表储存

两个，add存无边权，未缩点；build有边权，已缩点。

void add(int u,int v)
 {
    cnt++;
    e[cnt].to=v;
    e[cnt].next=head[u];
    head[u]=cnt;
 }

 void build(int u,int v,int w)
 {
    cnt++;
    e[cnt].to=v;
    e[cnt].val=w;
    e[cnt].next=head[u];
    head[u]=cnt;
 }

贰.输入

懒得开两个head数组了，所以memset了。

cnt记得重置为零。

　　 cnt=0;
    memset(e,0,sizeof(e));
    memset(head,0,sizeof(head));
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&u[i],&v[i]);
        add(u[i],v[i]);
    }
    for(int i=1;i<=n;i++) scanf("%d",&w[i]);
    scanf("%d%d",&s,&p);
    for(int i=1;i<=p;i++) scanf("%d",&bar[i]);

叄.tarjan 缩点

 void Tarjan(int x)
 {
    dfn[x]=low[x]=++total;
    stk[++top]=x;vis[x]=true;
    for(int i=head[x];i;i=e[i].next)
    {
        int t=e[i].to;
        if(!dfn[t])
        {
            Tarjan(t);
            low[x]=min(low[x],low[t]);
        }
        else if(vis[t])
         low[x]=min(low[x],dfn[t]);
    }
    if(dfn[x]==low[x])
    {
        tot++;
        do{
            int tp=stk[top];
            sum[tot]+=w[tp];
            vis[tp]=false;
            be[tp]=tot;
        }while(stk[top--]!=x);
    }//数组模拟栈
 }

这里我是用的数组模拟栈，首先int tp=stk[top]取出栈顶

sum表示缩完点后这个点的点权
不是很懂Tarjan的好好理解下Tarjan弹栈的部分再看这里就懂了
懂Tarjan的模拟一下应该就懂了，每次弹栈时，所有被弹出的点都是缩完点后的一个点
即sum[tot]+=w[tp]，缩完点后的点权+=原点权
很好理解吧
不懂的说明你对Tarjan还是理解不到位……这篇题解不是讲Tarjan的，楼下大佬应该有详细讲解。

然后vis[tp]=false表示tp已经出栈

g表示缩完点后每个点在哪个点中
即g[tp]=tot，tp这个点在缩完点后的第tot个点里
然后用栈顶和x比较，标准Tarjan操作

stk[top--]就相当于pop弹栈了

肆.Spfa跑最长路

 void Spfa(int s)
 {
    for(int i=1;i<=tot;i++) dis[i]=0;
    int bes=be[s];//不想认真想变量名了
    q.push(bes);
    vis[bes]=true;
    dis[bes]=sum[bes];
    while(!q.empty())
    {
        int h=q.front();q.pop();
        vis[h]=false;
        for(int i=head[h];i;i=e[i].next)
        {
            int t=e[i].to;
            if(dis[t]<dis[h]+e[i].val)
            {
                dis[t]=dis[h]+e[i].val;
                if(!vis[t])
                {
                    q.push(t);
                    vis[t]=true;
                }
            }
        }
    }
 }

起点边权解决方法：

起点从s变为be[s]了，dis[s]不是0了

因为缩点

我们刚刚build建的图是一张缩完点后的缩点图，所以我们push起点的时候当然是push缩完点后s所在的点啊

为什么呢？万一s本身就在一个环里，push（s)的话问题就大了

所以我们把起点一律改成g[s]来操作

并且，我们把起点的dis值直接加上点权，这样就不会漏掉起点点权了

而且放心，一开始更改dis值不会对后续松弛操作造成无法更改的影响，毕竟这是最长路

伍.main函数部分

 for(int i=1;i<=m;i++)
     if(be[u[i]]!=be[v[i]])
      build(be[u[i]],be[v[i]],sum[be[v[i]]]);

这时候前面的u，v数组便起作用了

我们通过判断u[i],v[i]是否在一个新点里，如果不在的话就build一条新边，这样就能建一个缩完点后的图

！！！build：起点是u[i]所在的缩点，终点是v[i]所在的缩点（如果u[i]和v[i]在一个缩点里就不会执行build了），边权是v[i]所在缩点的点权（sum）！！！

这样，这张新图就表明：从U走到V可以抢劫W的钱，钱数当然是缩点点权啊

但是-------------------------------------------------------------------------这样每次把边权设置为后头那个缩点的点权，前头那个点（起点）被忽略了，点权不就没用了吗？

对√的确有这个问题

但是在上一部分我们已经简单粗暴の解决了

以下为AC码：

#include<cstdio>
#include<cstring>
#include<stack>
#include<algorithm>
#include<queue>
#define maxn 500010
using namespace std;
struct edbee
{
    int to,val,next;
} e[maxn];
int m,n,p,s,cnt,be[maxn],u[maxn],v[maxn],w[maxn],head[maxn],bar[maxn],dis[maxn],dfn[maxn],low[maxn],stk[maxn],sum[maxn];
bool vis[maxn];
queue <int> q;
int ans,top,tot,total;

 void add(int u,int v)
 {
    cnt++;
    e[cnt].to=v;
    e[cnt].next=head[u];
    head[u]=cnt;
 }
 
 void build(int u,int v,int w)
 {
    cnt++;
    e[cnt].to=v;
    e[cnt].val=w;
    e[cnt].next=head[u];
    head[u]=cnt;
 }
 
 void Tarjan(int x)
 {
    dfn[x]=low[x]=++total;
    stk[++top]=x;vis[x]=true;
    for(int i=head[x];i;i=e[i].next)
    {
        int t=e[i].to;
        if(!dfn[t])
        {
            Tarjan(t);
            low[x]=min(low[x],low[t]);
        }
        else if(vis[t])
         low[x]=min(low[x],dfn[t]);
    }
    if(dfn[x]==low[x])
    {
        tot++;
        do{
            int tp=stk[top];
            sum[tot]+=w[tp];
            vis[tp]=false;
            be[tp]=tot;
        }while(stk[top--]!=x);
    }
 }
 
 void Spfa(int s)
 {
    for(int i=1;i<=tot;i++) dis[i]=0;
    int bes=be[s];
    q.push(bes);
    vis[bes]=true;
    dis[bes]=sum[bes];
    while(!q.empty())
    {
        int h=q.front();q.pop();
        vis[h]=false;
        for(int i=head[h];i;i=e[i].next)
        {
            int t=e[i].to;
            if(dis[t]<dis[h]+e[i].val)
            {
                dis[t]=dis[h]+e[i].val;
                if(!vis[t])
                {
                    q.push(t);
                    vis[t]=true;
                }
            }
        }
    }
 }
 
int main()
{
    cnt=0;
    memset(e,0,sizeof(e));
    memset(head,0,sizeof(head));
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&u[i],&v[i]);
        add(u[i],v[i]);
    }
    for(int i=1;i<=n;i++) scanf("%d",&w[i]);
    scanf("%d%d",&s,&p);
    for(int i=1;i<=p;i++) scanf("%d",&bar[i]);
    for(int i=1;i<=n;i++)
     if(!dfn[i]) Tarjan(i);
    cnt=0;
    memset(e,0,sizeof(e));
    memset(head,0,sizeof(head));
    for(int i=1;i<=m;i++)
     if(be[u[i]]!=be[v[i]])
      build(be[u[i]],be[v[i]],sum[be[v[i]]]);
    Spfa(s);
    for(int i=1;i<=p;i++)
     ans=max(ans,dis[be[bar[i]]]);
    printf("%d",ans);
    return 0;
}

谢谢你能看到这里。

2019-07-25 22:35:43

以下为私货，可以不看

↓