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

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>
            亚洲色诱最新| 亚洲日本欧美日韩高观看| 欧美在线999| 国产日韩亚洲欧美精品| 欧美国产成人在线| 欧美日韩色婷婷| 亚洲网站在线观看| 欧美三区在线| 欧美激情一区二区三区蜜桃视频 | 99视频精品| 欧美电影免费| 国产一区二区三区高清| 亚洲精品国产欧美| 国产精品久久久| 久久精品首页| 亚洲欧洲一区二区三区久久| 一二三区精品| 亚洲综合色婷婷| 日韩午夜在线观看视频| 欧美色图麻豆| 美女黄网久久| 亚洲精品视频免费| 国产色产综合色产在线视频| 在线一区二区日韩| 久久精品视频免费| 国产精品区一区二区三| 久久精品99| 久久免费精品视频| 欧美大片免费| 在线亚洲美日韩| 最新中文字幕亚洲| 国产麻豆精品视频| 欧美影院视频| 亚洲免费大片| 久久久久久欧美| 亚洲高清视频在线| 亚洲人成人一区二区三区| 久久久99爱| 嫩草成人www欧美| 91久久嫩草影院一区二区| 久久国产福利| 看欧美日韩国产| 亚洲精品国偷自产在线99热| 在线色欧美三级视频| 欧美三级不卡| 久久综合久久久| 在线观看国产成人av片| 欧美三级在线播放| 久久久噜噜噜久久中文字幕色伊伊 | 亚洲性图久久| 99国产精品99久久久久久粉嫩 | 欧美区亚洲区| 午夜视频一区| 久久电影一区| 欧美日韩美女| 国产精品免费视频观看| 日韩系列欧美系列| 欧美日韩精品国产| 亚洲国产欧美在线| 一本久久综合| 亚洲二区在线| 性色一区二区三区| 欧美在线资源| 国产亚洲欧洲一区高清在线观看 | 在线成人www免费观看视频| 国产综合色精品一区二区三区| 99视频精品| 亚洲理论在线观看| 一区二区三区福利| 久久av在线看| 亚洲第一精品久久忘忧草社区| 在线成人av.com| 在线视频国内自拍亚洲视频| 亚洲激情综合| 久久都是精品| 亚洲男女自偷自拍| 欧美日韩在线免费视频| 在线观看亚洲视频| 99成人在线| 亚洲精品专区| 欧美/亚洲一区| 1000部精品久久久久久久久| 一区二区三区国产在线| 欧美在现视频| 亚洲高清在线精品| 亚洲视频一区二区免费在线观看| 欧美在线在线| 国产亚洲成av人在线观看导航| 日韩视频在线一区二区| 亚洲视频精品在线| 亚洲视频综合在线| 国产综合在线视频| 午夜精品免费在线| 亚洲电影av在线| 欧美二区在线看| 亚洲第一在线| 免费成人在线视频网站| 亚洲乱码国产乱码精品精可以看| 亚洲欧美日韩精品久久久久| 国产欧美丝祙| 久久亚洲综合色一区二区三区| 欧美激情四色| 久久一区二区三区四区| 欧美激情国产日韩精品一区18| 亚洲天堂免费观看| 1024成人网色www| 欧美黑人在线观看| 欧美日韩国产综合视频在线观看| 亚洲淫片在线视频| 亚洲影院污污.| 国产日韩精品电影| 久久精品免费观看| 亚洲成人在线视频播放| 国产精品视频专区| 在线视频欧美一区| 午夜精品一区二区三区在线播放| 欧美一区二区三区啪啪| 欧美jizzhd精品欧美巨大免费| 夜夜嗨av色一区二区不卡| 国产欧美日本| 欧美刺激性大交免费视频| 日韩一级黄色av| 欧美亚洲视频一区二区| 狠狠色狠狠色综合| 免费观看30秒视频久久| 欧美一区二区免费| 亚洲一区二区在| 午夜精品久久久| 亚洲高清三级视频| 国产美女扒开尿口久久久| 欧美日韩亚洲国产一区| 久热精品在线| 久热成人在线视频| 午夜精品婷婷| 久久精品卡一| 另类春色校园亚洲| 亚洲欧美制服另类日韩| 欧美电影在线观看完整版| 亚洲欧美日韩在线| 亚洲一区在线播放| 亚洲欧美日本国产专区一区| 一本久道久久久| 亚洲精品免费观看| 欧美中文字幕精品| 欧美日韩精品一区二区天天拍小说| 一区二区三区国产在线| 99在线精品免费视频九九视| 亚洲区中文字幕| 亚洲一区二区在线看| 久久精品国产77777蜜臀| 久久久蜜桃精品| 久久国产加勒比精品无码| 欧美伊人久久大香线蕉综合69| 欧美激情视频在线播放 | 国产精品99久久久久久久vr| 裸体女人亚洲精品一区| 久久久久久久一区二区| 你懂的国产精品永久在线| 一本色道久久综合亚洲精品不卡| 午夜国产精品视频免费体验区| 欧美亚洲自偷自偷| 蜜乳av另类精品一区二区| 欧美暴力喷水在线| 国产精品视频yy9099| 国产欧美日韩在线| 亚洲人成久久| 蜜桃av噜噜一区| 亚洲免费观看高清完整版在线观看熊| 狼人天天伊人久久| 国产亚洲视频在线观看| 亚洲永久免费av| 亚洲电影第1页| 久久婷婷人人澡人人喊人人爽| 国产精品magnet| 亚洲精品男同| 亚洲乱亚洲高清| 欧美日韩精品国产| 宅男噜噜噜66一区二区| 欧美激情视频一区二区三区在线播放| 久久久久国产成人精品亚洲午夜| 国产真实久久| 麻豆精品视频在线观看| 欧美制服丝袜第一页| 国模 一区 二区 三区| 欧美日韩精品久久久| 亚洲国产精品精华液网站| 欧美韩日亚洲| 国产精品v日韩精品| 国产精品人人爽人人做我的可爱| 久久精品国产999大香线蕉| 亚洲欧美日韩精品一区二区| 狠狠爱成人网| 99精品视频免费在线观看| 欧美午夜一区二区三区免费大片| 久久久在线视频| 欧美精品午夜视频| 亚洲桃色在线一区| 久久国产精彩视频| 中文亚洲视频在线| 先锋影音一区二区三区|