青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

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 閱讀(424) 評論(0)  編輯 收藏 引用

<2025年9月>
31123456
78910111213
14151617181920
21222324252627
2829301234
567891011

導航

統計

常用鏈接

留言簿

隨筆檔案

搜索

最新評論

閱讀排行榜

評論排行榜

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            激情视频一区二区| 欧美华人在线视频| 亚洲一区美女视频在线观看免费| 久久另类ts人妖一区二区| 日韩视频在线免费观看| 午夜精品影院在线观看| 欧美r片在线| 国产精品一区二区久久久| 亚洲国产精品t66y| 久久久精品视频成人| 亚洲人体一区| 久久精品一区二区| 欧美国产精品专区| 欧美一区二区在线| 国产日韩欧美综合精品| 亚洲欧美激情精品一区二区| 亚洲人成啪啪网站| 欧美精品一区二区三| 亚洲欧洲日韩综合二区| 欧美 日韩 国产一区二区在线视频| 午夜在线电影亚洲一区| 国产欧美日韩伦理| 久久久久久久综合日本| 欧美一区二区观看视频| 国产日韩精品在线观看| 久久久久欧美精品| 久久网站免费| 亚洲欧洲视频| 亚洲精品一区在线| 欧美日韩第一页| 午夜激情亚洲| 欧美一区亚洲一区| 亚洲福利国产精品| 亚洲蜜桃精久久久久久久| 欧美亚男人的天堂| 久久久久欧美| 欧美大片在线看免费观看| 一区二区成人精品 | 在线观看成人av电影| 欧美大片免费观看在线观看网站推荐| 美女福利精品视频| 亚洲一区二区在线免费观看| 亚洲女人天堂成人av在线| 精品不卡一区二区三区| 亚洲国产一区二区在线| 国产精品每日更新| 欧美成人一区二区三区| 欧美三级网址| 开心色5月久久精品| 欧美美女bb生活片| 久久婷婷av| 国产精品高清一区二区三区| 国产精品视频你懂的| 欧美成人蜜桃| 国产欧美一区二区三区在线老狼 | 亚洲另类一区二区| 国产女主播在线一区二区| 欧美黄色成人网| **网站欧美大片在线观看| 夜夜躁日日躁狠狠久久88av| 亚洲美女黄网| 国产精品扒开腿做爽爽爽软件| 欧美一区二视频| 久久综合色播五月| 亚洲一区二区视频| 久久久噜久噜久久综合| 亚洲午夜一区二区| 老司机亚洲精品| 午夜精品久久久久久99热| 久久综合久久美利坚合众国| 亚洲色图自拍| 欧美xxx在线观看| 久久久精品国产免费观看同学 | 国产一区二区三区免费不卡 | 国产视频在线观看一区二区三区| 亚洲国产综合视频在线观看| 国产日韩欧美在线播放| 宅男噜噜噜66一区二区| 亚洲麻豆视频| 欧美.日韩.国产.一区.二区| 久久视频这里只有精品| 国产欧美日韩在线| 亚洲中字在线| 午夜久久黄色| 国产精品视频精品| 亚洲欧美高清| 欧美一级片久久久久久久| 欧美午夜精品| 99re66热这里只有精品4| 亚洲人成亚洲人成在线观看| 久久久久久久综合狠狠综合| 久久这里只有| 韩国成人精品a∨在线观看| 欧美一级淫片播放口| 久久激情视频久久| 国产一区美女| 久久久亚洲欧洲日产国码αv| 久久一区二区精品| 在线成人激情视频| 女女同性女同一区二区三区91| 欧美大香线蕉线伊人久久国产精品| 国产欧美日韩中文字幕在线| 亚洲男人第一av网站| 久久精品国产精品亚洲精品| 国产欧美三级| 久久精品国产99| 欧美黄色aa电影| 一区二区欧美精品| 国产精品成人一区| 欧美亚洲免费| 欧美不卡视频一区| 宅男精品导航| 黄色精品免费| 国产精品久久久久久久第一福利 | 麻豆91精品| 久久精品99久久香蕉国产色戒| 亚洲免费人成在线视频观看| 亚洲欧美日韩网| 蜜桃久久av一区| 亚洲国产综合视频在线观看| 久久久久久婷| 欧美怡红院视频| 久久亚洲欧美国产精品乐播| 亚洲国产精品一区二区第四页av| 欧美激情一区在线| 亚洲小说春色综合另类电影| 久久久久成人网| 亚洲麻豆国产自偷在线| 国产精品久久久久久久久动漫| 久久av免费一区| 亚洲精品美女在线观看| 欧美一区二区视频在线观看| 亚洲成色777777在线观看影院| 欧美久久久久久久久久| 欧美一级大片在线观看| 亚洲国产精品专区久久| 欧美在线观看网址综合| 亚洲国产精彩中文乱码av在线播放| 欧美区一区二区三区| 欧美亚洲一区三区| 亚洲激情另类| 老司机亚洲精品| 午夜精品视频一区| 亚洲乱码国产乱码精品精可以看| 国产欧美一区二区精品仙草咪| 欧美国产视频在线观看| 欧美综合77777色婷婷| 99一区二区| 亚洲国产裸拍裸体视频在线观看乱了中文 | 国产综合色在线视频区| 欧美日韩免费一区| 久热精品视频在线观看| 亚洲一本大道在线| 91久久夜色精品国产九色| 久久久久久欧美| 欧美一级艳片视频免费观看| 亚洲精品视频在线看| 黄色一区二区在线| 国产欧美日韩在线视频| 欧美日韩在线播放一区二区| 另类成人小视频在线| 欧美诱惑福利视频| 亚洲欧美在线观看| 亚洲专区在线| 亚洲男人的天堂在线aⅴ视频| 亚洲卡通欧美制服中文| 欧美高清视频在线观看| 另类欧美日韩国产在线| 久久精品亚洲一区| 欧美影院一区| 在线一区视频| 久久精品一区二区三区四区| av成人激情| 亚洲精品一二| 亚洲人成在线观看| 亚洲精品美女在线| 99国产精品一区| av不卡在线观看| 亚洲一级片在线看| 亚洲欧美自拍偷拍| 欧美伊人久久大香线蕉综合69| 亚洲欧美综合v| 日韩午夜黄色| 99精品视频一区| 99精品视频网| 亚洲女与黑人做爰| 欧美在线地址| 麻豆精品精华液| 欧美激情久久久| 91久久国产精品91久久性色| 亚洲第一主播视频| 亚洲国产精品小视频| 最新国产精品拍自在线播放| 日韩午夜激情av| 亚洲一级特黄| 久久久久久一区二区三区| 麻豆久久精品| 欧美日韩亚洲一区二区三区在线 | 久久精品夜色噜噜亚洲a∨| 久久久久国产一区二区三区四区|