洛谷P3387【模板】缩点
思路：
虽然是缩点模板题，但是明显感觉比同一个题单中的其他题都难。 题目思路已经提供给你:Tarjan缩点+DAGdp。就是用Tarjan缩点，重新建图之后，边拓扑排序边建边。 Tarjan DAGdp
代码：
#include<bits/stdc++.h>
#define pii pair<int,int>
#define ll long long
#define cl(x,y) memset(x,y,sizeof(x))
#define ct cerr<<"Time elapsed:"<<1.0*clock()/CLOCKS_PER_SEC<<"s.\n";
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define lson x<<1,l,mid
#define rson x<<1|1,mid+1,r
#define INF 1e18
const int N
=1e6+10;
const int mod
=1e9+7;
const int inf
=0x3f3f3f3f;
const double eps
=1e-8;
const double pi
=acos(-1);
using namespace std
;
int w
[N
],dfn
[N
],low
[N
],num
=0,fa
[N
],n
,in
[N
]={0},dp
[N
]={0},vis
[N
]={0},w2
[N
]={0};
vector
<int> e1
[N
],e2
[N
];
stack
<int> s
;
void tarjan(int x
)
{
dfn
[x
]=low
[x
]=++num
;
s
.push(x
);
vis
[x
]=1;
int i
;
for(i
=0;i
<e1
[x
].size();i
++)
{
int y
=e1
[x
][i
];
if(!dfn
[y
])
{
tarjan(y
);
low
[x
]=min(low
[x
],low
[y
]);
}
else if(vis
[y
])
low
[x
]=min(low
[x
],dfn
[y
]);
}
if(low
[x
]==dfn
[x
])
{
int pre
;
do
{
pre
=s
.top();
s
.pop();
vis
[pre
]=0;
w2
[x
]+=w
[pre
];
fa
[pre
]=x
;
}while(pre
!=x
);
}
}
int topo()
{
int i
;
queue
<int> q
;
for(i
=1;i
<=n
;i
++)
if(fa
[i
]==i
)
{
dp
[i
]=w2
[i
];
if(in
[i
]==0)
q
.push(i
);
}
while(!q
.empty())
{
int u
=q
.front();
q
.pop();
for(i
=0;i
<e2
[u
].size();i
++)
{
int v
=e2
[u
][i
];
dp
[v
]=max(dp
[v
],dp
[u
]+w2
[v
]);
in
[v
]--;
if(in
[v
]==0)
q
.push(v
);
}
}
int ans
=0;
for(i
=1;i
<=n
;i
++)
if(fa
[i
]==i
)
ans
=max(ans
,dp
[i
]);
return ans
;
}
int main()
{
ios
::sync_with_stdio(false);
cin
.tie(0);cout
.tie(0);
int m
,i
,j
;
cin
>>n
>>m
;
for(i
=1;i
<=n
;i
++)
{
fa
[i
]=i
;
cin
>>w
[i
];
}
for(i
=1;i
<=m
;i
++)
{
int u
,v
;
cin
>>u
>>v
;
e1
[u
].pb(v
);
}
for(i
=1;i
<=n
;i
++)
if(!dfn
[i
])
tarjan(i
);
for(i
=1;i
<=n
;i
++)
for(j
=0;j
<e1
[i
].size();j
++)
{
int v
=e1
[i
][j
];
if(fa
[i
]==fa
[v
])
continue;
else
{
e2
[fa
[i
]].pb(fa
[v
]);
in
[fa
[v
]]++;
}
}
cout
<<topo()<<endl
;
return 0;
}
