The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

POJ 1511-Invitation Cards(SPFA算法)

今天终于用SPFA写出了第一个程序,感觉收获很大,从Dij到Floyed再到Bellmen,以及今天的SPFA,每一种算法背后都蕴藏着许多值得思考的地方。正因为研究了它们,才使得我的能力不断地获得了提高。
之前以为SPFA做为最短路问题最快的算法,想必代码定不好写,不过今天研究过才知道,SPFA的代码量远远不及Dij,这着实令人惊叹,原来最好的算法SPFA是如此的好写,呵呵 我想此算法在很大程度上可以完全代替之前的算法,以后再碰到最短路问题时,SPFA一定能成为首要的选择!
PS:由于是用邻接表来存储的,所以每次操作前要收回以前分配的内存,我尝试了收回和不收回两种方法,发现其实差别不大,如果纯粹是比赛的话,可能不收回反而会更好些(避免超时)。当然如果在实际应用中,应该切记内存的分配,否则软件可能会发生异常。

//Coded by abilitytao 
//Time:2009-04-10 22:49:58
#include<iostream>
#include
<cmath>
#include
<queue>
using namespace std;
#define MAX_NUM 1000000001
#define MAX_DOTNUM 1000001

int n,m;
queue
<int>myqueue;
bool mark[MAX_DOTNUM];
__int64 dis[MAX_DOTNUM];


struct node
{

    
int v;
    
int w;
    node 
*next;
}
edge[MAX_DOTNUM];//此邻接表用于存储正向图

node reversed_edge[MAX_DOTNUM];
//此逆邻接表用于存储逆向图

void initial(node edge[])//邻接表的初始化,里面封装了回收上一次操作所分配之内存的操作
{
    
int i;
    node 
*p;
    node 
*q;
    
for(i=1;i<=n;i++)
    
{
        p
=&edge[i];
        q
=p->next;
        
while(q!=NULL)
        
{
            p
->next=q->next;
            delete q;
            q
=p->next;
        }

    }

}



void input_case()//每一个case的输入函数
{

    
int i;
    
for(i=1;i<=m;i++)
    
{
        node 
*p;
        node 
*q;
        
int a,b,c;
        scanf(
"%d%d%d",&a,&b,&c);
        
////////////////////////
        p=&edge[a];
        q
=new node;
        q
->v=b;
        q
->w=c;
        q
->next=p->next;
        p
->next=q;
        
////////////////////////
        p=&reversed_edge[b];
        q
=new node;
        q
->v=a;
        q
->w=c;
        q
->next=p->next;
        p
->next=q;
    }

}



void spfa(node edge[])//SPFA部分
{

    
int i;
    
///////////////////////////////////////////////////////////////
    memset(mark,false,sizeof(mark));
    
for(i=1;i<=n;i++)
        dis[i]
=MAX_NUM;
    
while(myqueue.size()!=0)
        myqueue.pop();
    
///////////////////////////////////////////////////////////
    dis[1]=0;
    mark[
1]=true;
    myqueue.push(
1);
    
while(myqueue.size()!=0)//如果队列不空,则进行松弛操作,直到队列空为止
    {
        
int temp=myqueue.front();
        myqueue.pop();
        mark[temp]
=false;
        node 
*p;
        
for(p=edge[temp].next;p!=NULL;p=p->next)
        
{
            
if(dis[p->v]>dis[temp]+p->w)
            
{
                dis[p
->v]=dis[temp]+p->w;
                
if(mark[p->v]!=true)
                
{
                    myqueue.push(p
->v);
                    mark[p
->v]=true;
                }

            }

        }

    }

}



int main()
{

    
int testcase;
    
int i,j;
    __int64 sum;
    scanf(
"%d",&testcase);
    
for(i=1;i<=MAX_DOTNUM-1;i++)
    
{
        edge[i].v
=i;
        edge[i].w
=0;
        edge[i].next
=NULL;
    }

    
for(i=1;i<=MAX_DOTNUM-1;i++)
    
{
        reversed_edge[i].v
=i;
        reversed_edge[i].w
=0;
        reversed_edge[i].next
=NULL;
    }

    
for(i=1;i<=testcase;i++)
    
{
        sum
=0;
        scanf(
"%d%d",&n,&m);
        initial(edge);
        initial(reversed_edge);
        input_case();
        spfa(edge);
        
for(j=1;j<=n;j++)
            sum
+=dis[j];
        spfa(reversed_edge);
        
for(j=1;j<=n;j++)
            sum
+=dis[j];
        printf(
"%I64d\n",sum);
    }

    system(
"pause");
    
return 0;

}


posted on 2009-04-11 00:51 abilitytao 阅读(2779) 评论(2)  编辑 收藏 引用

评论

# re: POJ 1511-Invitation Cards(SPFA算法) 2009-04-12 12:25 lzmagic

嘿嘿,写得真不错,我的用STL超时了~
貌似把
initial(edge);
initial(reversed_edge);
这两句放到
printf("%I64d\n",sum);
后面去会超时,也许是最后一句数据释放要很久……  回复  更多评论   

# re: POJ 1511-Invitation Cards(SPFA算法) 2009-04-14 16:09 abilitytao

really?我试试看 我开始还以为是回收的效率很高呢...  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理