解题报告 P1119 灾后重建

题目内容

P1119

大意:给定编号从 1n-1 的村庄,每个村庄都被一定程度上损毁,而公路正常,在 t_i 时间前 i 号村庄不能通过,询问在 t 时间时 x 号和 y 号村庄能不能通车,如果能,最短路径是多少。

解题思路

这题思路真的很妙,让我们对 Floyd 的本质有了更深的理解,至少本蒟蒻是这样觉得的。

回归 Floyd 算法的本质:

for(int k=1;k<=n;k++)
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            f[i][j]=min(f[i][j],f[i][k]+f[k][j])

实际上,Floyd 是通过枚举中转点 k 来求得每个点之间的最短路,本质上是一种 dp。

然后,注意到本题中,每个村庄的恢复时间是递增的,且给出的询问的时间也是递增的。而题目让我们求任意两点的最短路,那么也可以抽象成 Floyd。具体的方法就是,由于时间是递增的,所以每到一个村庄恢复的时间点我们就可以让这个村庄成为那个可以用来中转的 k 来更新这一时间的所有最短路。

在这题中,就是使用时间戳,保证回答被询问的时间前信息被更新过即可。注意村庄编号从 0 开始

#include <cstdio>
#include <cctype>
#include <cstring>

inline int read()
{
    char c = getchar();
    int s = 0;
    while (!isdigit(c))
        c = getchar();
    while (isdigit(c))
        s = 10 * s + c - '0', c = getchar();
    return s;
}

inline int min(int a,int b)
{
    return a<b?a:b;
}

const int maxn=205;
int n,m,t[maxn],f[maxn][maxn],q;

inline void floyd(int k)//更新信息的,通过给定可以中转的中转点来进行更新
{
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
    return;
}

int main()
{
    n=read(),m=read();
    memset(f,0x3f,sizeof(f));//初始赋极大值 0x3f 不至于加起来爆int
    for(int i=0;i<n;i++)
        t[i]=read(),f[i][i]=0;
    while(m--)
    {
        int x=read(),y=read(),w=read();
        f[x][y]=f[y][x]=w;//双向边
    }
    q=read();
    int now=0;
    while(q--)
    {
        int x=read(),y=read(),s=read();
        while(t[now]<=s && now<n)//将这一时间前的所有时间信息更新
            floyd(now++);
        if(t[x]>s || t[y]>s || f[x][y]>=0x3f3f3f3f)//如果这一时间时村庄未修复,或者无路线
            printf("-1\n");//输出 -1
        else
            printf("%d\n",f[x][y]);//否则输出最短路即可
    }
    return 0;
}

解题报告 P4568 [JLOI2011]飞行路线

题目内容

P4568

大意:n 个城市 m 条航线,可以免费掉最多 k 条航线,求从 st 的最少花费。

解题思路

分层图最短路模板,将图分成 k+1 层处理,每层之间照常连航线的边,跨层连免费航线,跑一遍最短路然后统计答案就可以了。每往下一层就相当于免费搭了一次飞机。

spfa 会被卡

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

const int maxn=1e4+5;

struct edge
{
    int to,dist;
    edge(){}
    edge(int b,int c)
    {
        to=b,dist=c;
    }
};

vector<edge> g[maxn*11];
int n,m,k,s,t;
queue<int> q;
bool vis[maxn*11];//记得空间开够
int d[maxn*11];

void ins(int u,int v,int w)
{
    g[u].push_back(edge(v,w));
    return;
}

void dij()//跑dij
{
    priority_queue<pair<int,int>, vector<pair<int,int> >,greater<pair<int,int> > > q;
    memset(d,0x3f3f3f3f,sizeof(d));
    d[s]=0;
    q.push(make_pair(0,s));
    while(!q.empty())
    {
        int now=q.top().second;
        q.pop();
        if(!vis[now])
        {
            vis[now]=1;
            for(auto &e:g[now])
            {
                if(d[e.to]>d[now]+e.dist)
                {
                    d[e.to]=d[now]+e.dist;
                    q.push(make_pair(d[e.to],e.to));
                }
            }
        }
    }
    return;
}

int main()
{
    scanf("%d %d %d",&n,&m,&k);
    scanf("%d %d",&s,&t);
    register int a,b,c;
    for(int i=1;i<=m;i++)
    {
        scanf("%d %d %d",&a,&b,&c);
        for(int j=0;j<=k;j++)//每层中间连
        {
            ins(a+n*j,b+n*j,c);
            ins(b+n*j,a+n*j,c);
            if(j<k)//跨层连
            {
                ins(a+n*j,b+(j+1)*n,0);
                ins(b+n*j,a+(j+1)*n,0);
            }
        }
    }
    dij();
    int ans=0x3f3f3f3f;
    for(int i=0;i<=k;i++)
        ans=min(ans,d[i*n+t]);
    printf("%d\n",ans);
    return 0;
}

解题报告 P1073 最优贸易 【NOIP2009TGT3】

题目内容

P1073

大意:一个商人在一个国家(n个城市m条路)游玩,每到一个城市可以选择买入或者卖出物品,贸易只进行一次,从1出发,到n结束,求最大获利

解题思路

嗯,遇到这种贸易问题,可以抽象成图来看。

商人完整的贸易过程分为三个部分:出发到买入,买入到卖出,卖出到结束

可以使用分层图的思想,将整张图复制为三份,然后在第一层到第二层每个点之间连边,边权为该点的物价,在第二层到第三层之间每个点连边,边权为物价的相反数。然后每一层中间城市的道路边权都为0,因为在城市间移动不需要费用。

