【dfs or 最短路】【HDU1224】【Free DIY Tour】

路径只能由小序号到大序号..（起点可以视为最小的序号和最大的序号）问怎么走 happy值最大..

DFS

N=100 且只能小序号到大序号显然dfs可以过..

但是存路径的时候sb了.....应该在更新答案时拿一个ans_dis数组去全部存一遍路径...

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <cstring>

#include <ctime>

#include <algorithm>

#include <iostream>

#include <sstream>

#include <string>

#define oo 0x13131313

using namespace std;

const int maxn=105;

const int inf=-0x3f3f3f3f;

int w[maxn];

int dis[maxn];

struct edge

{

    int to;

    edge *next;

}E[maxn*maxn],*EE;

struct node

{

    edge *frist;

}Graph[maxn];

int N,M;

int pre[maxn];

void Link(int u,int v)

{

    EE->to=v;EE->next=Graph[u].frist;Graph[u].frist=EE++;

 //   EE->to=u;EE->next=Graph[v].frist;Graph[v].frist=EE++;

}

void input()

{

    cin>>N;

    memset(Graph,0,sizeof(Graph));

    memset(pre,0,sizeof(pre));

    memset(dis,0,sizeof(dis));

    EE=E;

    for(int i=1;i<=N;i++)

    {

        scanf("%d",&w[i]);

    }

    cin>>M;

    int a,b;

    for(int i=1;i<=M;i++)

    {

        scanf("%d%d",&a,&b);

        if(b==N+1) b=1;

        if(a==N+1) a=1;

        Link(a,b);

    }

}

int ans=-1;

int dfs(int P,int n,int ok,int W)

{

     pre[n]=P;

    if(ok==1&&n==1)

    {

        if(W>ans)

        {

            int p=pre[n];

            dis[n]=pre[n];

            while(p!=1)

            {dis[p]=pre[p];p=pre[p];}

            ans=W;

        }

        return 0;

    }

    else

    {

        for(edge *p=Graph[n].frist;p;p=p->next)

        {

            if(p->to>n||p->to==1){dfs(n,p->to,1,W+w[n]);}

        }

    }

}

void output(int n,int ok)

{

    if(n==1&&ok==1)

    {

        printf("%d",n);

    }

    else {

                output(dis[n],1);

                printf("->%d",n);

         }

}

    int CASE=0;

	int T;

void solve()

{

        ans=inf;

        dfs(0,1,0,0);

        printf("%d\n",ans);

        printf("circuit : ");

        output(1,0);

        printf("\n");

        if(T!=0) printf("\n");

}

void init()

{

    freopen("a.in","r",stdin);

    freopen("a.out","w",stdout);

}

int main()

{

   // init();

	cin>>T;

	while(T--)

    {

        printf("CASE %d#\n",++CASE);

        printf("points : ");

        input();

        solve();

    }

    return 0;

}

最短路

Floyd

利用floyd..在循环的时候修改一下循环次数即可

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <cstring>

#include <ctime>

#include <algorithm>

#include <iostream>

#include <sstream>

#include <string>

#define oo 0x13131313

using namespace std;

const int maxn=105;

const int inf=-0x3f3f3f3f;

int T;

int N,M;

int w[maxn];

int MAP[maxn][maxn];

int F[maxn][maxn];

int dis[maxn][maxn];

void input()

{

    memset(MAP,0,sizeof(MAP));

    memset(dis,0,sizeof(dis));

    int a,b;

    cin>>N;

    for(int i=1;i<=N;i++)

    {

        scanf("%d",&w[i]);

        w[i]=-w[i];

    }

    w[N+1]=0;

    cin>>M;

    for(int i=1;i<=M;i++)

    {

        scanf("%d%d",&a,&b);

        MAP[a][b]=1;

    }

             for(int i=0;i<maxn;i++)

            for(int j=0;j<maxn;j++)

            {

                F[i][j]=-inf;

                if(MAP[i][j]==1)

                F[i][j]=0;

            }

}

void floyed()

{

    for(int i=1;i<=N+1;i++)

        for(int j=1;j<=N+1;j++)

        dis[i][j]=j;

    for(int k=1;k<=N+1;k++)

        for(int i=1;i<k;i++)

         for(int j=k+1;j<=N+1;j++)

    {

        if(F[i][k]+F[k][j]+w[k]<F[i][j])

        {

            F[i][j]=F[i][k]+F[k][j]+w[k];

            dis[i][j]=dis[i][k];

        }

    }

    printf("points : %d\n",-F[1][N+1]);

    printf("circuit : ");

    for(int p=1;1;p=dis[p][N+1])

    {

        if(p==N+1){printf("1");break;}

        else{

             printf("%d->",p);

            }

    }

    printf("\n");

    if(T!=0) printf("\n");

}

void init()

{

    freopen("a.in","r",stdin);

    freopen("a.out","w",stdout);

}

int main()

{

    int CASE=0;

  //  init();

    cin>>T;

    while(T--)

    {

        printf("CASE %d#\n",++CASE);

        input();

        floyed();

    }

}

巴特西

【dfs or 最短路】【HDU1224】【Free DIY Tour】

最新文章

热门文章