【Acwing—单源最短路：建图】

雨点打透心脏的1/2处 2024-03-31 09:02 76阅读 0赞

**y总说，图论题的难点不在于打板子，而是建图的过程**

**个人觉得，建图的过程分成以下阶段：**

**1.确定结点的意义**

**2.确定边权的意义**

**结点一般都很显然，但是边权的意义我们一般把它设成对答案（或需要维护的东西）的贡献**

**具体看以下的例子：**

## **1.热浪** ##

[1129. 热浪 - AcWing题库][1129. _ - AcWing]

题意：

![5233d12cf91f4597b494069476ace130.png][]

思路：

跑一遍最短路就行，spfa，dij，floyd都行

Code:

#include <bits/stdc++.h>
    using namespace std;
    const int mxn=1e4+10,mxe=1e4+10,mnf=0x3f3f3f3f;
    struct ty{
        int to,next,w;
    }edge[mxe<<1];
    queue<int> q;
    int n,m,s,t,u,v,w,tot=0;
    int head[mxn],dis[mxn],vis[mxn];
    void add(int u,int v,int w){
        edge[tot].w=w;
        edge[tot].to=v;
        edge[tot].next=head[u];
        head[u]=tot++;
    }
    void init(){
        tot=0;
        for(int i=0;i<=n;i++){
            head[i]=-1;
            vis[i]=0;
            dis[i]=mnf;
        }
        while(!q.empty()) q.pop();
    }
    void spfa(){
        dis[s]=0;
        vis[s]=1;
        q.push(s);
        while(!q.empty()){
            int u=q.front();
            q.pop();
            vis[u]=0;
            for(int i=head[u];~i;i=edge[i].next){
                if(dis[edge[i].to]>dis[u]+edge[i].w){
                    dis[edge[i].to]=dis[u]+edge[i].w;
                    if(!vis[edge[i].to]){
                        vis[edge[i].to]=1;
                        q.push(edge[i].to);
                    }
                }
            }
        }
    }
    int main(){
        ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
        cin>>n>>m>>s>>t;
        init();
        for(int i=1;i<=m;i++){
            cin>>u>>v>>w;
            add(u,v,w);
            add(v,u,w);
        }
        spfa();
        if(dis[t]==mnf) cout<<-1<<'\n';
        else cout<<dis[t]<<'\n';
    }

## **2.信使** ##

[1128. 信使 - AcWing题库][1128. _ - AcWing]

题意：

![fef0c4eab9a646f2a9fb7bfae32f3158.png][]

这个就是跑一遍最短路，预处理一下dis数组，然后去看dis最大值就行

Code：

#include <bits/stdc++.h>
    using namespace std;
    const int mxn=2e2+10,mxe=2e2+10,mnf=0x3f3f3f3f,inf=0xc0c0c0c0;
    struct ty{
        int to,next,w;
    }edge[mxe<<1];
    queue<int> q;
    int n,m,x,y,w,tot=0;
    int head[mxn],dis[mxn],vis[mxn];
    void add(int u,int v,int w){
        edge[tot].w=w;
        edge[tot].to=v;
        edge[tot].next=head[u];
        head[u]=tot++;
    }
    void init(){
        tot=0;
        for(int i=0;i<=n;i++){
            vis[i]=0;
            head[i]=-1;
            dis[i]=mnf;
        }
        while(!q.empty()) q.pop();
    }
    void spfa(){
        dis[1]=0;
        vis[1]=1;
        q.push(1);
        while(!q.empty()){
            int u=q.front();
            q.pop();
            vis[u]=0;
            for(int i=head[u];~i;i=edge[i].next){
                if(dis[edge[i].to]>dis[u]+edge[i].w){
                    dis[edge[i].to]=dis[u]+edge[i].w;
                    if(!vis[edge[i].to]){
                        q.push(edge[i].to);
                        vis[edge[i].to]=1;
                    }
                }
            }
        }
    }
    int main(){
        ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
        cin>>n>>m;
        init();
        for(int i=1;i<=m;i++){
            cin>>x>>y>>w;
            add(x,y,w);
            add(y,x,w);
        }
        spfa();
        int ans=inf;
        for(int i=1;i<=n;i++){
            if(dis[i]==mnf){
                cout<<-1<<'\n';
                return 0;
            }
            ans=max(ans,dis[i]);
        }
        cout<<ans<<'\n';
    }

##  **3.香甜的黄油** ##

[1127. 香甜的黄油 - AcWing题库][1127. _ - AcWing]

