T25990 [Wind Festival]Running In The Sky

时间：2023-03-08 23:33:26
T25990 [Wind Festival]Running In The Sky

T25990 [Wind Festival]Running In The Sky

题目背景

[Night - 20:02[Night−20:02 P.M.]P.M.]

夜空真美啊……但是……快要结束了呢……

题目描述

一天的活动过后，所有学生都停下来欣赏夜空下点亮的风筝。 CurtisCurtis NishikinoNishikino 想要以更近的视角感受一下，所以她跑到空中的风筝上去了(这对于一个妹子来说有点匪夷所思)! 每只风筝上的灯光都有一个亮度 k_ik

i

​ . 由于风的作用，一些风筝缠在了一起。但是这并不会破坏美妙的气氛，缠在一起的风筝会将灯光汇聚起来，形成更亮的光源！

CurtisCurtis NishikinoNishikino 已经知道了一些风筝间的关系，比如给出一对风筝 (a,b)(a,b) , 这意味着她可以从 aa 跑到 bb 上去，但是不能返回。

现在，请帮她找到一条路径(她可以到达一只风筝多次，但只在第一次到达时她会去感受上面的灯光), 使得她可以感受到最多的光亮。同时请告诉她这条路径上单只风筝的最大亮度，如果有多条符合条件的路径，输出能产生最大单只风筝亮度的答案。

Tarjan缩点途中处理圈内最大值和圈内和，变成DAG然后dp就好

Code

#include<iostream>

#include<cstdio>

#include<queue>

#include<cstring>

#include<algorithm>

typedef long long LL;

using namespace std;

int RD(){

    int out = 0,flag = 1;char c = getchar();

    while(c < '0' || c >'9'){if(c == '-')flag = -1;c = getchar();}

    while(c >= '0' && c <= '9'){out = out * 10 + c - '0';c = getchar();}

    return flag * out;

    }

const int maxn = 1000019,INF = 1e9;

int head[maxn][2],nume;

struct Node{

    int v,dis,nxt;

    }E[maxn << 3][2];

void add(int u,int v,int dis,int o){

    E[++nume][o].nxt = head[u][o];

    E[nume][o].v = v;

    E[nume][o].dis = dis;

    head[u][o] = nume;

    }

int num,nr,v[maxn];

int DFN[maxn],LOW[maxn],INDEX;

int S[maxn],top;

bool ins[maxn];

int col[maxn],numc,vc[maxn],MAX[maxn];

void Tarjan(int u){

    DFN[u] = LOW[u] = ++INDEX;

    S[++top] = u;ins[u] = 1;

    for(int i = head[u][0];i;i = E[i][0].nxt){

        int v = E[i][0].v;

        if(!DFN[v]){Tarjan(v);LOW[u] = min(LOW[u],LOW[v]);}

        else if(ins[v])LOW[u] = min(LOW[u],DFN[v]);

        }

    if(DFN[u] == LOW[u]){

        numc++;

        while(S[top + 1] != u){

            col[S[top]] = numc;

            vc[numc] += v[S[top]];

            MAX[numc] = max(MAX[numc],v[S[top]]);

            ins[S[top--]] = 0;

            }

        }

    }

int fam[maxn];

int dp[maxn];

int DP(int u){

    if(dp[u] > 0)return dp[u];

    dp[u] = vc[u];int now = 0;

    for(int i = head[u][1];i;i = E[i][1].nxt){

        int v = E[i][1].v;

        if(DP(v) > now){

            now = DP(v);

            fam[u] = fam[v];

            }

        }

    dp[u] += now;

    fam[u] = max(fam[u],MAX[u]);

    return dp[u];

    }

int main(){

    num = RD();nr = RD();

    for(int i = 1;i <= num;i++)v[i] = RD();

    for(int i = 1;i <= nr;i++){

        int u = RD(),v = RD();

        add(u,v,1,0);

        }

    for(int i = 1;i <= num;i++)if(!DFN[i])Tarjan(i);

    for(int u = 1;u <= num;u++){

        for(int i = head[u][0];i;i = E[i][0].nxt){

            int v = E[i][0].v;

            if(col[u] != col[v])add(col[v],col[u],1,1);

            }

        }

    int ans = 0,maxx = 0;

    for(int i = 1;i <= numc;i++){

        int cmp = DP(i);

        if(cmp > ans){

            ans = cmp;

            maxx = fam[i];

            }

        else if(cmp == ans)maxx = max(maxx,fam[i]);

        }

    printf("%d %d\n",ans,maxx);

    return 0;

    }

