求助神犇P1113 ,第一份过了,第二份和第一份差不多,但样例都没过,帮忙找一下错误
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
int n, x, y, m;
struct graph {
queue<int> Q;
int rd[10005];
int tp[10005], ct, le[10005];
int ed[10005];
vector<int> E[10005];
void push(int x, int y) {
E[x].push_back(y);
rd[y]++;
}
void tuopu() {
for(int i = 1; i <= n; ++i) {
if(rd[i] == 0) Q.push(i);
}
ct = 0;
while(Q.size()) {
int nw = Q.front();
Q.pop();
tp[++ct] = nw;
for(int i = 0; i < E[nw].size(); ++i) {
rd[E[nw][i]]--;
if(rd[E[nw][i]] == 0) Q.push(E[nw][i]);
}
}
}
int mx[10005];
int work() {
for(int i = 1; i <= n; ++i) {
int x = tp[i];
ed[x] = mx[x] + le[x];
for(int j = 0; j < E[x].size(); ++j) {
mx[E[x][j]] = max(mx[E[x][j]], ed[x]);
}
}
int as = 0;
for(int i = 1; i <= n; ++i) as = max(as, ed[i]);
return as;
}
}G;
int main() {
scanf("%d", &n);
for(int i = 1; i <= n; ++i) {
scanf("%*d%d", &G.le[i]);
while(true){
scanf("%d", &y);
if(y == 0) break;
G.push(i, y);
}
}
G.tuopu();
cout << G.work() << endl;
return 0;
}
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
#define ll long long
struct graph{
int n,m;
long long tp[10005],le[10005];//tp拓扑序
bool vs[10005];
vector<int> E[10005];//E[i][j]表示编号为i的点通过第j条边连接的点的编号
vector<int> V[10005];//V[i][j]表示编号为i的点的第j条边的长度
graph (){
memset(vs,0,sizeof(vs));
memset(tp,0,sizeof(tp));
}
void push(int x,int y,int z){
E[x].push_back(y);
V[x].push_back(z);
}
long long toupusort(){
queue<int> Q;
int rt[10005];
memset(vs,0,sizeof(vs));
long long cnt=0,mx=-1,end=0;
memset(rt,0,sizeof(rt));
for(int i=1;i<=n;i++){
for(int j=0;j<E[i].size();j++){
rt[E[i][j]]++;
}
}
do{
for(int i=1;i<=n;i++){
if(rt[i]==0&&vs[i]!=1){
Q.push(i);
vs[i]=1;
cnt++;
tp[cnt]=i;
}
}
int nw=Q.front();
Q.pop();
for(int i=0;i<E[nw].size();i++){
rt[E[nw][i]]--;
if(rt[E[nw][i]]==0&&vs[E[nw][i]]!=1){
Q.push(E[nw][i]);
vs[E[nw][i]]=1;
cnt++;
tp[cnt]=E[nw][i];
}
}
}while(!Q.empty());
memset(vs,0,sizeof(vs));
}
long long gets(){
long long mx[10005];
memset(mx,0,sizeof(mx));
long long end[10005];
memset(end,0,sizeof(end));
for(int i=1;i<=n;i++){
int x=tp[i];
end[x]=mx[x]+le[x];
for(int j=0;j<E[x].size();j++){
mx[E[x][j]]=max(mx[E[x][j]],end[x]);
}
}
long long maxs=-1;
for(int i=1;i<=n;i++)maxs=max(maxs,end[i]);
return maxs;
}
}G;
int x,y,z;
int main(){
cin>>G.n;
int x;
for(int i=1;i<=G.n;i++){
scanf("%*d%d",&G.le[i]);
while(1){
scanf("%d",&x);
if(x==0)break;
G.push(i,x,0);
}
}
cout<<G.gets();
return 0;
}