利内罗女士准备来到意大利进行修行。
意大利由 n 个城市和 m 条道路构成，道路是双向的。
到达第 i 个城市时，她可以取得该城市的全部信仰，并获得 ai 点能力提升，但因为在一个城市可以
取得的信仰有限，多次到达同一个城市不会多次提升能力。
意大利对能力也有很严的要求，对于第 i 条道路，只有能力大于等于 bi 的人才能经过。
利内罗女士准备乘坐飞机去往意大利，飞机可以降落在任意城市（即可以在任意城市开始修行），她
想知道自己的能力最多可以成长为多少。
她提出了 Q 次询问，表示当自己初始能力为 qi 时，能力最多可以成长为多少。

Input

第一行三个整数 n, m, Q。接下来一行 n 个非负整数，a1 到 an。
接下来 m 行，每行三个正整数，ui, vi, bi，表示城市 ui 和城市 vi 之间有一条道路。
最后 Q 行，每行一个非负整数 qi。

Output

Q 行，每行一个整数表示答案。

Notes
对于所有数据，满足 n, Q ≤ 105, m ≤ 2 ∗ 105, ai ≤ 104, qi, bi ≤ 109
Task1[20%]

n ≤ 5 , m ≤ 10 , Q =1

Task2[30%]
n ≤ 50 , m ≤ 100 , Q ≤ 5

Task3[40%]

n ≤ 100 , m ≤ 200 , Q ≤5

Task4[50%]
n ≤ 300 , m ≤ 600 , Q ≤ 100

Task5[60%]

n ≤ 1000 , m ≤ 2000 , Q ≤ 10

Task6[100%]
无特殊限制
Subtask1[10pts]
n ≤ 1000 , m = n − 1 , Q ≤ 1000，图保证联通
Subtask2[10pts]
m = n − 1，图保证联通0

题意：对于一个有向图，求一条通过点值最大的路径，通过每条边需要一定大小要求。

思路：第一篇博客就已经声明过的：本人蒟蒻，奔着提高省3去的，所以显然，此题只能暴搜。

据出题人说，此题求连通块加个并查集维护即可，时间复杂度 O((n + m + q)log n)。我当然不会，看诸位大佬懂不懂。

见暴搜代码：

#include<bits/stdc++.h>

using namespace std;

const int inf=0x3f3f3f3f;

int a[],n,m,bi,q,ui[],vi[],b[][],ans,qi,sum=;

bool road[][],place[];

void dfs(int x)

{

    if(place[x]==false)

    {

        ans=ans+a[x];

        place[x]=true;

    }

    if(ans>sum)

    sum=ans;

    for(int i=;i<=n;i++)

    {

        if(i==x)

        continue;

        else if(road[x][i]==true&&ans>=b[x][i])

        {

            road[x][i]=false;

            road[i][x]=false;

            dfs(i);

        }

    }

    ans=ans-a[x];

}

int main()

{

    cin>>n>>m>>q;

    for(int i=;i<=n;i++)

    cin>>a[i];

    for(int i=;i<=m;i++)

    {

        cin>>ui[i]>>vi[i]>>bi;

        b[ui[i]][vi[i]]=bi;

        b[vi[i]][ui[i]]=bi;

    }

    for( int i=;i<=q;i++)

    {

        cin>>qi;

        ans=qi;

        for(int j=;j<=n;j++)

        {

            memset(road,false,sizeof(road));

            memset(place,false,sizeof(place));

            for(int i1=;i1<=m;i1++)

            {

                road[ui[i1]][vi[i1]]=true;

                road[vi[i1]][ui[i1]]=true;

            }

            dfs(j);

        }

        cout<<sum<<endl;

    }

    fclose(stdin);

    fclose(stdout);

    return ;

}

巴特西

嵊州普及Day3T4

Input

Output

好题哉!!!

最新文章

热门文章