DAGDP求DAG最长路求查问题
查看原帖
DAGDP求DAG最长路求查问题
93701
Morgen_Kornblume楼主2021/5/15 09:22
int dagdp(){
		queue<int>deg0;//入度为0点
		while(!deg0.empty()){
			deg0.pop();
		}
		memset(dp,0,sizeof(dp));
		memset(rd,0,sizeof(dp));//入度
		//memset(vis,false,sizeof(vis));
		
		for(int i=1;i<=tot;i++){//tot为总边数
			rd[to[i]]++;
		}
		
		for(int i=3*bas;i>=1;i--){
  			//3*bas是总点数
			if(!rd[i]){
				deg0.push(i);
			}
		}
		
		while(!deg0.empty()){
			int nowa=deg0.front();
			deg0.pop();
			
			for(int i=head[nowa];i;i=nxt[i]){
				dp[to[i]]=max(dp[to[i]],dp[nowa]+wei[i]);
				rd[to[i]]--;
				if(!rd[to[i]]){
					deg0.push(to[i]);
				}
			}
		}
		int res=0;
		for(int i=1;i<=3*bas;i++){//3*bas是总点数
			res=max(res,dp[i]);
		}
		return res;
	}
2021/5/15 09:22
加载中...