程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> poj-1062-昂貴的聘禮

poj-1062-昂貴的聘禮

編輯:C++入門知識

這道題目不能說什麼了,狂改了很久很久,現在終於AC了,在這道題目上花的時間太多太多了,,,,
一開始看這道題目的時候想到的是用DFS,後來想起來前天看了A*算法。就用A*算法寫了。
 [html] 
#include<stdio.h> 
#include<math.h> 
int map[301][301];//記錄邊 
int di[301],val[301];//記錄地位,價值 
struct list 

    int a; 
    int max; 
    int min; 
    int v; 
}open[301],close[301],ex;//open是起始數組,close是結果數組 
int open_n=0; 
int close_n=0; 
int cheak[301][301]; 
int m,n; 
void guanlian() 

    int open_first,i,j,open_val,open_max,open_min; 
    open_first=open[open_n-1].a;//------------------------------------------------ 
    open_val=open[open_n-1].v; 
    open_max=open[open_n-1].max; 
    open_min=open[open_n-1].min;//    中間這部分是把open數組中價值最小的轉移到close數組中 
    open_n--; 
    close[close_n]=open[open_n]; 
    close_n++;                 //------------------------------------------------- 
    for(i=1;i<=n;i++) 
    { 
        if(map[open_first][i]!=-1&&cheak[open_first][i]) 
        { 
            if((fabs(di[i]-open_max)<=m)&&fabs(di[i]-open_min)<=m) 
            { 
                if(di[i]<open_min)             //------------------------------------------- 
                { 
                    open[open_n].min=di[i]; 
                    open[open_n].max=open_max; 
                } 
                else if(di[i]>open_max)       //這部分是決定這條兌換鏈所涉及到的人的最大地位和最小地位 
                { 
                    open[open_n].max=di[i]; 
                    open[open_n].min=open_min; 
                } 
                else                           //---------------------------------------------- 
                {  
                    open[open_n].max=open_max; 
                    open[open_n].min=open_min; 
                } 
                cheak[open_first][i]=0; 
                open[open_n].a=i; 
                open[open_n].v=map[open_first][i]+open_val; 
                open_n++; 
            } 
        } 
    } 
    for(i=0;i<open_n;i++)//把open數組按照價值排序 
    { 
        for(j=i+1;j<open_n;j++) 
        { 
            if((open[i].v+val[open[i].a])<(open[j].v+val[open[j].a])) 
            { 
                ex=open[i];   
                open[i]=open[j]; 
                open[j]=ex; 
            } 
        } 
    } 
}    
int A() 

    int i,nmax,max; 
    open[0].a=1; 
    open[0].v=0; 
    open[0].max=di[1]; 
    open[0].min=di[1]; 
    open_n++; 
    while(open_n!=0) 
    { 
        guanlian(); 
    } 
    nmax=val[1]; 
    for(i=0;i<close_n;i++)//尋找close數組裡面價值最小的值,即是結果值 
    { 
        max=close[i].v+val[close[i].a]; 
        if(max<nmax) 
        { 
            nmax=max; 
        } 
    } 
    return nmax; 

int main() 

    int i,j,p,l,x,t,v,val_put; 
    for(i=1;i<=300;i++) 
    { 
        close[i].v=0; 
    } 
    for(i=1;i<=300;i++) 
    { 
        for(j=1;j<=300;j++) 
        { 
            cheak[i][j]=1; 
            map[i][j]=-1; 
        } 
    } 
    scanf("%d%d",&m,&n); 
    for(i=1;i<=n;i++) 
    { 
        scanf("%d%d%d",&p,&l,&x); 
        di[i]=l;val[i]=p; 
        for(j=1;j<=x;j++) 
        { 
            scanf("%d%d",&t,&v); 
            map[i][t]=v; 
        } 
    } 
    val_put=A(); 
    printf("%d\n",val_put); 
    return 0; 

作者:rowanhaoa

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved