[BZOJ 4144] Petrol

Link:

BZOJ 4144 传送门

Solution:

一道不错的图论综合题

因为只询问关键点，因此重点是要求出关键点之间的最短路，以最短路建图

记$nst[i]$为离$i$最近的关键点：可以发现$A->B$的最短路径上，一定是前一半$nst[i]$为$A$，后一半$nst[i]$为$B$

否则设$nst[x]=C$，则$A->C->B$由于经过了$C$的加油一定不会更差

因此对于符合条件的$A->B$连边就建出了新图（如果离线的话仅修改权值不更改节点也可行）

接下来为了使连通的最大边最小跑$Kruskal$，此时分为两种方式：

Solution A：Offline

明显是更简单的解法，学会利用离线啊！

将$Query$按$b$从小到大排序

每次只连接$edge(u,v)  (w(u,v)<=b)$，最后判断$x,y$是否在一个点集中即可

Solution B：Online

如果要强制在线也可以做，而且算常用套路

先跑$Kruskal$，将图转化为了树，每次询问在树上倍增查找

Code:

#include<bits/stdc++.h>

using namespace std;

typedef pair<int,int> P;

const int MAXN=2e5+;

struct data{int x,y,w;}edge[MAXN];

struct E{int to,nxt,w;}e[MAXN<<];

priority_queue<P,vector<P>,greater<P> > pq;

int belong[MAXN],f[MAXN][],mx[MAXN][],dep[MAXN],nst[MAXN],cnt=;

int n,m,s,q,tot,head[MAXN],pos[MAXN],dist[MAXN],res[MAXN],vis[MAXN],fa[MAXN];

void add_edge(int from,int to,int cost)

{

    e[++tot].nxt=head[from];e[tot].w=cost;e[tot].to=to;head[from]=tot;

    e[++tot].nxt=head[to];e[tot].w=cost;e[tot].to=from;head[to]=tot;

}

int find(int x){return (fa[x]==x)?x:(fa[x]=find(fa[x]));}

bool cmp(data a,data b){return a.w<b.w;}

void dijkstra()

{

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

        dist[pos[i]]=,nst[pos[i]]=pos[i],pq.push(P(,pos[i]));

    while(!pq.empty())

    {

        int u=pq.top().second;pq.pop();

        if(vis[u]) continue;vis[u]=true;

        for(int i=head[u];i;i=e[i].nxt)

            if(dist[e[i].to]>dist[u]+e[i].w)

            {

                dist[e[i].to]=dist[u]+e[i].w;nst[e[i].to]=nst[u];

                pq.push(P(dist[e[i].to],e[i].to));

            }

    }

}

void MST()

{

    memset(head,,sizeof(head));

    int e_cnt=;tot=;

    for(int i=;i<=n;i++) fa[i]=i;

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

    {

        int x=edge[i].x,y=edge[i].y;

        if(nst[x]==nst[y]) continue;

        edge[++e_cnt].w=dist[x]+dist[y]+edge[i].w;

        edge[e_cnt].x=nst[x];edge[e_cnt].y=nst[y];

    }

    sort(edge+,edge+e_cnt+,cmp);

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

    {

        int fx=find(edge[i].x),fy=find(edge[i].y);

        if(fx!=fy)

            fa[fx]=fa[fy],add_edge(edge[i].x,edge[i].y,edge[i].w);

    }

}

void dfs(int x,int bloc)

{

    belong[x]=bloc;

    for(int i=;(<<i)<=dep[x];i++)

        f[x][i]=f[f[x][i-]][i-],

        mx[x][i]=max(mx[x][i-],mx[f[x][i-]][i-]);

    for(int i=head[x];i;i=e[i].nxt)

    {

        if(e[i].to==f[x][]) continue;

        dep[e[i].to]=dep[x]+;

        f[e[i].to][]=x;mx[e[i].to][]=e[i].w;

        dfs(e[i].to,bloc);

    }

}

int check(int x,int y)

