自动搬运

查看原文

来自洛谷，原作者为

	ShineEternal **

搬运于2025-08-24 22:05:56，当前版本为作者最后更新于2018-11-17 08:47:23，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

为了让大家看起来方便，于是验题人就把题解放进来了，相关题目请点击这里

T4

题意较为复杂，详见题面。

本题操作较多，前面的测试点基本上都分别对应一个操作，因此我们逐个测试点分析。

$1$：没什么好说的……

$2$：最暴力的方法也能过，也没什么好说的。

$4$：这个也很简单，直接跑一遍最长路即可，当然裸$dijkstra$是过不了的，需要加堆优化；

由于出题人的数据生成器比较水，生成个数据都要几分钟，所以很良心地没有卡$spfa$。

$3$：这一测试点边权为0，那就省去了最长路了；

如何判断图的连通性？顺着去枚举并每次判断连通性，显然会超时；

这里标程用了笨办法：分块二分；由于删除的边不超过1000条，最多只会把操作分成1000个部分，每一部分操作都是添加边，显然有单调性！

顺着枚举每一部分的操作，在处理每个部分时二分判断连通性，可以减少判断的次数，优化操作时间。

至于删除操作，我用了树状数组+二分，树状数组存前缀和，即它是第几条边，然后二分它在原数组的标号即可。

$5-6$：经过上面一番分析大家大概也有整体思路了：先分块二分判连通性，再求最长路。

这里无消失的边，那么省去了分块与删除操作，其它与上面方法一样。

$7-8$：这里也是非常简单的，由于删除边对生成连通图没有贡献，所以操作同$4$。

$9-10$：其实就是测试点$3$+测试点$4$，用$3$的方法判断连通性后求个最长路即可。

可见，本题中其实大部分分都可以水的，而要AC，解决测试点$3$是关键。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
    struct newdata
    {
        int tm,type,u,v,w,k;
    };
    struct forward_star 
    {
        int next,to,w;
    };
    int n,m,t,cnt,tot;
    forward_star edge[1100001];
    newdata work[100001];
    int head[100001];
    int heap[100001];
    int que[100001];
    int ref[100001];
    int tree[1100001];
    int dist[100001];
    bool usable[1100001];
    bool vis[100001];