![c9c137eb43b047f387d0da6115ed995b.png][]

枚举就行，枚举奶油放在哪个点上，每个点都去跑一遍最短路，然后去看奶油放在哪个点上牛牛到奶油的距离之和最小

Code：

#include <bits/stdc++.h>
    using namespace std;
    const int mxn=2e3+10,mxe=2e3+10,mnf=0x3f3f3f3f;
    struct ty{
        int to,next,w;
    }edge[mxe<<1];
    struct ty2{
        int x,dis;
        bool operator< (const ty2 &a) const{
            return a.dis<dis;
        }
    };
    unordered_map<int,int> mp;
    priority_queue<ty2> q;
    int N,n,m,x,y,w,tot=0;
    int head[mxn],dis[mxn],vis[mxn];
    void add(int u,int v,int w){
        edge[tot].w=w;
        edge[tot].to=v;
        edge[tot].next=head[u];
        head[u]=tot++;
    }
    void init(){
        tot=0;
        mp.clear();
        for(int i=0;i<=n;i++){
            head[i]=-1;
            dis[i]=mnf;
            vis[i]=0;
        }
        while(!q.empty()) q.pop();
    }
    void init2(){
        for(int i=0;i<=n;i++){
            vis[i]=0;
            dis[i]=mnf;
        }
        while(!q.empty()) q.pop();
    }
    int dij(int s){
        init2();
        dis[s]=0;
        ty2 u;
        u.dis=dis[s],u.x=s;
        q.push(u);
        while(!q.empty()){
            ty2 u=q.top();
            q.pop();
            if(vis[u.x]) continue;
            vis[u.x]=1;
            for(int i=head[u.x];~i;i=edge[i].next){
                if(vis[edge[i].to]) continue;
                if(dis[edge[i].to]>dis[u.x]+edge[i].w){
                    dis[edge[i].to]=dis[u.x]+edge[i].w;
                    ty2 tmp;
                    tmp.dis=dis[edge[i].to];
                    tmp.x=edge[i].to;
                    q.push(tmp);
                }
            }
        }
        int res=0;
        for(int i=1;i<=n;i++){
            if(mp[i]){
                if(dis[i]==mnf) return mnf;
                res+=dis[i]*mp[i];
            }
        }
        return res;
    }
    int main(){
        ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
        cin>>N>>n>>m;
        init();
        for(int i=1;i<=N;i++) cin>>x,mp[x]++;
        for(int i=1;i<=m;i++){
            cin>>x>>y>>w;
            add(x,y,w);
            add(y,x,w);
        }
        int ans=mnf;
        for(int i=1;i<=n;i++){
            ans=min(ans,dij(i));
        }
        cout<<ans<<'\n';
    }

## 4.最小花费 ##

[1126. 最小花费 - AcWing题库][1126. _ - AcWing]

题意：

![92e37b59382742b299570c20b3dcd8f0.png][]

思路：

转化为A\*w1\*w2\*....\*wn=B，即求w1\*w2\*....\*wn最小值，其中wi为扣除的百分比

那么我们可以建图：

结点表示人

边权表示扣除的百分比

建完图后，可以发现我们要求的就是边权最小积

那么我们怎么从最小和转换到最小积：取对数就好了

lg(w1\*w2\*....\*wn)=lgw1+lgw2+....+lgwn

因为lg函数始终是单调递增的，因此要求w1\*w2\*....\*wn的最小值，就求lg(w1\*w2\*....\*wn)的最小值

即求lgw1+lgw2+....+lgwn的最小值

即求lgwi的最小值

因此我们可以按照wi的大小去跑一遍最短路，然后跑的时候dist的值维护边权积就可以了

Code：

#include <bits/stdc++.h>
    using namespace std;
    const int mxn=2e3+10,mxe=1e5+10,mnf=0x3f3f3f3f;
    struct ty{
        int to,next;
        double w;
    }edge[mxe<<1];
    queue<int> q;
    int n,m,x,y,w,tot=0,s,t;
    int head[mxn],vis[mxn];
    double dis[mxn];
    void add(int u,int v,double w){
        edge[tot].w=w;
        edge[tot].to=v;
        edge[tot].next=head[u];
        head[u]=tot++;
    }
    void init(){
        tot=0;
        for(int i=0;i<=n;i++){
            head[i]=-1;
            vis[i]=0;
        }
        while(!q.empty()) q.pop();
    }
    double spfa(int u,int v){
        dis[u]=1;
        q.push(u);
        while(!q.empty()){
            int u=q.front();
            q.pop();
            vis[u]=0;
            for(int i=head[u];~i;i=edge[i].next){
                if(dis[edge[i].to]<dis[u]*(1.0-edge[i].w)){
                    dis[edge[i].to]=dis[u]*(1.0-edge[i].w);
                    if(!vis[edge[i].to]){
                        vis[edge[i].to]=1;
                        q.push(edge[i].to);
                    }
                }
            }
        }
        return dis[t];
    }
    int main(){
        //ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
        scanf("%d%d",&n,&m);
        init();
        for(int i=1;i<=m;i++){
            scanf("%d%d%d",&x,&y,&w);
            add(x,y,1.0*w/100);
            add(y,x,1.0*w/100);
        }
        scanf("%d%d",&s,&t);
        printf("%.8f\n",100/spfa(s,t));
    }

