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

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>
            久久亚洲视频| 国产一区二区三区免费不卡 | 亚洲欧洲精品成人久久奇米网| 亚洲在线视频一区| 99国产精品国产精品毛片| 每日更新成人在线视频| 亚洲激情av| 亚洲精品国久久99热| 老鸭窝亚洲一区二区三区| 久久精品国产精品亚洲综合| 国产欧美日韩一区二区三区在线 | 亚洲一区3d动漫同人无遮挡| 亚洲福利小视频| 久久久精品动漫| 久久久久久久综合狠狠综合| 国产亚洲精品v| 欧美伊人久久大香线蕉综合69| 亚洲精品一区二区在线| 欧美激情亚洲精品| 亚洲欧美怡红院| 久久久综合网站| 99在线精品视频| 亚洲摸下面视频| 中文在线不卡| 欧美亚洲日本国产| 亚洲美女精品一区| 欧美中文字幕视频在线观看| 国产视频不卡| 欧美a级一区二区| 国产精品免费看久久久香蕉| 久久综合网色—综合色88| 欧美jizzhd精品欧美喷水| 一本色道久久88综合亚洲精品ⅰ | 亚洲欧美资源在线| 狠狠色丁香婷婷综合影院| 亚洲图片欧洲图片日韩av| 在线看片成人| 亚洲欧美一级二级三级| 99re6这里只有精品视频在线观看| 正在播放日韩| 亚洲专区一区二区三区| 蜜臀av性久久久久蜜臀aⅴ四虎| 狂野欧美激情性xxxx欧美| 99xxxx成人网| 国产精品高潮呻吟| 欧美在线视频观看| 国产精品盗摄久久久| 欧美成人精精品一区二区频| 国产精一区二区三区| 亚洲精品乱码久久久久| 亚洲国产高潮在线观看| 国产视频在线观看一区二区三区| 国产精品s色| 欧美一区二区性| 久久久久九九视频| 亚洲激情成人网| 欧美精品三级日韩久久| 91久久久精品| 欧美在线视频二区| 国产一区二区三区在线观看精品| 欧美一区二区精品| 久久久久久网站| 亚洲欧洲精品一区二区| 欧美精品激情blacked18| 亚洲天堂av图片| 久久久综合网| 亚洲欧美不卡| 1024日韩| 蘑菇福利视频一区播放| 国产精品99久久久久久久女警| 久久久av网站| 亚洲一区观看| 亚洲看片网站| 亚洲欧洲一区二区天堂久久| 国产老肥熟一区二区三区| 欧美极品aⅴ影院| 久久久另类综合| 久久成人18免费网站| 性做久久久久久久免费看| 亚洲视频你懂的| 在线视频精品一| 一区二区三区蜜桃网| 红杏aⅴ成人免费视频| 国产精品手机在线| 国产精品美女黄网| 国产老肥熟一区二区三区| 国产精品二区影院| 国产人妖伪娘一区91| 国产日韩精品一区观看| 国产日韩精品电影| 国产日韩欧美日韩大片| 国产精品久久久久一区| 亚洲一二三区在线观看| 亚洲欧美日本日韩| 久久激情中文| 欧美黑人多人双交| 国产精品久久久久久久久婷婷| 欧美视频二区36p| 国产无遮挡一区二区三区毛片日本| 国产亚洲福利社区一区| 国产在线精品一区二区中文 | 国模私拍视频一区| 亚洲国产精品福利| 亚洲一区免费观看| 久久这里只有| 亚洲在线成人精品| 欧美国产三区| 尤物精品国产第一福利三区 | 香港成人在线视频| 亚洲资源av| 亚洲国产日韩欧美综合久久| 亚洲午夜黄色| 欧美日韩国产一区二区三区| 蜜桃久久精品一区二区| 欧美日韩国产成人精品| 亚洲黄色在线视频| 久热精品视频在线观看| 欧美一级夜夜爽| 国产精品va在线播放我和闺蜜| 欧美在线免费| 国产精品久久久一区二区| 91久久线看在观草草青青| 亚洲欧美一区二区三区在线| 欧美高清在线一区| 久久青青草综合| 国产伦理一区| 欧美一级久久久| 亚洲网站视频| 欧美午夜宅男影院在线观看| 在线观看国产日韩| 欧美高清在线一区| 久久欧美中文字幕| 亚洲图片欧洲图片日韩av| 欧美日韩免费观看一区| 在线观看av一区| 欧美成年人在线观看| 欧美好骚综合网| 久久爱另类一区二区小说| 久久精品欧美日韩| 免费的成人av| 一本一本大道香蕉久在线精品| 91久久在线| 国产欧美一区二区三区沐欲| 国产有码在线一区二区视频| 久久亚洲二区| 欧美日韩午夜| 久久久久国色av免费观看性色| 久久天天躁狠狠躁夜夜av| 日韩午夜激情| 羞羞视频在线观看欧美| 亚洲国产精品女人久久久| 亚洲激情视频网| 国产精品高潮在线| 美女黄网久久| 国产精品免费看| 亚洲国产成人av| 在线观看视频亚洲| 日韩视频一区二区三区在线播放免费观看| 欧美喷潮久久久xxxxx| 久久精品网址| 国产精品久久久久aaaa九色| 欧美jizz19性欧美| 国产一区二区精品丝袜| 一区二区三区免费在线观看| 国产欧美精品xxxx另类| 亚洲一区制服诱惑| 亚洲国产免费| 在线观看久久av| 欧美制服丝袜| 久久精品1区| 好看的日韩视频| 久久精品99| 欧美高清视频| 日韩视频久久| 欧美日韩国产一区精品一区| 91久久亚洲| 亚洲欧美一区二区在线观看| 国产欧美91| 欧美一区二区在线观看| 久久青草久久| 9国产精品视频| 国产精品制服诱惑| 久久综合伊人77777麻豆| 亚洲国产精品尤物yw在线观看| 91久久久久久| 国产精品自在欧美一区| 久久综合亚州| 亚洲欧美日韩高清| 国产在线欧美日韩| 久久综合九色综合欧美就去吻 | 亚洲人精品午夜在线观看| 欧美日韩 国产精品| 久久国产视频网| 亚洲国产精品一区制服丝袜| 欧美v日韩v国产v| 国产精品99久久久久久久久| 美女国产一区| 久久久久一区二区三区四区| 在线一区免费观看| 亚洲国产精品国自产拍av秋霞|