不同流派,恕我实在看不来……
by 薛裕龙 @ 2018-11-09 10:19:18
@[pipixue](/space/show?uid=49620) 码风还是vector
by 九头蛇 @ 2018-11-09 10:20:09
@[九头蛇](/space/show?uid=33634) 你用关键点跑拓扑,存边却直接用点存?
by 薛裕龙 @ 2018-11-09 10:21:48
```cpp
for(register int i=1;i<=n;i++)
for(register int j=0;j<a[i].size( );j++){
int u=i,v=a[i][j];
if(sd[u]!=sd[v]){
b[u].push_back(v);
in[v]++;
}
}
```
by 薛裕龙 @ 2018-11-09 10:22:21
应该是关键点之间减边吧
by 薛裕龙 @ 2018-11-09 10:24:25
@[pipixue](/space/show?uid=49620) 我好像知道了,容我想一下
by 九头蛇 @ 2018-11-09 10:24:28
```cpp
#include <bits/stdc++.h>
using namespace std;
int read( ){
int x=0,y=1;
char c=getchar( );
while(c>'9'||c<'0'){if(c=='-')y=-1;c=getchar( );}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar( );}
return x*y;
}
int n,m,w[10001];
bool vis[10001];
int dfn[10001],low[10001],stac[10001],top,num=1;
int sd[10001];
vector<int> a[10001];
vector<int> b[10001];
int in[10001],dist[10001];
void tarjian(int u)
{
dfn[u]=low[u]=num;
num++;
vis[u]=1;
stac[++top]=u;
for(register int i=0;i<a[u].size( );i++)
{
int v=a[u][i];
if(!dfn[v])
{
tarjian(v);
low[u]=min(low[u],low[v]);
}
else if(vis[v]) low[u]=min(low[u],dfn[v]);
}
if (dfn[u]==low[u])
{
int v;
while (v=stac[top--])
{
sd[v]=u;
vis[v]=0;
if (u==v) break;
w[u]+=w[v];
}
}
}
int topo()
{
queue <int> q;
int tot=0;
for (register int i=1;i<=n;i++)
if (sd[i]==i&&!in[i])
{
q.push(i);
dist[i]=w[i];
}
while (!q.empty( ))
{
int u=q.front( );q.pop( );
// for (int i=h[k];i;i=ed[i].next)
for(register int i=0;i<b[u].size( );i++)
{
// int v=ed[i].to;
int v=b[u][i];
dist[v]=max(dist[v],dist[u]+w[v]);
in[v]--;
if (in[v]==0) q.push(v);
}
}
int ans=0;
for (int i=1;i<=n;i++)
ans=max(ans,dist[i]);
return ans;
}
int main( ){
//freopen("1.in","r",stdin);
n=read( );m=read( );
for(register int i=1;i<=n;i++) w[i]=read( );
for(register int i=1;i<=m;i++){
int u,v;
u=read( );v=read( );
a[u].push_back(v);
}
for(register int i=1;i<=n;i++)
if(!dfn[i]) tarjian(i);
for(register int i=1;i<=n;i++)
for(register int j=0;j<a[i].size( );j++){
int u=i,v=a[i][j];
if(sd[u]!=sd[v]){
b[sd[u]].push_back(sd[v]);
in[sd[v]]++;
}
}
printf("%d",topo( ));
return 0;
}
```
by 薛裕龙 @ 2018-11-09 10:26:13
我用你的A了
by 薛裕龙 @ 2018-11-09 10:26:21
@[pipixue](/space/show?uid=49620) 哦哦,对的,存点错了,谢谢,应该存关键点的,谢谢啦
by 九头蛇 @ 2018-11-09 10:28:17