Upd 两分钟以后

其实之前结构体的写法是完全没有错的！！！，学会了重载，这里贴一下

#include<iostream>

#include<cstdio>

#include<queue>

#include<cstring>

#include<algorithm>

typedef long long LL;

using namespace std;

int RD(){

    int out = 0,flag = 1;char c = getchar();

    while(c < '0' || c >'9'){if(c == '-')flag = -1;c = getchar();}

    while(c >= '0' && c <= '9'){out = out * 10 + c - '0';c = getchar();}

    return flag * out;

    }

const int maxn = 1000019,INF = 1e9;

int head[maxn][2],nume;

struct Node{

    int v,dis,nxt;

    }E[maxn << 3][2];

void add(int u,int v,int dis,int o){

    E[++nume][o].nxt = head[u][o];

    E[nume][o].v = v;

    E[nume][o].dis = dis;

    head[u][o] = nume;

    }

int num,nr,v[maxn];

int DFN[maxn],LOW[maxn],INDEX;

int S[maxn],top;

bool ins[maxn];

int col[maxn],numc,vc[maxn],MAX[maxn];

void Tarjan(int u){

    DFN[u] = LOW[u] = ++INDEX;

    S[++top] = u;ins[u] = 1;

    for(int i = head[u][0];i;i = E[i][0].nxt){

        int v = E[i][0].v;

        if(!DFN[v]){Tarjan(v);LOW[u] = min(LOW[u],LOW[v]);}

        else if(ins[v])LOW[u] = min(LOW[u],DFN[v]);

        }

    if(DFN[u] == LOW[u]){

        numc++;

        while(S[top + 1] != u){

            col[S[top]] = numc;

            vc[numc] += v[S[top]];

            MAX[numc] = max(MAX[numc],v[S[top]]);

            ins[S[top--]] = 0;

            }

        }

    }

int ing[maxn],outg[maxn];

struct Dp{

    int sum,maxx;

    Dp (int sum,int maxx):sum(sum), maxx(maxx){}

    Dp(){}

    bool operator > (const Dp &a)const{

        if(a.sum != sum)return sum > a.sum;

        return maxx > a.maxx;

        }

    Dp operator + (const Dp &a){

        Dp ans;

        ans.sum = sum + a.sum;

        ans.maxx = max(maxx,a.maxx);

        return ans;

        }

    }dp[maxn];

Dp DP(int u){

    if(dp[u].sum > 0)return dp[u];

    dp[u] = Dp(vc[u],MAX[u]);

    Dp max = dp[u];

    for(int i = head[u][1];i;i = E[i][1].nxt){

        int v = E[i][1].v;

        Dp temp = DP(v);

        if(temp + dp[u] > max)max = temp + dp[u];

        }

    dp[u] = max;

    return dp[u];

    }

int main(){

    num = RD();nr = RD();

    for(int i = 1;i <= num;i++)v[i] = RD();

    for(int i = 1;i <= nr;i++){

        int u = RD(),v = RD();

        add(u,v,1,0);

        }

    for(int i = 1;i <= num;i++)if(!DFN[i])Tarjan(i);

    for(int u = 1;u <= num;u++){

        for(int i = head[u][0];i;i = E[i][0].nxt){

            int v = E[i][0].v;

            if(col[u] != col[v])add(col[v],col[u],1,1);

            }

        }

    Dp ans = Dp(0,0);

    for(int i = 1;i <= numc;i++){

        if(DP(i) > ans)ans = DP(i);

        }

    //for(int i = 1;i <= numc;i++)printf("col=%d,sum=%d,max=%d\n",i,dp[i].sum,dp[i].maxx);

    printf("%d %d\n",ans.sum,ans.maxx);

    //printf("judge=%d\n",Dp(100000,10000) > Dp(0,0));

    return 0;

    }

相关文章