11.6 DAG最長路

DAG:有向無環圖

1.求整個DAG中的最長路徑（即：不固定終點和起點）

2.固定終點，求DAG中的最長路徑

問題1

給定一個有向無環圖，如何求解整個圖的所有路徑中權值之和最大的那條

令：dp[i]表示從i号頂點出發能獲得的最長路徑長度。dp[i]的最大值即是DAG的最長路徑長度

dp[i]=max{

    dp[j]+length(i->j)

}

j是i的所有直接後繼

#include<iostream>
#include<cstring>
using namespace std;

const int N=100;
int dp[N],G[N][N];
int n,choose[N];

int DP(int i){
  if(dp[i]>0) return dp[i];
  for(int j=0;j<n;j++){
    if(G[i][j]!=0){
      int temp=DP(j)+G[i][j];
      if(temp>dp[i]){
        dp[i]=temp;
        choose[i]=j;//在最長路徑中更新i的後繼是j
      }
    }
  }
  return dp[i];
}

void printPath(int i){//i是最大dp[i]的下标
  cout<<i;
  while(choose[i]!=-1){//初始化-1  d到-1說明到頭了
    i=choose[i];//巧妙往前走了一步
    cout<<"->"<<i;//輸出i不是chosoe[i] 已經複制給i了
  }
  cout<<endl;
}

int main(){
  freopen("input2.txt","r",stdin);
  //領接矩陣存儲
  while(cin>>n){
    memset(dp,0,sizeof(dp));
    memset(choose,-1,sizeof(choose));
    for(int i=0;i<n;i++){
      for(int j=0;j<n;j++){
        cin>>G[i][j];//0代表不通
      }
    }

    int max=0;
    DP(max);
    for(int i=1;i<n;i++){
      if(dp[max]<DP(i)) max=i;
    }

    printf("長度:%d\n路徑:",dp[max]);
    printPath(max);
  }
  return 0;
}      

測試用例：

問題二；

dp[i]表示從i号頂點出發到終點T能獲得最長路徑

邊界dp[T]=0               dp[i]初始化為-INF

#include<iostream>
#include<cstring>
using namespace std;

const int N=100;
const int INF=-INT_MAX;
int dp[N],G[N][N];
int n,choose[N];
bool vis[N];

int DP(int i){
  if(vis[i]) return dp[i];
  vis[i]=true;
  for(int j=0;j<n;j++){
    if(G[i][j]!=INF){
      dp[i]=max(dp[i],DP(j)+G[i][j]);
      choose[i]=j;
    }
  }
  return dp[i];
}

void printPath(int i){//i是最大dp[i]的下标
  cout<<i;
  while(choose[i]!=-1){//初始化-1  d到-1說明到頭了
    i=choose[i];//巧妙往前走了一步
    cout<<"->"<<i;//輸出i不是chosoe[i] 已經複制給i了
  }
  cout<<endl;
}

int main(){
  freopen("input2.txt","r",stdin);
  //領接矩陣存儲
  // cout<<INF<<endl;
  while(cin>>n){
    memset(dp,0,sizeof(dp));
    memset(choose,-1,sizeof(choose));
    memset(vis,0,sizeof(vis));//bool型初始化0  0==false
    for(int i=0;i<n;i++){
      for(int j=0;j<n;j++){
        cin>>G[i][j];//0代表不通或者到自己
        if(G[i][j]==0) G[i][j]=INF;
      }
    }
    //★★
    int T;
    cin>>T;
    dp[T]=0;
    vis[T]=true;

    int max=0;
    DP(max);
    for(int i=1;i<n;i++){
      if(dp[max]<DP(i)) max=i;
    }
    printf("以%d為終點\n",T);
    printf("最大路徑長度:%d\n路徑:",dp[max]);
    printPath(max);
    cout<<endl;
  }
  return 0;
}