求助P1113找不同
  • 板块学术版
  • 楼主1Stone
  • 当前回复2
  • 已保存回复2
  • 发布时间2022/7/17 20:08
  • 上次更新2023/10/27 19:49:20
查看原帖
求助P1113找不同
648953
1Stone楼主2022/7/17 20:08

求助神犇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;
}

2022/7/17 20:08
加载中...