【图论】最短路算法题解1

51nod 1459 迷宫游戏

题目描述

给定n个点，m条边，起点，终点，每个点有一个点权，给出走每条边所需的时间。
要求从起点尽快到达终点，使得获得的点权之和最大，输出最大得分。

题解

在dijkstra算法中增加一个判断，从u到v的距离更新时，若有d[v]==d[u]+cost[u][v]，更新v的值。

#include<cstdio>
#include<map>
#include<queue>
#include<iostream>
#include<vector>
using namespace std;

typedef pair<int,int> P;
const int maxm=250000;
const int maxn=502;
const int INF=1e9;
int n,m,start,end;
int head[maxn];
int d[maxn],val[maxn],score[maxn];
int pos;
int pre[maxn];

struct node{
    int to,next,cost;
}e[maxm];

void add(int x,int y,int z)
{
    e[++pos].to=y;
    e[pos].cost=z;
    e[pos].next=head[x];
    head[x]=pos;
}
int ans;
map<int,int> mp;

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

void dijstra(int s)
{
    for(int i=0;i<n;i++) d[i]=INF;
    d[s]=0;
    q.push(P(0,s));
    while(!q.empty())
    {
        P p=q.top();q.pop();
        int v=p.second;
        if(d[v]<p.first) continue;
        for(int i=head[v];i;i=e[i].next)
        {
            if(d[e[i].to]>d[v]+e[i].cost)
                d[e[i].to]=d[v]+e[i].cost,score[e[i].to]=score[v]+val[e[i].to],q.push(P(d[e[i].to],e[i].to));
            else if(d[e[i].to]==d[v]+e[i].cost)
            {
                score[e[i].to]=max(score[e[i].to],score[v]+val[e[i].to]);
            }
        }
    }
}

int main()
{
    scanf("%d%d%d%d",&n,&m,&start,&end);
    for(int i=0;i<n;i++) scanf("%d",&val[i]),score[i]=val[i];
    for(int i=0;i<m;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z),add(y,x,z);
    }
    dijstra(start);
    printf("%d %d\n",d[end],score[end]);
    return 0;
}

51nod 1366 贫富差距

题目描述

给出n个人的朋友关系，要求朋友之间的存款额之差不能大于d，要求所有点中存款额极差的可能值。若这个值为无穷大，输出-1.

输入样例

3

3 10

NYN

YNY

NYN

2 1

NN

NN

6 1000

NNYNNN

NNYNNN

YYNYNN

NNYNYY

NNNYNN

NNNYNN

输出样例

20

-1

3000

题解

即要求图中每条边所连端点的值不大于d，根据贪心，可以把每条边边权定为d，这样求出的极差有最大值（有限或无穷大）。
显然，若图中连通块数大于1，则为无穷大，若等于1，则用Floyd算法求解。答案为max{d[i][j]}。

#include<bits/stdc++.h>
using namespace std;

const int maxn=55;
const int maxm=3000;
const int INF=1e9;
int pos,mx;
int N,d;
int t;
char g[maxn][maxn];
int dis[maxn][maxn];
int fa[maxn];
bool root[maxn];

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

void unite(int x,int y)
{
    if(find(x)==find(y)) return;
    int fax=fa[x],fay=fa[y];
    fa[fax]=fay;
}

void floyd()
{
    for(int k=0;k<N;k++)
        for(int i=0;i<N;i++)
            for(int j=0;j<N;j++)
                if(dis[i][j]>dis[i][k]+dis[k][j]) dis[i][j]=dis[i][k]+dis[k][j];
}

int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&N,&d);
        for(int i=0;i<N;i++) fa[i]=i;
        for(int i=0;i<N;i++)
            scanf("%s",g[i]);
        for(int i=0;i<N;i++)
            for(int j=0;j<N;j++)
                if(i==j||g[i][j]=='Y')
                {
                    dis[i][j]=d;
                    unite(i,j);
                } 
                else dis[i][j]=INF;
        for(int i=0;i<N;i++) root[i]=false;
        for(int i=0; i<N; i++)  root[find(i)] = true;
        int res = 0;
        for(int i=0; i<N; i++)
        if(root[i]) res++;
        if (res>1)
        {
            cout << "-1\n";
            continue;
        }
        floyd();
        for(int i=0;i<N;i++) 
            for(int j=0;j<N;j++)
                mx=max(mx,dis[i][j]);
        if(mx==INF) printf("-1\n");else printf("%d\n",mx);
        mx=0;
    }
    return 0;
} 

51nod 1693 水群

题目描述

记num0为对话框中表情数，num1为剪贴板中表情数。

当前对话框内有一个表情，接下来可以进行三种操作：

op1：全选复制。把对话框内所有表情复制到粘贴板中，num1=num0；

op2：粘贴。num0+=num1；

op3：退格。把对话框中最后一个表情删去。num0--。

问得到n个表情，最少需要的操作数。

输入样例

233

输出样例

17

题解

不难想到，若在粘贴k次后全选复制再粘贴，对应着从x到kx连一条权值为k的边，在每次复制粘贴操作结束后再进行退格，对应着从每个x向x-1连一条权值为1的边。跑一遍最短路算法，d[N]即为所求。
但对于连边(x,kx,k)，若k不作限制，则会有o(N^2)条边，显然行不通。
由此想到质因数分解定理，若只连(x,px,p)的边，则可以走到任意一个点i。
因此，添加所有px<n+m的边（m为一常数，用于进行范围估计），连所有x到x-1的边，即可求出d[n]。
通过提交发现，p只取前几个质数也可得到正解，以此减少空间和时间复杂度。

#include<bits/stdc++.h>
using namespace std;

typedef pair<int,int> P;
const int maxm=1e7;
const int maxn=1e6+10;
const int INF=1e9;
int n,pos,tot;
int head[maxn];
int isprime[maxn];
int d[maxn];
int p[maxn];
struct node{int to,next,cost;}e[maxm];

void add(int x,int y,int z) {
    e[++pos].next=head[x];
    e[pos].to=y;
    e[pos].cost=z;
    head[x]=pos;
}

void init()
{
    for(int i=2;i<maxn;i++) isprime[i]=1;
    for(int i=2;i<maxn;i++)if(isprime[i])
        for(int j=i+i;j<maxn;j+=i)
            isprime[j]=0;
    for(int i=2;i<=maxn;i++)
        if(isprime[i]) p[++tot]=i;
}

priority_queue<P,vector<P>,greater<P> > q;
bool vis[maxn];
void dij(int s)
{
    for(int i=1;i<=n+10;i++) d[i]=INF;
    q.push(P(0,s));
    d[s]=0;
    while(!q.empty())
    {
        P p=q.top();q.pop();
        int v=p.second;
        if(vis[v]||d[v]<p.first) continue;
        vis[v]=1;
        for(int i=head[v];i;i=e[i].next)
        {
            if(d[e[i].to]>d[v]+e[i].cost)
            {
                d[e[i].to]=d[v]+e[i].cost;
                q.push(P(d[e[i].to],e[i].to));
            }
        }
    }

int main()
{
    scanf("%d",&n); 
    init();
    for(int i=2;i<=n+20;i++) add(i,i-1,1);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=8&&p[j]*i<=n+10;j++)
            add(i,p[j]*i,p[j]);
    }
    dij(1);
    printf("%d\n",d[n]); 
    return 0;
}

【图论】最短路算法题解1

原文：https://www.cnblogs.com/JWizard/p/11742175.html