Free DIY Tour HDU1224-白红宇

Free DIY Tour HDU1224

阅读量：4323 次

发布时间：2019-06-06

本文共 4072 字，大约阅读时间需要 13 分钟。

一道很好的dfs加储存路径的题目：路径保存：每次dfs都存i 当大于max时将临时数组保存到答案数组

并不是当当前值大于最大值时更新路径

还要加上一个条件：能回去

#include
      
       using namespace  std;int n;int m1[200][200];int valu[105];int ans[105];int path[105];int maxi,len;void dfs(int stepn,int sum,int cur){   for(int i=cur+1;i<=n;i++)   {       if(m1[cur][i])       {           path[stepn]=i;           if(m1[i][n+1])           {               path[stepn+1]=1;               if(sum+valu[i]>maxi)               {                   maxi=sum+valu[i];                   len=stepn+1;                   for(int j=1;j<=len;j++)                   {                       ans[j]=path[j];                   }               }           }           dfs(stepn+1,sum+valu[i],i);       }   }}int main(){  int cas;scanf("%d",&cas);int case1=1;  while(cas--)  {        maxi=0;      len=1;      ans[0]=1;       memset(m1,0,sizeof(m1));      scanf("%d",&n);      for(int i=1;i<=n;i++)scanf("%d",&valu[i]);            valu[1]=valu[1+n]=0;             int q;        scanf("%d",&q);      while(q--)      {          int a,b;          scanf("%d%d",&a,&b);          m1[a][b]=m1[b][a]=1;      }        if(case1!=1)        printf("\n");      printf("CASE %d#\n",case1++);      dfs(1,0,1);      printf("points : %d\n",maxi);      if(len!=1)      {          printf("circuit : ");          for(int i=0;i
       
        ",ans[i]);          printf("%d\n",ans[len]);      }  }return 0;}

View Code

还可以用dp来做

#include 
      
       #include 
       
        bool link[105][105];int intrest[105], dp[105], last[105], path[105];int main(){    int t, case_num = 1;    //freopen("input.txt", "r", stdin);    scanf("%d", &t);    while(t--)    {        int n, m, i, j;        memset(link, 0, sizeof(link));        memset(dp, 0, sizeof(dp));        last[1] = 0; //last记录上一个走的城市的标号，last[1] = 0是为了让追溯到第一个城市之后就不继续追溯了        scanf("%d", &n);        if(case_num != 1)            printf("\n");        for(i = 1; i <= n; i++)        {            scanf("%d", &intrest[i]);        }        intrest[i] = 0; //注意i城市有趣度为0!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!        scanf("%d", &m);        for(int i = 0; i < m; i++)        {            int a, b;            scanf("%d%d", &a, &b);            link[a][b] = link[b][a] = 1;        }        for(i = 2; i <= n+1; i++) //假设目标城市标号为i(注意到达它之前经过的城市的标号都小于它)        {            for(j = 1; j < i; j++)                //遍历到达i城市之前所在的城市的标号的所有可能性，                //更新到达i城的时候的有趣度之和为所有情况中最大的            {                if(dp[j]+intrest[i] > dp[i] && link[i][j])                {                    dp[i] = dp[j]+intrest[i];                   last[i] = j;                }            }        }        j = 0;        i = n+1;        while(last[i])        {            path[j++] = last[i];            i = last[i];        }        printf("CASE %d#\n", case_num++);        printf("points : %d\n", dp[n+1]);        printf("circuit : ");        for(i = j-1; i >= 0; i--)//注意输出的个数并非为城市数目！！！！！！！！！！！！！        {            printf("%d->", path[i]);        }        printf("1\n");    }    return 0;}

View Code

回顾

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          #include
           
            #include
            
             using namespace std;#define N 105#define inf 0x3f3f3f3fint ans[N];int path[N];int n,maxx;int mp[N][N];int city[N];int len;void dfs(int cur,int interest,int num){ for(int i=cur+1;i<=n;i++) { if(mp[cur][i]) { int t=interest+city[i]; path[num]=i; if(t>maxx&&mp[i][n+1]) { maxx=t; for(int i=0;i<=num;i++) ans[i]=path[i]; len=num; } dfs(i,t,num+1); } }}int main(){ int cas;cin>>cas; for(int kase=1;kase<=cas;kase++) { memset(mp,0,sizeof mp); scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&city[i]); city[n+1]=city[1]=0; int m,a,b; cin>>m; while(m--) { scanf("%d%d",&a,&b); mp[a][b]=mp[b][a]=1; } path[0]=1; maxx=0; dfs(1,0,1); if(kase!=1)printf("\n"); printf("CASE %d#\n",kase); printf("points : %d\ncircuit : ",maxx); for(int i=0;i<=len;i++) printf("%d->",ans[i]); printf("%d\n",1); }}