BZOJ 4289 最短路+优化建图

题意：给出一个N个点M条边的无向图，经过一个点的代价是进入和离开这个点的两条边的边权的较大值，求从起点1到点N的最小代价。起点的代价是离开起点的边的边权，终点的代价是进入终点的边的边权。

解法：参考https://www.cnblogs.com/zj75211/p/7168254.html这位大佬的。学到了建图新姿势。

首先还是先讲讲朴素建图：很容易想到拆点然后把边看成点，对于任意两条边a->b,b->c我们可以连一条权值为min(v1,v2)的a->c的边。容易看出这样的建图极限是n^2的，菊花图上会被卡成傻逼。我们要考虑优化建图：首先还是拆边然后把边看成点，然后我们枚举每一个中间点x（1<x<n），把x的出边按权值从小到大排序，然后小出边小大出边连权值差值的边，大出边向小出边连权值为0的边，x的每条入边向其对应的出边连权值为原边权的边，然后我们创造起点和终点：对于起点向其出边连权值原来的边，对于终点其入边向终点连权值原来的边。最后跑一次Dijkstra即可。

这样的建图看起来有些诡异，我们不妨思考一下为什么这样是对的？其实很简单：因为这样建图能起到和朴素建图一样的作用，这种方法是巧妙的利用了差值起到了一种逐步累加变成正确边长的方法。入边向相应出边的连边保证了经过x点入边的代价，然后通过补差值保证了通过x点出边的代价。并且这样累加的方式可以变成任何一条原来的边，没有任何遗漏。

只能说这样的建图确实十分巧妙，凭蒟蒻自己是想不到的，只能可遇不可求吧qwq。

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

typedef pair<LL,int> pii;

const int N=4e5+;

int n,m,s,t;

struct edge{ int x,y,z; }e[N<<];

vector<int> G[N];

int cnt=,head[N],nxt[N<<],to[N<<],len[N<<];

void add_edge(int x,int y,int z) {

    nxt[++cnt]=head[x]; to[cnt]=y; len[cnt]=z; head[x]=cnt;

}

bool cmp(int t1,int t2) { return e[t1].z<e[t2].z; }

void Build() {

    for (int i=;i<=*m+;i++) {  //起点和终点连边

        if (e[i].x==) add_edge(s,i,e[i].z);

        if (e[i].y==n) add_edge(i,t,e[i].z);

    }

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

        sort(G[i].begin(),G[i].end(),cmp);

        for (int j=;j<G[i].size();j++) {

            add_edge(G[i][j]^,G[i][j],e[G[i][j]].z);  //i点入边向出边连边

            if (j!=) add_edge(G[i][j],G[i][j-],);  //大出边向小出边连0

            if (j<G[i].size()-)  //小出边向大出边连差值

                add_edge(G[i][j],G[i][j+],e[G[i][j+]].z-e[G[i][j]].z);

        }

    }

}

priority_queue<pii> q;

LL dis[N<<];  bool vis[N<<];

LL Dijkstra() {

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

    dis[s]=;

    q.push(make_pair(,s));

    while (!q.empty()) {

        pii u=q.top(); q.pop();

        if (vis[u.second]) continue;

        vis[u.second]=;

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

            int y=to[i];

            if (dis[u.second]+len[i]<dis[y]) {

                dis[y]=dis[u.second]+len[i];

                q.push(make_pair(-dis[y],y));

            }

        }

    }

    return dis[t];

}

int main()

{

    cin>>n>>m;

    s=; t=m*+;

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

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

        e[i*]=(edge){x,y,z};

        e[i*+]=(edge){y,x,z};

        G[x].push_back(i*); G[y].push_back(i*+);  //G[i]保存i出边编号

    }

    Build();

    cout<<Dijkstra()<<endl;

    return ;

}

巴特西

BZOJ 4289 最短路+优化建图

最新文章

热门文章