【dfs or 最短路】【HDU1224】【Free DIY Tour】-白红宇

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

阅读量：5914 次

发布时间：2019-06-19

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

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

DFS

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

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

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #define oo 0x13131313using 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 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #define oo 0x13131313using 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
             
              ",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(); }}