{

    if(dep[x]<dep[y]) swap(x,y);

    int t=dep[x]-dep[y],ret=;

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

        if(t&(<<i)) ret=max(ret,mx[x][i]),x=f[x][i];

    for(int i=;i>=;i--)

        if(f[x][i]!=f[y][i])

            ret=max(ret,max(mx[x][i],mx[y][i])),

            x=f[x][i],y=f[y][i];

    if(x!=y) ret=max(ret,max(mx[x][],mx[y][]));

    return ret;

}

int main()

{

    scanf("%d%d%d",&n,&s,&m);

    for(int i=;i<=s;i++) scanf("%d",&pos[i]);

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

        scanf("%d%d%d",&edge[i].x,&edge[i].y,&edge[i].w),

        add_edge(edge[i].x,edge[i].y,edge[i].w);

    memset(dist,0x3f,sizeof(dist));

    dijkstra();MST();

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

        if(!belong[pos[i]]) dfs(pos[i],++cnt);

    scanf("%d",&q);

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

    {

        int x,y,b;scanf("%d%d%d",&x,&y,&b);

        if(belong[x]!=belong[y]) puts("NIE");

        else puts((check(x,y)<=b)?"TAK":"NIE");

    }

    return ;

}

Online

#include<bits/stdc++.h>

using namespace std;

typedef pair<int,int> P;

const int MAXN=2e5+;

struct data{int x,y,w;}edge[MAXN];

struct E{int to,nxt,w;}e[MAXN<<];

struct Query{int x,y,b,id;}q[MAXN];

priority_queue<P,vector<P>,greater<P> > pq;

int n,m,s,tot,head[MAXN],pos[MAXN],dist[MAXN],f[MAXN],res[MAXN],vis[MAXN];

void add_edge(int from,int to,int cost)

{

    e[++tot].nxt=head[from];e[tot].w=cost;e[tot].to=to;head[from]=tot;

    e[++tot].nxt=head[to];e[tot].w=cost;e[tot].to=from;head[to]=tot;

}

int find(int x){return (f[x]==x)?x:(f[x]=find(f[x]));}

bool cmp1(data a,data b){return a.w<b.w;}

bool cmp2(Query a,Query b){return a.b<b.b;}

void dijkstra()

{

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

        dist[pos[i]]=,pq.push(P(,pos[i]));

    while(!pq.empty())

    {

        P t=pq.top();pq.pop();

        int u=t.second;

        if(t.first>dist[u]) continue; //这里的判断一定要加，或用vis也行

        for(int i=head[u];i;i=e[i].nxt) //否则疯狂TLE

            if(dist[e[i].to]>dist[u]+e[i].w)

                dist[e[i].to]=dist[u]+e[i].w,pq.push(P(dist[e[i].to],e[i].to));

    }

}

int main()

{

    scanf("%d%d%d",&n,&s,&m);

    for(int i=;i<=s;i++) scanf("%d",&pos[i]);

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

        scanf("%d%d%d",&edge[i].x,&edge[i].y,&edge[i].w),

        add_edge(edge[i].x,edge[i].y,edge[i].w);

    memset(dist,0x3f,sizeof(dist));dijkstra();

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

        edge[i].w+=dist[edge[i].x]+dist[edge[i].y];

    scanf("%d",&s);

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

        scanf("%d%d%d",&q[i].x,&q[i].y,&q[i].b),q[i].id=i;

    sort(edge+,edge+m+,cmp1);

    sort(q+,q+s+,cmp2);

    int cur=;

    for(int i=;i<=n;i++) f[i]=i;

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

    {

        while(cur<=m&&edge[cur].w<=q[i].b)

        {

            int fx=find(edge[cur].x),fy=find(edge[cur].y);

            if(fx!=fy) f[fx]=fy;cur++;

        }

        res[q[i].id]=(find(q[i].x)==find(q[i].y));

    }

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

        puts(res[i]?"TAK":"NIE");

    return ;

}

Offline

Review:

1、关于$dijkstra$的模板：

一定要保证每个点只对其后继更新一次！不管是用$vis[i]$还是$top.first>dist[top.second]$

2、如果可以离线，查看能否通过将询问排序简化查询过程

3、套路：将图转为树，然后树上倍增查询