## 5.最优乘车 ##

[920. 最优乘车 - AcWing题库][920. _ - AcWing]

题意：

![fe35a021a57e454d882a63af05ef9f3b.png][]

思路：

换乘次数=坐车次数-1

因此我们只需要维护坐车次数就行

首先先建图：

结点就是公交车站

边权意义就设成坐车次数

那么在同一线路上的车站之间的坐车次数都为1，因此同一线路上的车站之间都连一条边权为1的边

不同线路的车站之间的坐车次数就可以根据跑最短路来求了

时间复杂度为O(M\*(N-1)\*N/2)

Code：

#include <bits/stdc++.h>
    using namespace std;
    const int mxn=5e2+10,mxe=5e2+10,mnf=0x3f3f3f3f;
    struct ty{
        int to,next,w;
    }edge[mxe<<1];
    queue<int> q;
    string s;
    int m,n,len=0,p,tot=0;
    int a[mxn],head[mxn],dis[mxn],vis[mxn];
    void add(int u,int v,int w){
        edge[tot].w=w;
        edge[tot].to=v;
        edge[tot].next=head[u];
        head[u]=tot++;
    }
    void init(){
        tot=0;len=0;
        s.clear();
        for(int i=0;i<=n;i++){
            head[i]=-1;
            dis[i]=mnf;
        }
        while(!q.empty()) q.pop();
    }
    void spfa(){
        dis[1]=0;
        vis[1]=1;
        q.push(1);
        while(!q.empty()){
            int u=q.front();
            q.pop();
            vis[u]=0;
            for(int i=head[u];~i;i=edge[i].next){
                if(dis[edge[i].to]>dis[u]+edge[i].w){
                    dis[edge[i].to]=dis[u]+edge[i].w;
                    if(!vis[edge[i].to]){
                        vis[edge[i].to]=1;
                        q.push(edge[i].to);
                    }
                }
            }
        }
    }
    int main(){
        ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
        cin>>m>>n;
        init();
        getline(cin,s);
        for(int i=1;i<=m;i++){
            len=0;
            getline(cin,s);
            stringstream ssin(s);
            while(ssin>>p) a[++len]=p; 
            for(int i=1;i<=len;i++){
                for(int j=i+1;j<=len;j++){
                    add(a[i],a[j],1);
                    add(a[j],a[i],1);
                }
            }
        }
        spfa();
        if(dis[n]==mnf) cout<<"NO"<<'\n';
        else cout<<dis[n]<<'\n';
    }

**总结：**

**建图的过程分成以下阶段：**

**1.确定结点的意义**

**2.确定边权的意义**

**结点一般都很显然，但是边权的意义我们一般把它设成对答案（或需要维护的东西）的贡献**

[1129. _ - AcWing]: https://www.acwing.com/problem/content/1131/
[5233d12cf91f4597b494069476ace130.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/af2ba2d931b54ac3adc373df65df4262.png
[1128. _ - AcWing]: https://www.acwing.com/problem/content/1130/
[fef0c4eab9a646f2a9fb7bfae32f3158.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/7c1d567fc8ad4710adc21c7e4af8d8ba.png
[1127. _ - AcWing]: https://www.acwing.com/problem/content/1129/
[c9c137eb43b047f387d0da6115ed995b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/5635ca50e73440aba1bb373d49d4c49e.png
[1126. _ - AcWing]: https://www.acwing.com/problem/content/1128/
[92e37b59382742b299570c20b3dcd8f0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/c868ff481d1e4b5c87015bc7592137cd.png
[920. _ - AcWing]: https://www.acwing.com/problem/content/922/
[fe35a021a57e454d882a63af05ef9f3b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/f5cc6e3876da4e5391e24ec862ccc3e2.png