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;
}