您现在的位置: 主页 > 华夏黑客联盟 > QQ黑客教程 > 文章内容

QQ破解密码poj-1062-昂贵的破解聘礼

作者: QQ黑客 来源:未知 时间: 2013-12-13 阅读:

黑客qq基地这道题目不能说什么了,狂改了很久很久,现在终于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;
}
作者:QQ破解技术

本篇文章来源于 黑客基地-专业的QQ黑客技术最优秀密码破解网站!