调了两天了,就是看不出来哪里有错误,在线求助(
不管我重构多少次代码,总是4,7两个点WA掉。。
另:我在tarjan函数后面发现有的点的"父亲"(即f数组)为0,所以在前面加了for循环。
我觉的我tarjan问题,但是又找不出来哪里有问题= =
#include <iostream>
#include <queue>
#include <stack>
using namespace std;
int n,m1,m2,timea;
int p[10001],h1[10001],h2[10001],f[10001],dfn[10001],low[10001];
stack<int> st;
int vis[10001],dp[10001],rd[10001];
struct Edge
{
int from,next,to;
};
Edge bian1[100001],bian2[100001];
void add1(int x,int y,int id)
{
bian1[id].from=x;
bian1[id].to=y;
bian1[id].next=h1[x];
h1[x]=id;
}
void add2(int x,int y)
{
m2++;
bian2[m2].from=x;
bian2[m2].to=y;
bian2[m2].next=h2[x];
h2[x]=m2;
rd[y]++;
}
void tarjan(int x)
{
timea++;
dfn[x]=low[x]=timea;
st.push(x);
int i,j;
for (i=h1[x];i;i=bian1[i].next)
{
j=bian1[i].to;
if (dfn[j]==0)
{
tarjan(j);
low[x]=min(low[x],low[j]);
}
else
low[x]=min(low[x],dfn[j]);
}
if (dfn[x]==low[x])
{
while (st.top()!=x)
{
p[x]+=p[st.top()];
f[st.top()]=x;
st.pop();
}
f[x]=x;
st.pop();
}
}
void lb()
{
int i;
for (i=1;i<=m1;i++)
{
if (f[bian1[i].from]!=f[bian1[i].to])
add2(f[bian1[i].from],f[bian1[i].to]);
}
}
int topo()
{
queue<int> Q;
int i;
for (i=1;i<=n;i++)
if (f[i]==i&&rd[i]==0)
{
Q.push(i);
dp[i]=p[i];
}
while (!Q.empty())
{
int k=Q.front();
Q.pop();
for (i=h2[k];i;i=bian2[i].next)
{
dp[bian2[i].to]=max(dp[bian2[i].to],dp[k]+p[bian2[i].to]);
rd[bian2[i].to]--;
if (rd[bian2[i].to]==0)
Q.push(bian2[i].to);
}
}
int ans=0;
for (i=1;i<=n;i++)
ans=max(ans,dp[i]);
return ans;
}
int main()
{
cin>>n>>m1;
int i,x,y;
for (i=1;i<=n;i++)
cin>>p[i];
for (i=1;i<=m1;i++)
{
cin>>x>>y;
add1(x,y,i);
}
for (i=1;i<=n;i++)
f[i]=i;
for (i=1;i<=n;i++)
if (!dfn[i])
tarjan(i);
lb();
cout<<topo();
return 0;
}