对于商人的移动,层内的对应的是正常移动,跨层的是买卖操作,求出从第一层的1号节点到第三层的n节点的最短路再取相反数即可。

代码细节

首先,由于负权边的存在,最短路的算法要使用SPFA,实现的细节不再赘述。

其次,分层图的表示,使用的是1\~n号代表第一层,n+1\~2n号代表第二层,2n+1~3n号代表第三层。对于每一个节点编号为i,权值为c_i的节点,需要添加边(i,n+i)=c_i(n+i,2n+i)=-c_i

至于城市间道路的添加,需要在三层图上都分别添加,注意双向边的存在。

多层图的节点切记不是2*n或3*n,我第一次打的时候就因为这个spfa陷入了死循环

注意如果商人不能获得优惠的话就不进行贸易输出0

代码

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

const int maxn=1e5+5;

struct edge
{
    int from,to,dist;
    edge(){}
    edge(int u,int v,int w)
    {
        from=u,to=v,dist=w;
    }
};

vector<edge> g[maxn*3];//开空间的时候maxn要乘上3
queue<int> q;
bool inq[maxn*3];
int d[maxn*3];
int n,m;

void ins(int u,int v,int w)
{
    g[u].push_back(edge(u,v,w));
    return;
}

int spfa()
{
    memset(d,0x3f3f3f3f,sizeof(d));
    q.push(1);
    inq[1]=true;
    d[1]=0;
    while(!q.empty())
    {
        int now=q.front();
        q.pop();
        inq[now]=false;
        for(auto &e:g[now])
        {
            int to=e.to, dist=e.dist;
            if(d[now]+dist<d[to])
            {
                d[to]=d[now]+e.dist;
                if(!inq[to])
                {
                    inq[to]=true;
                    q.push(to);
                }
            }
        }
    }
    return d[n+(n<<1)];//返回值是到终点的最小值
}

int main()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        int k;
        scanf("%d",&k);
        ins(i,i+n,k);//记得加边
        ins(i+n,i+(n<<1),-k);//第二,三层之间边权是负的
    }
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        scanf("%d %d %d",&u,&v,&w);
        ins(u,v,0);//三层边都要加上
        ins(u+n,v+n,0);
        ins(u+(n<<1),v+(n<<1),0);
        if(w==2)//如果是双向边的话也要加上
        {
            ins(v,u,0);
            ins(v+n,u+n,0);
            ins(v+(n<<1),u+(n<<1),0);
        }
    }
    int ans=spfa();
    //这里如果ans小于0,说明能获利,否则不能获利就不进行贸易,输出0
    printf("%d\n",ans<0?-ans:0);
    return 0;
}

解题报告 P1629 邮递员送信

题目内容

P1629

大意:有一邮递员送信,邮局为1节点,每次只能送1封,道路为单向,每条路需一定时间通过,求送完n-1封信要多长时间

解题思路

将这座城市抽象成一张图,可以发现每条路需通过的时间就是边的权值,求单源最短路即可。

但是:

注意到道路是单向的,所以邮递员不可能原路返回,这就是我犯的第一个错误(还好样例都没过,不然gg)

那怎么办,难道求1到所有点的最短路,再求所有点到1的最短路?显然不可能,复杂度爆炸,虽然Floyd优化之后可以勉强过,所以肯定有其他办法,就是

反向建图

将正常图的最短路算一遍,再将所有道路都反向了的反向图算一遍,两者加起来就是最终答案。

那反向图怎么建呢?

可以按照通常dij的思路,直接将所有数组复制一遍,然后写两个dij函数。但是这样不便于查错和维护,所以我选择OOP。考虑将一张图封装成一个结构体,然后所有操作通过成员函数进行,这样的话方便维护而且代码量少一些。

具体实现细节见代码

#include <cstdio>
#include <queue>
#include <cstring>
#include <utility>
using namespace std;

const int maxn=1005;
int n,m;

struct edge//存储边的结构体
{
    int from,to,dist;
    edge(){}
    edge(int u,int v,int w)
    {
        from=u,to=v,dist=w;
    }
};

struct graph//这是定义的存储一张图的结构体
{
    vector<edge> g[maxn];//我使用vector存图
    priority_queue<pair<int,int>, vector<pair<int,int> >, greater<pair<int,int> > > q;//dij时使用的优先队列
    int d[maxn];//存储从1到每个节点的距离
    bool vis[maxn];//存储是否被访问过
    void ins(int u,int v,int w)//加入边操作
    {
        g[u].push_back(edge(u,v,w));
        return;
    }
    void dijkstra()//dij本体
    {
        memset(d,0x3f3f3f3f,sizeof(d));
        memset(vis,false,sizeof(vis));
        d[1]=0;
        q.push(make_pair(0,1));
        while(!q.empty())
        {
            int now=q.top().second;
            q.pop();
            if(!vis[now])
            {
                vis[now]=true;
                for(auto &e:g[now])
                {
                    if(d[e.to]>d[now]+e.dist)
                    {
                        d[e.to]=d[now]+e.dist;
                        q.push(make_pair(d[e.to],e.to));
                    }
                }
            }
        }
    }
}a,b;//定义两个图分别存储正向和反向

int main()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        scanf("%d %d %d",&u,&v,&w);
        a.ins(u,v,w);//记得正向存
        b.ins(v,u,w);//记得反向存
    }
    a.dijkstra(),b.dijkstra();//两边dij
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        ans+=a.d[i];
        ans+=b.d[i];
        //统计答案
    }
    printf("%d\n",ans);
    return 0;
}