只有第一个点对,求助
  • 板块P1113 杂务
  • 楼主2009cqr
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/11/7 20:22
  • 上次更新2023/11/7 20:29:09
查看原帖
只有第一个点对,求助
610758
2009cqr楼主2023/11/7 20:22

拓扑排序做法求助

#include<bits/stdc++.h>
using namespace std;
#define LF putchar('\n')
#define SP putchar(' ')
#define rep(i,a,b) for(register int i=(a);i<=(b);++i)
#define repp(i,a,b) for(register int i=(a);i>=(b);i--)
#define pill pair<int,int>
#define mem(t, v) memset((t),v,sizeof(t))
#define fir first
#define sec second
#define mk make_pair
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
#define lc root<<1
#define rc root<<1|1
typedef long long ll;
typedef unsigned long long ull;
template<typename T>
void read(T &x) {x=0;char ch=getchar();ll f=1;while(!isdigit(ch)){if(ch=='-')f*=-1;ch=getchar();}while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}x*=f;}
template<typename T, typename... Args>
void read(T &first, Args& ... args) {read(first);read(args...);}
template<typename T>
void write(T arg) {T x=arg;if(x<0) {putchar('-');x=-x;}if(x>9) {write(x/10);}putchar(x%10+'0');}
template<typename T, typename ... Ts>
void write(T arg, Ts ... args) {write(arg);if(sizeof...(args)!=0) {putchar(' ');write(args ...);}}
const ll mod=10007,N=1e4+10,M=1e6+10;
int head[M],tot,n,cost[N],dist[N],indx[N],maxx;
queue<int> q,cl;
struct node{
	int u,v,w,nex;
}edge[M];
void add(int a,int b,int w){
	edge[++tot]=(node){a,b,w,head[a]};
	head[a]=tot;
}
void BFS(int start){
	q=cl;
	q.push(start);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(int i=head[u];~i;i=edge[i].nex){
			int v=edge[i].v;
			indx[v]--;
			dist[v]=max(dist[v],dist[u]+edge[i].w);
			if(indx[v]==0){
				q.push(v);
			}
		}
	}
}
signed main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	memset(head,-1,sizeof head);
	read(n);
	rep(i,1,n){
		int u,t,v;
		read(v,t);
		cost[v]=t;
		while(1){
			read(u);
			if(u==0)break;
			indx[v]++;
			add(u,v,cost[u]);
		}
	}
	rep(i,1,n){
		if(indx[i]==0 and dist[i]==0)BFS(i);
	}
	rep(i,1,n){
		maxx=max(maxx,dist[n]+cost[n]);
	}
	write(maxx);
//	fclose(stdin);
//	fclose(stdout);
	return 0;
}

2023/11/7 20:22
加载中...