首页 > 代码库 > 遇见（dj+并查集）

遇见（dj+并查集）

2024-08-17 16:43:45   220人阅读

题4  遇见

【故事背景】

    聪聪是个非常单纯的小朋友。有一天他在食堂打饭的时候遇见了一位绝世MM，立刻就被吸引住了。正当他想上前搭讪的时候，天空突然黑了，一个巨大的蚕宝宝从天而降，竟然把该MM吃了下去！蚕宝宝狂笑着对聪聪说：“这个MM，你给她东西吃，她就吃，你不给她吃，她自己就死掉了是吧？我已经把她藏到了我体内的最深处，再过不久她就饿死了！聪聪当然不会放过这个英雄救美的机会，于是他立刻施展法术，进入蚕宝宝体内去营救MM ！ 

【问题描述】 

    进入蚕宝宝体内后，聪聪发现蚕宝宝的身体是一个含有N个结点的有向图。聪聪所在的位置为1号结点，MM所在的位置为N号结点。两个结点之间可能会有多条路，通过每条路都需要一定的时间。另外，聪聪还发现这个迷宫中有一些隐藏的双向道路，通过隐藏道路不需要花费任何时间。当然，两个结点之间可能有不止一条隐藏道路。无论是普通道路还是隐藏道路，当聪聪第一次通过时能获得一定数量的金币。聪聪现在从1号结点出发，要到MM所在的N号结点。聪聪虽然救MM心切，但他也希望能多拿走一些金币，所以现在你的目标是：在保证所需时间最小的前提下，拿走最多的金币。 

【输入格式】 

    输入文件meet.in包含M2+M1+1行。 

    第1行包含三个正整数N、M1、M2，分别表示结点总数、普通道路与隐藏道路的数量。 

    第2行到M2+1行，每行包含三个正整数A、B、C，表示有一条连接A和B的隐藏道路，该道路上的金币数为C。 

    第M2+2行到M2+M1+1行，每行包含四个正整数A、B、C、D，表示有一条从A到B的普通道路，这条路上的金币数为C，通过这条路所需花费的时间为D。 

【输出格式】 

输出文件meet.out只包含1行，依次输出最优方案所需的时间和金币数，中间用一个空格分开。 

【输入输出样例】 

meet.in

meet.out

4 4 1

2 3 5

1 2 8 2

3 2 5 2

3 4 6 6

1 4 10 9

8 19

【样例解释】 

    最优路线为1→2→3→4，其中2→3是隐藏道路。 

【数据规模和约定】 

    对于10%的数据，N≤10，M1≤8，M2=0。 

    对于30%的数据，N≤1000，M1≤50000，M2=0。 

    对于50%的数据，N≤10000，M1≤200000，M2=0。 

    对于另外30%的数据，N≤2000，M1≤60000，M2≤200。 

    对于全部的数据，N≤10000，M1≤200000，M2≤1000。 

    通过每条普通道路所需的时间和通过每条道路所获得的金币数均不超过100。 

    保证不会出现无解的情况，即至少存在一条从结点1通向结点N的路径。

对于M2=0的情况，可以直接用dijkstra求最优解；（因使用路径的长度和金币判断）

对于有隐藏路径的情况，因为不花费时间，所以其上面的金币不拿白不拿，并且还可以不费时间达到另一个点。

所以我们可以将隐藏路径的点加入并查集中，之后连接普通边时直接连到祖先上，之后再求最短路即可。

（dijkstra要用优化版）

 

#include<cstdio>
#include<cstring>
#include<queue>
#define N 10005
using namespace std;
struct X
{
    int v,q,j,f,n;
}x[200005];
struct E
{
    int v,q,j;
    bool operator<(const E &A)const
    {
        if(q>A.q) return 1;
        if(q<A.q) return 0;
        return j<A.j;
    }
};
priority_queue <E> qq;
int fa[N],go[N],d[N],mo[N];
int read()
{
    char c;
    while((c=getchar())<‘0‘||c>‘9‘);
    int re=c-‘0‘;
    while((c=getchar())>=‘0‘&&c<=‘9‘)
        re=(re<<1)+(re<<3)+c-‘0‘;
    return re;
}
int find(int a)
{
    int b=a;
    while(fa[a]) a=fa[a];
    while(fa[b]&&fa[b]!=a)
    {
        int t=fa[b];
        fa[b]=a;go[b]+=go[t];
        b=t;
    }
    return a;
}
void dij()
{
    int s=find(1);
    memset(d,0x3f,sizeof(d));
    d[s]=0;qq.push((E){s,0,go[s]});
    go[s]=0;
    while(!qq.empty())
    {
        E t=qq.top();qq.pop();
        for(int i=x[t.v].f;i;i=x[i].n)
            if(t.q+x[i].q<d[x[i].v]||(t.q+x[i].q==d[x[i].v]&&mo[x[i].v]<go[x[i].v]+t.j+x[i].j))
            {
                d[x[i].v]=x[i].q+t.q;
                mo[x[i].v]=go[x[i].v]+t.j+x[i].j;
                //go[x[i].v]=0;
                qq.push((E){x[i].v,d[x[i].v],mo[x[i].v]});
            }
    }
}
int main()
{
    freopen("meet.in","r",stdin),freopen("meet.out","w",stdout);
    int n=read(),m1=read(),m2=read();
    while(m2--)
    {
        int u=find(read()),v=find(read()),j=read();
        if(u!=v) fa[v]=u,go[u]+=go[v],go[v]=0;
        go[u]+=j;
    }
    for(int i=1;i<=m1;i++)
    {
        int u=find(read());
        x[i].v=find(read());
        x[i].j=read();
        x[i].q=read();
        x[i].n=x[u].f;
        x[u].f=i;
        if(u==x[i].v)
        {
            x[i].v=0;
            x[u].f=x[i].n;
            x[i].q=0;
            x[i].j=0;
            x[i].n=0;
            continue;
        }
    }
    dij();
    printf("%d %d",d[n=find(n)],mo[n]);
    fclose(stdin),fclose(stdout);
    return 0;
}

 

遇见（dj+并查集）


联系
我们