• <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>

            POJ 3259 Wormholes


            Bellman_Ford 算法,

            利用Bellman_Ford算法判斷是否存在負回路。如果存在負回路就一定可以回到(不停的走這個回路,直到賺到的負值夠與回去的值抵消的),如果不存在一定不可以回去。
            用cin500+ms, 用scanf  100+ms

            #include<iostream>
            #include
            <stdio.h>
            using namespace std;
            const int INF=0x0fffffff;
            struct type
            {
                   
            int s,t;
                   
            int len;
            }edge[
            30000];

            int n,m,w,nedge=0;
            int d[505];
            bool Bellman_Ford()
            {
                 
            bool isPossible=false;
                 
            for(int j=1; j<=n; j++)d[j]=INF;
                 d[
            1]=0;
                 
            int u,v;
                 
            bool f;
                 
            for(int j=1; j<=n-1; j++)
                 {
                         f
            =0;
                         
            for(int k=1; k<=nedge; k++)
                         {
                                 u
            =edge[k].s; v=edge[k].t;
                                 
            if(d[v]>d[u]+edge[k].len)
                                             d[v]
            =d[u]+edge[k].len;
                                 f
            =1;            
                         }
                         
            if(f==0)return false;
                 }
              /*前面n-1次循環可以求出無負回路時的最短路徑,再來一次如果可以更新就一定有負回路。/*
                  
            for(int k=1; k<=nedge; k++)
                         {
                                 u
            =edge[k].s; v=edge[k].t;
                                 
            if(d[v]>d[u]+edge[k].len)
                                       {  d[v]
            =d[u]+edge[k].len; return 1;}
                                            
                         }
                 
                
            // system("pause");
                 return 0;
                 
            }

            int main()
            {
                
            int t;
                cin
            >>t;
                
            while(t--)
                {
                          
            int i,j,u,v,value;
                          scanf(
            "%d %d %d",&n,&m,&w);//cin>>n>>m>>w;
                          nedge=0;
                          
            for(int i=1; i<=m; i++)
                          {
                                  scanf(
            "%d %d %d",&u,&v,&value);//cin>>u>>v>>value;
                                  ++nedge;
                                  edge[nedge].s
            =u;
                                  edge[nedge].t
            =v;
                                  edge[nedge].len
            =value;
                                  
            ++nedge;
                                  edge[nedge].s
            =v;
                                  edge[nedge].t
            =u;
                                  edge[nedge].len
            =value;
                          }     
                              
                          
            for(int i=1; i<=w; i++)
                          {
                                  scanf(
            "%d %d %d",&u,&v,&value);//cin>>u>>v>>value;
                                  ++nedge;
                                  edge[nedge].s
            =u;
                                  edge[nedge].t
            =v;
                                  edge[nedge].len
            =-value;
                                  
                                 
            /* ++nedge;
                                  edge[nedge].s=v;
                                  edge[nedge].t=u;
                                  edge[nedge].len=-value;
                                  
            */
                          }
                          
                          
            if(Bellman_Ford())
                                     cout
            <<"YES"<<endl;
                          
            else       cout<<"NO"<<endl;
                 
                }
                system(
            "pause");
                
            return 0;
            }

            posted on 2010-08-09 19:38 田兵 閱讀(723) 評論(0)  編輯 收藏 引用 所屬分類: POJ

            <2010年8月>
            25262728293031
            1234567
            891011121314
            15161718192021
            22232425262728
            2930311234

            導航

            統計

            常用鏈接

            留言簿(2)

            隨筆分類(65)

            隨筆檔案(65)

            文章檔案(2)

            ACM

            搜索

            積分與排名

            最新隨筆

            最新評論

            閱讀排行榜

            日韩精品久久久久久| 久久精品国产精品亚洲精品| 久久91精品国产91| 精品久久久久一区二区三区| 久久九九亚洲精品| 久久综合综合久久97色| 久久综合欧美成人| 久久精品国产72国产精福利| 久久久久一区二区三区| 97久久精品无码一区二区天美| 久久九九精品99国产精品| 久久无码国产| 性色欲网站人妻丰满中文久久不卡| 亚洲一本综合久久| 久久久久成人精品无码| 久久久久久精品成人免费图片| 四虎国产精品成人免费久久| 久久妇女高潮几次MBA| 亚洲AV无码成人网站久久精品大| 97久久精品无码一区二区| 漂亮人妻被黑人久久精品| 久久免费大片| 久久久久久国产a免费观看黄色大片| 久久亚洲精品国产亚洲老地址 | 热99RE久久精品这里都是精品免费 | 久久99久久无码毛片一区二区 | 欧美精品久久久久久久自慰| 日韩欧美亚洲国产精品字幕久久久 | 精品综合久久久久久97| 色欲综合久久躁天天躁| 九九热久久免费视频| 国内精品久久久久久久久| 精品久久久久久99人妻| 麻豆精品久久久一区二区| 91精品国产色综久久| 狠狠色综合网站久久久久久久| avtt天堂网久久精品| 曰曰摸天天摸人人看久久久| 热久久国产精品| 国产A级毛片久久久精品毛片| 91精品国产高清久久久久久91|