算法与数据结构(图)
算法与数据结构  0次访问

算法与数据结构(图)

——以下题目均来自于PAT甲级题库。
✨✨✨

1003.Emergency (25分)(Dijkstra)

思路
这一道题考察了Dijkstra算法，并且在使用该算法的时候还需要额外的维护一些属性。 在Dijkstra算法运行的过程中，我们会确定一个到达源点c2(求救城市)的集合，这个集合中存储的是当前已经确定到c2最短路径的点，并且此时这些点到c2路径上的最多可以召集求救队的数量(num)也确定了，有多少条到c2的最短路径(cnt)也确定了。
每次当我们选一个全局最小的点i出来的时候，该点就是上面集合中新的一员了，我们用这个点去更新其他点到c2的最小距离，同时:还要更新到c2的路径的条数和召集求救队的最大数量,最小距离已经成为模板了，那这两个属性该如何维护呢？分为两种情况:

  • 用点i更新结点j的时候，j到i的距离d[j][i]和i到c2的最短距离dist[i]满足dist[j]>dist[i]+d[j][i]时说明此时j到c2的最短路径要经过i，所以cnt[j]=cnt[i],因为j只是连了一条边到i，因此j到c2的多条路径就由i到c2的多条路径决定;同理num[j]=num[i]+w[j]
  • 如果满足dist[j]==dist[i]+d[j][i]时说明j到c2的路径不止走i这一条，因此这里是要把从i这边走的情况加上即cnt[j]+=cnt[i];同理由于除了可以从i走之外j还可以从别处走，要把这些所有路径的走法所能召集的队伍数量取一个最大值所以num[j]=max(num[j],num[i]+w[j])。

    • 代码

    Emergency
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    #include<iostream>
    #include<cstring>
    using namespace std;

    const int N = 510;
    int d[N][N];
    int dist[N];
    bool st[N];
    int n,m,c1,c2;
    int w[N];
    int cnt[N],num[N];

    void dijkstra(){
        memset(dist,0x3f,sizeof dist);
        dist[c2]=0;cnt[c2]=1;num[c2]=w[c2];//除了距离外，这里额外维护的数组也要初始化
        
        for(int i=0;i<n;i++){
            int t=-1;
            for(int j=0;j<n;j++)
                if(!st[j]&&(t==-1||dist[j]<dist[t])) t=j;
            st[t]=true;
            for(int j=0;j<n;j++){
                if(dist[j]>dist[t]+d[t][j]){//情况1
                    dist[j]=dist[t]+d[t][j];
                    cnt[j]=cnt[t];//到达c2的路径数量
                    num[j]=num[t]+w[j];//到达c2路径上集合队伍的最大值
                }else if(dist[j]==dist[t]+d[t][j]){//情况2
                    cnt[j]+=cnt[t];
                    num[j]=max(num[j],num[t]+w[j]);
                }
            }
        }
    }

    int main(){
        cin>>n>>m>>c1>>c2;
        for(int i=0;i<n;i++) cin>>w[i];
        memset(d,0x3f,sizeof d);
        while(m--){
            int a,b,c;
            cin>>a>>b>>c;
            d[a][b]=d[b][a]=min(d[a][b],c);
        }
        
        dijkstra();
        cout<<cnt[c1]<<" "<<num[c1];
        return 0;
    }

    1030.Travel Plan (30分)(Dijkstra)

    思路
    这一题如何更新结点的思路和上面的几乎一样，当dist[j]==dist[t]+d[t][j]blabla~当dist[j]>dist[t]+d[t][j]blabla~。这里唯一需要说明下的就是这一题需要存路径了，对于这样唯一结果的题目，我们一般用一个pre数组存下每个节点的前驱即可。

    代码

    Travel Plan
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    #include<iostream>
    #include<cstring>
    #include<vector>
    #include<algorithm>
    using namespace std;

    const int N = 510;
    int d[N][N],c[N][N];
    int dist[N],cost[N],pre[N];
    bool st[N];
    int n,m,S,D;

    void dijkstra(){
        memset(dist,0x3f,sizeof dist);
        memset(cost,0x3f,sizeof cost);
        dist[D]=0,cost[D]=0;
        pre[D]=D;
        for(int i=0;i<n;i++){
            int t=-1;
            for(int j=0;j<n;j++){
                if(!st[j]&&(t==-1||dist[t]>dist[j])) t=j;
            }
            st[t]=true;
            for(int j=0;j<n;j++){
                if(dist[j]>dist[t]+d[t][j]){
                    //1)当从t走的时候是唯一的最短路时
                    dist[j]=dist[t]+d[t][j];
                    cost[j]=cost[t]+c[t][j];
                    pre[j]=t;
                }else if(dist[j]==dist[t]+d[t][j]){
                    //2)当最短路不唯一时
                    if(cost[j]>cost[t]+c[t][j]){
                        cost[j]=cost[t]+c[t][j];
                        pre[j]=t;
                    }
                }
            }
        }
    }

    int main(){
        cin>>n>>m>>S>>D;
        memset(d,0x3f,sizeof d);
        memset(c,0x3f,sizeof c);
        while(m--){
            int a,b,x,y;
            cin>>a>>b>>x>>y;
            if(d[a][b]>x){
                d[a][b]=d[b][a]=x;
                c[a][b]=c[b][a]=y;
            }else if(d[a][b]==x) c[a][b]=c[b][a]=min(c[a][b],y);
        }
        
        dijkstra();
        
        vector<int> v;
        //由于这里保证了最短路径唯一，所以要想输出最短路径，只需要它是从哪一个结点更新过来的即可
        //之后再倒着从起点找回终点即可
        for(int i=S;i!=D;i=pre[i]) v.push_back(i);
        for(int i=0;i<v.size();i++) cout<<v[i]<<" ";
        cout<<D<<" ";
        cout<<dist[S]<<" "<<cost[S];
        
        return 0;
    }

    1034.Head of a Gang (30分)

    思路
    这一题总的来说思路比较简单，即首先dfs连通块得到团伙的总通讯时间以及团伙的成员，然后再统计出团伙中通讯量最大的头目即可。并且此题在存数据的时候，我们用map来保存一个结点与之相连的所有边，存的方式比较随意，因为之后我们是通过dfs的方式来找这个连通块，所以只要把边存下来即可。但是比较复杂的地方在于这一题的读入上面以及输出方面，具体的看代码吧~~

    代码

    Head of a Gang
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    #include<iostream>
    #include<algorithm>
    #include<map>
    #include<vector>
    #include<string>

    using namespace std;

    #define fi first
    #define se second

    typedef pair<string,int> PSI;
    map<string,vector<PSI>> e;//这里存的是一条边的起始点和权重
    map<string,int> total;//这里存的是某个点总的通话时间
    map<string,bool> st;
    int n,k;
    int dfs(string u,vector<string> &tmp){
        int sum=0;
        st[u]=true;
        tmp.push_back(u);
        for(auto t:e[u]){
            string j=t.fi;
            sum+=t.se;
            if(!st[j])
                sum+=dfs(j,tmp);
        }

        return sum;
    }

    const int N = 1010;

    int main(){
        cin>>n>>k;
        for(int i=0;i<n;i++){
            string n1,n2;
            int t;
            cin>>n1>>n2>>t;
            total[n1]+=t;
            total[n2]+=t;
            e[n1].push_back({n2,t});
            e[n2].push_back({n1,t});
        }
        
        vector<PSI> res;
        for(auto t:total){
            vector<string> tmp;
            int sum=dfs(t.fi,tmp)/2;//dfs得到团伙总通话时长以及团伙名单
            if(tmp.size()>2&&sum>k){//团伙要大于2人，且总的通话时长要大于k
                string head=tmp[0];
                for(auto p:tmp)//遍历团伙名单找到通话时长最多的
                    if(total[p]>total[head])
                        head=p;
                res.push_back({head,tmp.size()});//存头目和团伙数
            }
            
        }
        
        sort(res.begin(),res.end());
        cout<<res.size()<<endl;
        if(res.size()){
            for(auto r:res){
                cout<<r.fi<<" "<<r.se<<endl;
            }
        }
        return 0;
    }

    🎡1087.All Roads Lead to Rome (30分)

    思路
    建议直接搞懂该题，这样可以省去写1003题和1030题，因为这题是前面题目的大集合，什么东西都给揉进来了。

    代码

    All Roads Lead to Rome
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    #include<iostream>
    #include<unordered_map>
    #include<algorithm>
    #include<string>
    #include<vector>
    #include<cstring>

    using namespace std;

    const int N = 210;

    //花费;开心度;最终走的路径经过的城市数量;最短路的条数;走过的城市
    int dist[N],happy[N],len[N],num[N],pre[N];
    int d[N][N];
    bool st[N];
    int w[N];

    unordered_map<string,int> maps;//城市名称映射到标号;起始位置为1(即初始的城市)
    string citys[N];//标号映射到城市名称

    int n,k;

    void dijkstra(){
        memset(dist,0x3f,sizeof dist);
        memset(len,0x3f,sizeof len);
        
        dist[1]=0;num[1]=1;len[1]=0;
        
        for(int i=0;i<n;i++){
            int t=-1;
            for(int j=1;j<=n;j++)
                if(!st[j]&&(t==-1||dist[t]>dist[j])) t=j;
            st[t]=true;
            for(int j=1;j<=n;j++){
                if(dist[j]>dist[t]+d[t][j]){
                    dist[j]=dist[t]+d[t][j];
                    happy[j]=happy[t]+w[j];
                    len[j]=len[t]+1;
                    num[j]=num[t];
                    pre[j]=t;
                }else if(dist[j]==dist[t]+d[t][j]){
                    if(happy[j]<happy[t]+w[j]){
                        happy[j]=happy[t]+w[j];
                        len[j]=len[t]+1;
                        pre[j]=t;
                    }else if(happy[j]==happy[t]+w[j]){
                        if(len[j]>len[t]+1){
                            len[j]=len[t]+1;
                            pre[j]=t;
                        }
                    }
                    num[j]+=num[t];
                }
            }
            
        }
        
    }

    int main(){
        cin>>n>>k>>citys[1];
        maps[citys[1]]=1;
        
        for(int i=2;i<=n;i++){
            cin>>citys[i]>>w[i];
            maps[citys[i]]=i;//建立好城市名到标号的映射
            
        }

        memset(d,0x3f,sizeof d);
        
        while(k--){
            string x,y;
            int z;
            cin>>x>>y>>z;
            
            int a=maps[x],b=maps[y];//映射到数字
            d[a][b]=d[b][a]=min(d[a][b],z);
        }    
        
        dijkstra();
        string des="ROM";
        int end=maps[des];
        cout<<num[end]<<" "<<dist[end]<<" "<<happy[end]<<" "<<happy[end]/len[end]<<endl;
        vector<int> v;
        for(int i=end;i!=1;i=pre[i]) v.push_back(i);

        cout<<citys[1];
        for(int i=v.size()-1;i>=0;i--) cout<<"->"<<citys[v[i]];
        
        return 0;
    }

    🌌1122.Hamiltonian Cycle (25分)

    思路
    这一题与其说是一个图论的题目，其实更像是一个模拟的题目，只需要对给出的每条路径，判断一下是否满足哈密顿回路的规则即可，哈密顿回路的规则如下:
  • 判断每一步会否是可达的。
  • 判断经过了所有的n个点，且除了起点之外其他的点只走了一次。
  • 判断起点和终点是否相同。

    • 代码

    Hamiltonian Cycle
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    #include<iostream>
    #include<unordered_set>
    #include<algorithm>
    #include<vector>
    using namespace std;

    const int N = 210;
    bool d[N][N];

    int n,m,k;

    int main(){
        cin>>n>>m;
        while(m--){
            int v1,v2;
            cin>>v1>>v2;
            d[v1][v2]=d[v2][v1]=true;
        }
        cin>>k;
        
        while(k--){

            int s;
            cin>>s;
            vector<int> v;
            for(int i=0;i<s;i++){
                int x;
                cin>>x;
                v.push_back(x);
            }
            bool suc=true;
            
            unordered_set<int> sets;
            for(int i=0;i<v.size()-1;i++){
                int v1=v[i],v2=v[i+1];
                sets.insert(v1);sets.insert(v2);
                //1.判断每一步会否是可达的
                if(!d[v1][v2]){
                    suc=false;
                    break;
                }
            }
            //2.判断经过了所有的n个点，且除了起点之外其他的点只走了一次
            if(sets.size()!=n||v.size()!=n+1) suc=false;
            //3.判断起点和终点是否相同
            if(v[0]!=v[s-1]) suc=false;
            
            if(suc) puts("YES");
            else puts("NO");
            
        }
        return 0;
    }

    🌌1126.Eulerian Path (25分)

    思路
    这一题依旧是一个模拟题，只用判断是否满足欧拉图，半欧拉图的特点即可。
  • 欧拉图:首先这是一个连通图，且所有点的度数为偶数。
  • 半欧拉图:首先这是一个连通图，且只有两个点的度为奇数，其余点的度数都为偶数。
    • 剩下的就是非欧拉图了，上面对于连通图的判断只需要遍历一遍图，看看从一点开始能不能扩展到图上的每一点。

    代码

    Eulerian Path
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    #include<iostream>
    #include<cstring>

    using namespace std;

    const int N = 510;
    bool d[N][N],st[N];
    int du[N];
    int n,m;

    int dfs(int u){//图的遍历
        int cnt=1;
        st[u]=true;//如果把st设置为true放在for循环里面的话，那么i=1一开始不会被设置为true，那么之后还会再访问到1这个点
        for(int i=1;i<=n;i++){
            if(i==u) continue;
            if(!st[i]&&d[u][i])
                cnt+=dfs(i);
        }
        
        return cnt;
    }

    int main(){
        cin>>n>>m;
        while(m--){
            int a,b;
            cin>>a>>b;
            d[a][b]=d[b][a]=true;
            du[a]++;du[b]++;
        }
        cout<<du[1];
        for(int i=2;i<=n;i++) cout<<" "<<du[i];
        puts("");
        int cnt = dfs(1);//看看从1开始可以展开多少个点
        if(cnt==n){
            int odd=0;
            for(int i=1;i<=n;i++)
                if(du[i]%2) odd++;
            
            if(odd==0) puts("Eulerian");
            else if(odd==2) puts("Semi-Eulerian");
            else puts("Non-Eulerian");
            
        }else{
            puts("Non-Eulerian");
        }
        
        return 0;
    }

    🎡1131.Subway Map (30分)

    思路
    本题的难点在于建图上，假如按照常规的存图的方式，我们只会对给定线路上相邻两点间建边，这样就有一个问题，由于本题还要求了当最短路不唯一的时候要求输出换乘数最少的线路，对于这个需求前面的建图方式就很不方便了，比如当要走到a站点的时候，还需要知道a之前的站点是从哪里走过来的，然后还需要把你走过的所有站点保存下来，最后再输出每段线路的起始端点(抠掉中间的站点不输出)，这样做就很麻烦。所以我们可以这样建图:把图中所有的点之间都建边，这样每次只要多走一个点就代表换乘了一次，这样就很方便了！ 注意：由于此题的点数较多，不能用朴素版的Dijkstra算法了，这里我们使用堆优化的Dijkstra算法，并用邻接表来存图。

    代码

    Subway Map
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    #include<iostream>
    #include<cstring>
    #include<queue>
    #include<string>
    #include<algorithm>

    using namespace std;
    #define fi first
    #define se second
    typedef pair<int,int> PII;

    //点数，边数
    const int N = 1e4+10,M=1e6+10;//m*m*n
    int post[N];
    int h[N],ne[M],e[M],line[M],w[M],idx;
    //dist:最短路长度
    //pre:存路线，打印输出的时候要按造路线输出
    int dist[N],pre[N],cnt[N];//cnt:记录换乘的次数
    bool st[N];
    string msg[N];

    int n,k;

    void add(int a,int b,int c,int id){
        e[idx]=b;line[idx]=id;w[idx]=c;ne[idx]=h[a];h[a]=idx++;
    }

    //得到数字的字符串表示，不足四位补0
    string get_num(int n){
        string res=to_string(n);
        while(res.size()<4) res="0"+res;
        return res;
    }

    void dijkstra(int S,int T){
        memset(dist,0x3f,sizeof dist);
        memset(cnt,0x3f,sizeof cnt);
        memset(st,false,sizeof st);
        dist[S]=0;cnt[S]=0;
        priority_queue<PII,vector<PII>,greater<PII>> q;
        q.push({0,S});
        while(q.size()){
            auto p=q.top();
            q.pop();
            int t=p.se;
            if(st[t]) continue;
            st[t]=true;
            for(int i=h[t];~i;i=ne[i]){
                int j=e[i];
                if(dist[j]>dist[t]+w[i]){
                    dist[j]=dist[t]+w[i];
                    pre[j]=t;
                    cnt[j]=cnt[t]+1;
                    msg[j]="Take Line#"+to_string(line[i])+" from "+get_num(t)+" to "+get_num(j)+".";
                    q.push({dist[j],j});
                }else if(dist[j]==dist[t]+w[i]){
                    if(cnt[j]>cnt[t]+1){
                        cnt[j]=cnt[t]+1;
                        pre[j]=t;
                        msg[j]="Take Line#"+to_string(line[i])+" from "+get_num(t)+" to "+get_num(j)+".";
                    }
                }
            }
        }
        
        vector<string> v;
        cout<<dist[T]<<endl;
        for(int i=T;i!=S;i=pre[i]) v.push_back(msg[i]);
        for(int i=v.size()-1;i>=0;i--) cout<<v[i]<<endl;
        
    }

    int main(){
        cin>>n;
        memset(h,-1,sizeof h);
        for(int i=1;i<=n;i++){
            int m;
            cin>>m;
            for(int j=0;j<m;j++) cin>>post[j];
            for(int j=0;j<m;j++){
                for(int k=0;k<j;k++){
                    int len;
                    if(post[0]!=post[m-1]) len=j-k;
                    //直接从k走到j; 先从j走到m,再从m走到k
                    else len=min(j-k,m-1-j+k);//假如是环的话那么j,k之间的距离则走的是较小的那一端圆弧
                    add(post[j],post[k],len,i);
                    add(post[k],post[j],len,i);
                }
            }
        }
        cin>>k;
        while(k--){
            int S,T;
            cin>>S>>T;
            dijkstra(S,T);
        }
        return 0;
    }

    🎡1018.Public Bike Management (30分)

    思路
    注意这里和上面的诸如《All Roads Lead to Rome》这样的题目不一样，虽然都是多关键字的最短路问题，但是本题的另外两个关键字即开始从PBMC发送的车的数量send，以及最终从问题站台带回的车的数量bring，它们不像之前问题的关键字那样在Dijkstra算法中可以直接判断是否是最优值的【比如拿最短路的距离dist来说，只要dist[j]>dist[t]+d[t][j],我们就可以从t走到j】，但是拿send来说，最终决定的要发送的车的数量是走完整条路之后决定的，没办法说从a点走到b点的时候就可以决定要发送的send的数量,也就不可以决定到底是从a走b还是从a走c。

    因此对于本题，我们的做法是首先用Dijkstra算法求得最短路，然后再dfs一下，求得在这些最短中最小的send和bring的最短路。

    代码

    Public Bike Management 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    #include<iostream>
    #include<cstring>
    #include<algorithm>
    #include<vector>
    using namespace std;

    const int N = 510,INF = 0x3f3f3f3f;
    int d[N][N];
    int dist[N],cpa[N];
    bool st[N];
    int C,n,S,m;
    /*Dijkstra模板*/
    void dijkstra(){
        memset(dist,0x3f,sizeof dist);
        dist[S]=0;//注意这里是从终点往起点做
        for(int i=0;i<=n;i++){
            int t=-1;
            for(int j=0;j<=n;j++)
                if(!st[j]&&(t==-1||dist[t]>dist[j])) t=j;
            st[t]=true;
            for(int j=0;j<=n;j++){
                if(dist[j]>dist[t]+d[t][j])
                    dist[j]=dist[t]+d[t][j];
            }
        }
    }
    int send=INF,bring=INF;
    vector<int> path,v;
    //s记录的是当前一路走来多余的车和缺少的车的数量之和，当某站点缺少车辆的时候减去相关车辆，
    //多余的时候加上相关的车辆，因此当s为负时代表的是走这条路径缺少了这么多辆车，当s为正代表
    //多余了这么多辆车;
    //mins即代表的是PBMC需要补充的车辆，它的值等于沿路走来时最小的s，因为沿路上
    //所有的站点都要达到理想状态的话，那么你到了某个站点它缺多少bike就要补多少。
    //注意这里的s算的是累加的和，它象征的是你到达某个点为止
    //时你需要补足的自行车数量，而假如它过了这个点之后s变大了，那么就代表有站点有多余的，那么你可以利用
    //这些多余的车来进行补足，因此只要保证最小的mins可以补足，那么从mins之后就可以拿别的站点多的bike了
    void dfs(int u,int s,int mins){
        if(u){//只有当u不是0点即不是PBMC的时候才计算携带的bike数量
            s-=C/2-cpa[u];//当站点的车辆<C/2时减去相应的车辆，当>C/2时加上相应的车辆
            mins=min(mins,s);
        }
        if(u==S){
            int sd=abs(min(mins,0));//mins为正代表的是多余了这么多自行车，所以不要携带任何自行车
            int bg=sd+s;//需要带回的自行车等于多余的自行车(为负数代表到S时还缺少多少自行车)+开始带来的自行车之和
            if(send>sd){
                path=v;send=sd;bring=bg;
            }else if(send==sd&&bring>bg){
                path=v;bring=bg;
            }
            return;
        }
        for(int i=1;i<=n;i++){
            //注意Dijkstra算法是从终点往起点做的；
            //所以这里判断的方向相当于是某个点走到起点的方向
            if(dist[u]==dist[i]+d[u][i]){//如果走i结点可能是最短路的话
                v.push_back(i);
                dfs(i,s,mins);
                v.pop_back();
            }
        }
    }

    int main(){
        cin>>C>>n>>S>>m;
        for(int i=1;i<=n;i++) scanf("%d",&cpa[i]);
        memset(d,0x3f,sizeof d);
        while(m--){
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            d[a][b]=d[b][a]=min(d[a][b],c);
        }
        dijkstra();
        
        
        //从PBMC开始走,在PMBC不需要计算s和mins
        dfs(0,0,0);
        cout<<send<<" "<<0;
        for(int i=0;i<path.size();i++) cout<<"->"<<path[i];
        cout<<" "<<bring;
        return 0;
    }

    🎡1072.Gas Station (30分)

    思路
    本题的难点在于对于英语长难句的解读上面。。。本题的思路是分别对每个加油站用一次Dijkstra算法，得到到加油站最近的距离以及所有城市到该加油站距离的平均值，然后比较全部Dijkstra算法的运行情况中最远的最近距离，如果该值相等则要最小的平均值。

    代码

    Gas Station
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    #include<iostream>
    #include<cstring>
    #include<string>
    #include<algorithm>

    using namespace std;

    //注意这里请＋20，因为我们存的时候把加油站(10个)一起存
    const int N = 1e3+20,INF=0x3f3f3f3f;
    int d[N][N];
    int dist[N];
    bool st[N];
    int n,m,k,D;
    int get(string s){
        //加油站从n+1开始映射
        //居民房映射到1~n
        if(s[0]=='G') return n+stoi(s.substr(1));
        else return stoi(s);
    }

    //加油站位置;到加油站的最短距离;总的距离
    void dijkstra(int u,int &mind,int &sumd){
        memset(dist,0x3f,sizeof dist);
        memset(st,false,sizeof st);
        dist[u]=0;
        for(int i=0;i<n+m;i++){
            int t=-1;
            for(int j=1;j<=m+n;j++)
                if(!st[j]&&(t==-1||dist[t]>dist[j]))
                    t=j;
            st[t]=true;
            for(int j=1;j<=n+m;j++)
                if(dist[j]>dist[t]+d[t][j])
                    dist[j]=dist[t]+d[t][j];
        }
        //判断是否有人超过了服务范围;超过的话直接把mind设置为-∞,表示无效答案
        for(int i=1;i<=n;i++){
            if(dist[i]>D){
                mind=-INF;
                return;
            }
        }
        mind=INF;sumd=0;
        for(int i=1;i<=n;i++){
            mind=min(dist[i],mind);
            sumd+=dist[i];
        }
    }

    int main(){
        cin>>n>>m>>k>>D;
        memset(d,0x3f,sizeof d);
        while(k--){
            string a,b;
            int c;
            cin>>a>>b>>c;
            int x=get(a),y=get(b);
            d[x][y]=d[y][x]=min(d[x][y],c);
        }
        
        int id=-1,mind=0,sumd=INF;
        //遍历加油站
        for(int i=n+1;i<=n+m;i++){
            int d1,d2;
            dijkstra(i,d1,d2);
            if(d1>mind){
                mind=d1;sumd=d2;
                id=i;
            }else if(d1==mind&&d2<sumd){
                sumd=d2;id=i;
            }
        }
        if(id==-1) puts("No Solution");
        else{
            printf("G%d\n",id-n);
            printf("%.1lf %.1lf",(double)mind,(double)sumd/n+1e-8);//+1e-8:为了防止浮点数保存时不精确
        }
        return 0;
    }
    #

    喜欢这篇文章？打赏一下作者吧

    评论

    最新文章

    ×