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

            O(1) 的小樂

            Job Hunting

            公告

            記錄我的生活和工作。。。
            <2010年8月>
            25262728293031
            1234567
            891011121314
            15161718192021
            22232425262728
            2930311234

            統計

            • 隨筆 - 182
            • 文章 - 1
            • 評論 - 41
            • 引用 - 0

            留言簿(10)

            隨筆分類(70)

            隨筆檔案(182)

            文章檔案(1)

            如影隨形

            搜索

            •  

            最新隨筆

            最新評論

            閱讀排行榜

            評論排行榜

            POJ 3169 差分約束方程

            一道簡單的差分約束方程,差分約束方程由Bellmanford轉換而來,一組差分方程由 x-y <=d 的形式,而在最短路中松弛條件有dis(x)<= dis(y)+w。 所以產生了一條由y連向x的有向邊,權重為d。

            https://github.com/Sosi/ProgrammingContest/blob/master/OnlineJudge/POJ/PKU3169.cpp

               1:   
               2:  #include <queue>
               3:  #include <iostream>
               4:  #include <string.h>
               5:  #include <stdio.h>
               6:  using namespace std;
               7:  #define MAXN 1005      // vertex
               8:  #define MAXM 20005      // edge
               9:  #define INF 0x3F3F3F3F
              10:   
              11:  struct node
              12:  {
              13:      int v, w, next;
              14:  }pnt[MAXM];
              15:   
              16:  int head[MAXN];
              17:  int  dis[MAXN];
              18:  bool vis[MAXN];
              19:  int  cnt[MAXN];       // the number of the operation of push to Quque. negatvie cycle.
              20:  int num = 0;          // the index of the edge
              21:  int N ;               // the number of the vertex.
              22:  int M ;               // the number of edges
              23:  int src, sink;
              24:  void addedge(int  u, int v, int w)
              25:  {
              26:      pnt[num].v = v; pnt[num].w= w;
              27:      pnt[num].next = head[u]; head[u] = num++;
              28:  }
              29:   
              30:  int SPFA()
              31:  {
              32:      for(int i=0; i<=N; i++)
              33:      {
              34:          vis[i]=0; dis[i] = INF; cnt[i] = 0;
              35:      }
              36:   
              37:      queue<int> Q;
              38:      Q.push(src); vis[src] = 1; dis[src] = 0; ++cnt[src]; 
              39:      while(!Q.empty()) 
              40:      {
              41:          int u = Q.front(); Q.pop();  vis[u] = 0;
              42:          for(int i=head[u]; i!=-1; i=pnt[i].next)
              43:          {
              44:              int v = pnt[i].v;
              45:              if( dis[v] > dis[u] + pnt[i].w  )
              46:              {
              47:                  dis[v] = dis[u] + pnt[i].w;
              48:                  if(!vis[v]) {Q.push(v); vis[v] = 1;}
              49:                  if( ++cnt[v] > N) return -1; // negative cycle.
              50:              }
              51:          }
              52:      }
              53:      if(dis[sink] == INF) return -2; // can't from src to sink.
              54:      return dis[sink];
              55:  }
              56:   
              57:  int main()
              58:  {
              59:      int ml,md;
              60:      while(scanf("%d%d%d", &N , &ml, &md)!= EOF)
              61:      {
              62:          num = 0;
              63:          memset(head, -1, sizeof(head)); 
              64:          int a, b, c;
              65:          for(int i=0; i<ml; i++)
              66:          {
              67:              scanf("%d%d%d", &a, &b, &c);
              68:              if(a>b) swap(a,b);
              69:              addedge(a, b,c);
              70:          }
              71:          for(int i=0; i<md; i++)
              72:          {
              73:              scanf("%d%d%d", &a, &b, &c);
              74:              if(a<b) swap(a,b);
              75:              addedge(a, b, -c);
              76:          }
              77:          src = 1; sink = N;
              78:          printf("%d\n", SPFA());
              79:      }
              80:      return 0;
              81:  }
            .csharpcode, .csharpcode pre { font-size: small; color: black; font-family: consolas, "Courier New", courier, monospace; background-color: #ffffff; /*white-space: pre;*/ } .csharpcode pre { margin: 0em; } .csharpcode .rem { color: #008000; } .csharpcode .kwrd { color: #0000ff; } .csharpcode .str { color: #006080; } .csharpcode .op { color: #0000c0; } .csharpcode .preproc { color: #cc6633; } .csharpcode .asp { background-color: #ffff00; } .csharpcode .html { color: #800000; } .csharpcode .attr { color: #ff0000; } .csharpcode .alt { background-color: #f4f4f4; width: 100%; margin: 0em; } .csharpcode .lnum { color: #606060; }

            posted on 2012-11-09 21:38 Sosi 閱讀(656) 評論(0)  編輯 收藏 引用

            統計系統
            中文字幕亚洲综合久久2| 久久综合88熟人妻| 狠狠88综合久久久久综合网| 久久中文字幕一区二区| 新狼窝色AV性久久久久久| 国产亚洲美女精品久久久2020| 久久久久久久精品妇女99| 国产精品美女久久久久| 亚洲美日韩Av中文字幕无码久久久妻妇| 久久综合丝袜日本网| 久久人人爽人爽人人爽av | 久久影院亚洲一区| 久久亚洲高清观看| 久久精品国产亚洲AV久| 精品国产乱码久久久久软件| 久久超碰97人人做人人爱| 中文国产成人精品久久亚洲精品AⅤ无码精品 | 少妇人妻综合久久中文字幕| 国产欧美久久一区二区| 国产精品欧美久久久久无广告 | 亚洲中文久久精品无码| 久久婷婷五月综合成人D啪| 久久精品无码专区免费东京热| 精品久久久无码人妻中文字幕豆芽 | 久久久久久亚洲精品成人| 精品久久久久久久久久久久久久久| 51久久夜色精品国产| 午夜天堂av天堂久久久| 久久免费看黄a级毛片| 国产精品美女久久久久久2018| 久久精品女人天堂AV麻| 国产精品美女久久久久| 久久久受www免费人成| 亚洲午夜久久久久久久久电影网| 久久精品国产亚洲7777| 久久亚洲中文字幕精品一区| 久久香蕉国产线看观看99| 精品国产婷婷久久久| 国产成人久久AV免费| 久久久久亚洲av无码专区导航| 久久SE精品一区二区|