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

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

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

    1.确定结点的意义

    2.确定边权的意义

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

    具体看以下的例子：

    1.热浪

    1129. 热浪 - AcWing题库

    题意：

    思路：

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

    Code:

    1. #include 
    2. using namespace std;
    3. const int mxn=1e4+10,mxe=1e4+10,mnf=0x3f3f3f3f;
    4. struct ty{
    5.     int to,next,w;
    6. }edge[mxe<<1];
    7. queue<int> q;
    8. int n,m,s,t,u,v,w,tot=0;
    9. int head[mxn],dis[mxn],vis[mxn];
    10. void add(int u,int v,int w){
    11.     edge[tot].w=w;
    12.     edge[tot].to=v;
    13.     edge[tot].next=head[u];
    14.     head[u]=tot++;
    15. }
    16. void init(){
    17.     tot=0;
    18.     for(int i=0;i<=n;i++){
    19.         head[i]=-1;
    20.         vis[i]=0;
    21.         dis[i]=mnf;
    22.     }
    23.     while(!q.empty()) q.pop();
    24. }
    25. void spfa(){
    26.     dis[s]=0;
    27.     vis[s]=1;
    28.     q.push(s);
    29.     while(!q.empty()){
    30.         int u=q.front();
    31.         q.pop();
    32.         vis[u]=0;
    33.         for(int i=head[u];~i;i=edge[i].next){
    34.             if(dis[edge[i].to]>dis[u]+edge[i].w){
    35.                 dis[edge[i].to]=dis[u]+edge[i].w;
    36.                 if(!vis[edge[i].to]){
    37.                     vis[edge[i].to]=1;
    38.                     q.push(edge[i].to);
    39.                 }
    40.             }
    41.         }
    42.     }
    43. }
    44. int main(){
    45.     ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    46.     cin>>n>>m>>s>>t;
    47.     init();
    48.     for(int i=1;i<=m;i++){
    49.         cin>>u>>v>>w;
    50.         add(u,v,w);
    51.         add(v,u,w);
    52.     }
    53.     spfa();
    54.     if(dis[t]==mnf) cout<<-1<<'\n';
    55.     else cout<'\n';
    56. }

    2.信使

    1128. 信使 - AcWing题库

    题意：

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

    Code：

    1. #include 
    2. using namespace std;
    3. const int mxn=2e2+10,mxe=2e2+10,mnf=0x3f3f3f3f,inf=0xc0c0c0c0;
    4. struct ty{
    5.     int to,next,w;
    6. }edge[mxe<<1];
    7. queue<int> q;
    8. int n,m,x,y,w,tot=0;
    9. int head[mxn],dis[mxn],vis[mxn];
    10. void add(int u,int v,int w){
    11.     edge[tot].w=w;
    12.     edge[tot].to=v;
    13.     edge[tot].next=head[u];
    14.     head[u]=tot++;
    15. }
    16. void init(){
    17.     tot=0;
    18.     for(int i=0;i<=n;i++){
    19.         vis[i]=0;
    20.         head[i]=-1;
    21.         dis[i]=mnf;
    22.     }
    23.     while(!q.empty()) q.pop();
    24. }
    25. void spfa(){
    26.     dis[1]=0;
    27.     vis[1]=1;
    28.     q.push(1);
    29.     while(!q.empty()){
    30.         int u=q.front();
    31.         q.pop();
    32.         vis[u]=0;
    33.         for(int i=head[u];~i;i=edge[i].next){
    34.             if(dis[edge[i].to]>dis[u]+edge[i].w){
    35.                 dis[edge[i].to]=dis[u]+edge[i].w;
    36.                 if(!vis[edge[i].to]){
    37.                     q.push(edge[i].to);
    38.                     vis[edge[i].to]=1;
    39.                 }
    40.             }
    41.         }
    42.     }
    43. }
    44. int main(){
    45.     ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    46.     cin>>n>>m;
    47.     init();
    48.     for(int i=1;i<=m;i++){
    49.         cin>>x>>y>>w;
    50.         add(x,y,w);
    51.         add(y,x,w);
    52.     }
    53.     spfa();
    54.     int ans=inf;
    55.     for(int i=1;i<=n;i++){
    56.         if(dis[i]==mnf){
    57.             cout<<-1<<'\n';
    58.             return 0;
    59.         }
    60.         ans=max(ans,dis[i]);
    61.     }
    62.     cout<'\n';
    63. }

     3.香甜的黄油

    1127. 香甜的黄油 - AcWing题库

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

    Code：

    1. #include 
    2. using namespace std;
    3. const int mxn=2e3+10,mxe=2e3+10,mnf=0x3f3f3f3f;
    4. struct ty{
    5.     int to,next,w;
    6. }edge[mxe<<1];
    7. struct ty2{
    8.     int x,dis;
    9.     bool operator< (const ty2 &a) const{
    10.         return a.dis
    11.     }
    12. };
    13. unordered_map<int,int> mp;
    14. priority_queue q;
    15. int N,n,m,x,y,w,tot=0;
    16. int head[mxn],dis[mxn],vis[mxn];
    17. void add(int u,int v,int w){
    18.     edge[tot].w=w;
    19.     edge[tot].to=v;
    20.     edge[tot].next=head[u];
    21.     head[u]=tot++;
    22. }
    23. void init(){
    24.     tot=0;
    25.     mp.clear();
    26.     for(int i=0;i<=n;i++){
    27.         head[i]=-1;
    28.         dis[i]=mnf;
    29.         vis[i]=0;
    30.     }
    31.     while(!q.empty()) q.pop();
    32. }
    33. void init2(){
    34.     for(int i=0;i<=n;i++){
    35.         vis[i]=0;
    36.         dis[i]=mnf;
    37.     }
    38.     while(!q.empty()) q.pop();
    39. }
    40. int dij(int s){
    41.     init2();
    42.     dis[s]=0;
    43.     ty2 u;
    44.     u.dis=dis[s],u.x=s;
    45.     q.push(u);
    46.     while(!q.empty()){
    47.         ty2 u=q.top();
    48.         q.pop();
    49.         if(vis[u.x]) continue;
    50.         vis[u.x]=1;
    51.         for(int i=head[u.x];~i;i=edge[i].next){
    52.             if(vis[edge[i].to]) continue;
    53.             if(dis[edge[i].to]>dis[u.x]+edge[i].w){
    54.                 dis[edge[i].to]=dis[u.x]+edge[i].w;
    55.                 ty2 tmp;
    56.                 tmp.dis=dis[edge[i].to];
    57.                 tmp.x=edge[i].to;
    58.                 q.push(tmp);
    59.             }
    60.         }
    61.     }
    62.     int res=0;
    63.     for(int i=1;i<=n;i++){
    64.         if(mp[i]){
    65.             if(dis[i]==mnf) return mnf;
    66.             res+=dis[i]*mp[i];
    67.         }
    68.     }
    69.     return res;
    70. }
    71. int main(){
    72.     ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    73.     cin>>N>>n>>m;
    74.     init();
    75.     for(int i=1;i<=N;i++) cin>>x,mp[x]++;
    76.     for(int i=1;i<=m;i++){
    77.         cin>>x>>y>>w;
    78.         add(x,y,w);
    79.         add(y,x,w);
    80.     }
    81.     int ans=mnf;
    82.     for(int i=1;i<=n;i++){
    83.         ans=min(ans,dij(i));
    84.     }
    85.     cout<'\n';
    86. }

     4.最小花费

    1126. 最小花费 - AcWing题库

    题意：

    思路：

    转化为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：

    1. #include 
    2. using namespace std;
    3. const int mxn=2e3+10,mxe=1e5+10,mnf=0x3f3f3f3f;
    4. struct ty{
    5.     int to,next;
    6.     double w;
    7. }edge[mxe<<1];
    8. queue<int> q;
    9. int n,m,x,y,w,tot=0,s,t;
    10. int head[mxn],vis[mxn];
    11. double dis[mxn];
    12. void add(int u,int v,double w){
    13.     edge[tot].w=w;
    14.     edge[tot].to=v;
    15.     edge[tot].next=head[u];
    16.     head[u]=tot++;
    17. }
    18. void init(){
    19.     tot=0;
    20.     for(int i=0;i<=n;i++){
    21.         head[i]=-1;
    22.         vis[i]=0;
    23.     }
    24.     while(!q.empty()) q.pop();
    25. }
    26. double spfa(int u,int v){
    27.     dis[u]=1;
    28.     q.push(u);
    29.     while(!q.empty()){
    30.         int u=q.front();
    31.         q.pop();
    32.         vis[u]=0;
    33.         for(int i=head[u];~i;i=edge[i].next){
    34.             if(dis[edge[i].to]1.0-edge[i].w)){
    35.                 dis[edge[i].to]=dis[u]*(1.0-edge[i].w);
    36.                 if(!vis[edge[i].to]){
    37.                     vis[edge[i].to]=1;
    38.                     q.push(edge[i].to);
    39.                 }
    40.             }
    41.         }
    42.     }
    43.     return dis[t];
    44. }
    45. int main(){
    46.     //ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    47.     scanf("%d%d",&n,&m);
    48.     init();
    49.     for(int i=1;i<=m;i++){
    50.         scanf("%d%d%d",&x,&y,&w);
    51.         add(x,y,1.0*w/100);
    52.         add(y,x,1.0*w/100);
    53.     }
    54.     scanf("%d%d",&s,&t);
    55.     printf("%.8f\n",100/spfa(s,t));
    56. }

    5.最优乘车

    920. 最优乘车 - AcWing题库

    题意：

     思路：

    换乘次数=坐车次数-1

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

    首先先建图：

    结点就是公交车站

    边权意义就设成坐车次数

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

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

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

    Code：

    1. #include 
    2. using namespace std;
    3. const int mxn=5e2+10,mxe=5e2+10,mnf=0x3f3f3f3f;
    4. struct ty{
    5.     int to,next,w;
    6. }edge[mxe<<1];
    7. queue<int> q;
    8. string s;
    9. int m,n,len=0,p,tot=0;
    10. int a[mxn],head[mxn],dis[mxn],vis[mxn];
    11. void add(int u,int v,int w){
    12.     edge[tot].w=w;
    13.     edge[tot].to=v;
    14.     edge[tot].next=head[u];
    15.     head[u]=tot++;
    16. }
    17. void init(){
    18.     tot=0;len=0;
    19.     s.clear();
    20.     for(int i=0;i<=n;i++){
    21.         head[i]=-1;
    22.         dis[i]=mnf;
    23.     }
    24.     while(!q.empty()) q.pop();
    25. }
    26. void spfa(){
    27.     dis[1]=0;
    28.     vis[1]=1;
    29.     q.push(1);
    30.     while(!q.empty()){
    31.         int u=q.front();
    32.         q.pop();
    33.         vis[u]=0;
    34.         for(int i=head[u];~i;i=edge[i].next){
    35.             if(dis[edge[i].to]>dis[u]+edge[i].w){
    36.                 dis[edge[i].to]=dis[u]+edge[i].w;
    37.                 if(!vis[edge[i].to]){
    38.                     vis[edge[i].to]=1;
    39.                     q.push(edge[i].to);
    40.                 }
    41.             }
    42.         }
    43.     }
    44. }
    45. int main(){
    46.     ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    47.     cin>>m>>n;
    48.     init();
    49.     getline(cin,s);
    50.     for(int i=1;i<=m;i++){
    51.         len=0;
    52.         getline(cin,s);
    53.         stringstream ssin(s);
    54.         while(ssin>>p) a[++len]=p; 
    55.         for(int i=1;i<=len;i++){
    56.             for(int j=i+1;j<=len;j++){
    57.                 add(a[i],a[j],1);
    58.                 add(a[j],a[i],1);
    59.             }
    60.         }
    61.     }
    62.     spfa();
    63.     if(dis[n]==mnf) cout<<"NO"<<'\n';
    64.     else cout<'\n';
    65. }

    总结：

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

    1.确定结点的意义

    2.确定边权的意义

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

  • 相关阅读:
    Java Double byteValue()方法具有什么功能呢？
    C# 实现 Linux 视频聊天、远程桌面（源码，支持信创国产化环境，银河麒麟，统信UOS）
    JAVA毕业设计098—基于Java+Springboot的在线教育课程视频(源码+数据库)
    什么是video codec? video codec在实际业务的应用。
    pl/sql之各参数详解（“箱子模型“）
    缓存击穿、穿透、雪崩和布隆过滤器
    「C#」异步编程玩法笔记-Thread、ThreadPool、Task
    分类问题常用算法之决策树、随机森林及python实现
    ControlNet原理及应用
    互联网名词解释
  • 原文地址：https://blog.csdn.net/weixin_62528401/article/details/127942370