void add(int u,int v,int w)
{
    cnt++;
    edge[cnt].to=v;
    edge[cnt].w=w;
    edge[cnt].next=head[u];
    head[u]=cnt;
}
void adjust_up(int now)
{
    if (now>1&&dist[heap[now]]>dist[heap[now/2]])
    {
        ref[heap[now]]=now/2;
        ref[heap[now/2]]=now;
        swap(heap[now],heap[now/2]);
        adjust_up(now/2);
    }
}
void adjust_down(int now)
{
    if (now*2+1<=tot)
    {
        int k;
        if (dist[heap[now*2+1]]>dist[heap[now*2]]) k=now*2+1; else k=now*2;
        if (dist[heap[k]]>dist[heap[now]])
        {
            ref[heap[k]]=now;
            ref[heap[now]]=k;
            swap(heap[k],heap[now]);
            adjust_down(k);
        }
    }
    else if (now*2<=tot)
    {
        if (dist[heap[now*2]]>dist[heap[now]])
        {
            ref[heap[now]]=now*2;
            ref[heap[now*2]]=now;
            swap(heap[now],heap[now*2]);
            adjust_down(now*2);
        }
    }
}
void addheap(int now)
{
    heap[++tot]=now;
    ref[now]=tot;
    adjust_up(tot);
}
void pushheap()
{
    heap[1]=heap[tot];
    ref[heap[1]]=1;
    tot--;
    adjust_down(1);
}
void dijkstra_heap(int u)
{
    memset(vis,false,sizeof(vis));
    memset(dist,255,sizeof(dist));
    dist[u]=0;
    vis[u]=true;
    addheap(u);
    while (tot!=0)
    {
        int now=heap[1];
        pushheap();
        int i=head[now];
        while (i!=0)
        {
            if (usable[i]&&i<=cnt)
                if (dist[now]+edge[i].w>dist[edge[i].to])
                {
                    dist[edge[i].to]=dist[now]+edge[i].w;
                    if (!vis[edge[i].to])
                    {
                        vis[edge[i].to]=true;
                        addheap(edge[i].to);
                    } else adjust_up(ref[edge[i].to]);
                }
            i=edge[i].next;
        }
    }
}
bool cmp(newdata i,newdata j)
{
    return i.tm<j.tm;
}
bool check(int u,int v)
{
    memset(vis,false,sizeof(vis));
    int top=1;
    que[top]=u;
    vis[u]=true; 
    while (top>0)
    {
        int now=que[top];
        top--;
        int i=head[now];
        while (i!=0)
        {
            if (i<=cnt&&usable[i])
                if (!vis[edge[i].to])
                {
                    if (edge[i].to==v) return true;
                    vis[edge[i].to]=true;
                    que[++top]=edge[i].to;
                }
            i=edge[i].next;
        }
    }
    return false;
}
void adjust(int now)
{
    int i=now;
    while (i>0)
    {
        i-=i&i;
        tree[now]+=tree[i];
    }
    tree[now]++;
}
int sum(int now)
{
    int tot=0;
    int i=now;
    while (i>0)
    {
        tot+=tree[i];
        i-=i&i;
    }
    return tot;
}
int solve(int now)
{
    int l=1;
    int r=cnt;
    while (l<r)
    {
        int mid=(l+r)>>1;
        if (sum(mid)<now)
            l=mid+1;
        else r=mid-1;
    }
    tree[l]--;
    return l;
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++)
    {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);
        adjust(i);
    }
    memset(usable,true,sizeof(usable));
    scanf("%d",&t);
    if (t==0)
    {
        dijkstra_heap(1);
        if (dist[n]==-1)
            printf("Continue from the last checkpoint");
        else
        {
            printf("0\n");
            printf("%d",dist[n]);
        }
        return 0;
    }
    else
    {
        bool occur=false;
        bool disappear=false;
        for (int i=1;i<=t;i++)
        {
            scanf("%d%d",&work[i].tm,&work[i].type);
            if (work[i].type==0)
            { 
                scanf("%d%d%d",&work[i].u,&work[i].v,&work[i].w);
                occur=true;
            }
            else 
            {
                scanf("%d",&work[i].k);
                disappear=true;
            }
        }
        if (disappear&&!occur)
        {
            dijkstra_heap(1);
            if (dist[n]==-1)
                printf("Continue from the last checkpoint");
            else
            {
                printf("0\n");
                printf("%d",dist[n]);
            }
            return 0;
        }
        sort(work+1,work+t+1,cmp);
        if (check(1,n))
        {
            printf("0\n");
            dijkstra_heap(1);
            printf("%d",dist[n]);
            return 0;
        }
        int l=1;
        for (int i=1;i<=t;i++)
            if (work[i].type==1)
            {
                int r=i-1;
                if (l>=r)
                {
                    usable[solve(work[i].k)]=false;
                    l=i+1;
                    continue;
                }
                int cnt_first=cnt;
                int l_first=l;
                for (int j=l;j<=r;j++)
                {
                    add(work[j].u,work[j].v,work[j].w);
                    adjust(cnt);
                }
                while (l<r-1)
                {
                    int mid=(l+r)>>1;
                    cnt=cnt_first+mid-l_first+1;
                    if (check(1,n))
                        r=mid;
                    else l=mid;
                }
                cnt=cnt_first+l-l_first+1;
                if (check(1,n))
                {
                    printf("%d\n",work[l].tm);
                    dijkstra_heap(1);
                    printf("%d",dist[n]);
                    return 0;
                }
                cnt=cnt_first+r-l_first+1;
                if (check(1,n))
                {
                    printf("%d\n",work[r].tm);
                    dijkstra_heap(1);
                    printf("%d",dist[n]);
                    return 0;
                }
                cnt=cnt_first+i-l_first+1;
                usable[solve(work[i].k)]=false;
                l=i+1;
            }
        int r=t;
        int cnt_first=cnt;
        int l_first=l;
        for (int j=l;j<=r;j++)
        {
            add(work[j].u,work[j].v,work[j].w);
            adjust(cnt);
        }
        while (l<r-1)
        {
            int mid=(l+r)>>1;
            cnt=cnt_first+mid-l_first+1;
            if (check(1,n))
                r=mid;
            else l=mid;
        }
        cnt=cnt_first+l-l_first+1;
        if (check(1,n))
        {
            printf("%d\n",work[l].tm);
            dijkstra_heap(1);
            printf("%d",dist[n]);
            return 0;
        }
        cnt=cnt_first+r-l_first+1;
        if (check(1,n))
        {
            printf("%d\n",work[r].tm);
            dijkstra_heap(1);
            printf("%d",dist[n]);
            return 0;
        }
        printf("Continue from the last checkpoint");
        return 0;
    }
    return 0;
}