久久精品国产精品青草app,91麻精品国产91久久久久,久久综合综合久久狠狠狠97色88

poj3259 WormHoles Spfa || BellmanFord

1) Bellman Ford算法找負環的應用.

#include?<cstdio>

#include?<cstdlib>

#include?<queue>

#include?<deque>

using?namespace?std;

struct?Node?{

????int?to;

????int?weight;

????Node?*next;

};

#define?MAXFIELD?(1000?+?10)

#define?MAXPATH?(2500?+?10)

#define?MAXWORMHOLE?(200?+?10)

Node?nodeHead[MAXFIELD];

Node?nodes[MAXPATH?*?2?+?MAXWORMHOLE];

int?dis[MAXFIELD?+?1];

bool?isInQueue[MAXFIELD?+?1];

int?allocPos?=?0;

Node?*getNode()?{

????return?nodes?+?allocPos++;

}

void?initGraph(int?n)?{

????allocPos?=?0;

????int?i?=?0;

????for?(i?=?0;?i?<?n;?++i)?{

????????nodeHead[i].next?=?NULL;

????????dis[i]?=?0;

????}

}

void?addEdge(int?from,?int?to,?int?timeNeed)?{

????Node?*newNode?=?getNode();

????newNode->next?=?nodeHead[from].next;

????newNode->to?=?to;

????newNode->weight?=?timeNeed;

????nodeHead[from].next?=?newNode;

}

int?main()?{

????int?caseCount,?fieldCount,?pathCount,?wormHoleCount;

????int?i,?j,?from,?to,?timeNeed;

????scanf("%d",?&caseCount);

????for?(i?=?0;?i?<?caseCount;?i++)?{

????????scanf("%d%d%d",?&fieldCount,?&pathCount,?&wormHoleCount);

????????initGraph(fieldCount?+?1);

????????for?(j?=?0;?j?<?pathCount;?j++)?{

????????????scanf("%d%d%d",?&from,?&to,?&timeNeed);

????????????addEdge(from,?to,?timeNeed);

????????????addEdge(to,?from,?timeNeed);

????????}

????????for?(j?=?0;?j?<?wormHoleCount;?++j)?{

????????????scanf("%d%d%d",?&from,?&to,?&timeNeed);

????????????addEdge(from,?to,?-timeNeed);

????????}

????????//?關鍵:?按照題目的要求,?可以看出是找圖中有沒有負環

????????//?引入一個超級點s,?s能夠到達任意一個field,?但是沒有任何field能夠到達s

????????//?然后如果圖中不存在負環,?則在經過fieldCount次松弛(我叫優化)以后,?

????????//?就沒有辦法使任意一個field節點的權值變小了,?而如果存在負環,?

????????//?則還能松弛/優化.

????????//?這就是為什么初始化時需要把所有的field都壓入隊列.

????????deque<int>?q;

????????for?(j?=?1;?j?<=?fieldCount;?++j)?{

????????????q.push_back(j);

????????????isInQueue[j]?=?true;

????????}

????????bool?answer?=?false;

????????int?round?=?0;

????????while?(!q.empty())?{

????????????int?n?=?q.size();

????????????for?(j?=?0;?j?<?n;?j++)?{

????????????????int?u?=?q.front();

????????????????q.pop_front();

????????????????isInQueue[u]?=?false;

????????????????Node?*tra;

????????????????for?(tra?=?nodeHead[u].next;?tra?!=?NULL;?tra?=?tra->next)?{

????????????????????int?temp?=?tra->weight?+?dis[u];

????????????????????if?(temp?<?dis[tra->to])?{

????????????????????????dis[tra->to]?=?temp;

????????????????????????if?(!isInQueue[tra->to])?{

????????????????????????????q.push_back(tra->to);

????????????????????????????isInQueue[tra->to]?=?true;

????????????????????????}

????????????????????}

????????????????}

????????????}

????????????round++;

????????????if?(round?>?fieldCount)?{

????????????????answer?=?true;

????????????????q.clear();

????????????????break;

????????????}

????????}

????????if?(answer)?{

????????????puts("YES");

????????}

????????else?{

????????????puts("NO");

????????}

????}

????return?0;

}

posted on 2011-07-06 01:20 cucumber 閱讀(419) 評論(0) 編輯收藏引用

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！



網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

poj3259 WormHoles Spfa || BellmanFord

導航

統計

常用鏈接

留言簿

隨筆檔案

搜索

最新評論

閱讀排行榜

評論排行榜