UVA 515 King

差分约束系统的第一个题目，看了落花大神的博客后，对差分约束有了一定了解，关键在于建图，然后就是判断是否存在负权回路。

关于差分约束系统的解释详见维基百科：http://zh.wikipedia.org/wiki/%E5%B7%AE%E5%88%86%E7%BA%A6%E6%9D%9F%E7%B3%BB%E7%BB%9F

利用spfa判断时，当图中有顶点出队次数多于图中顶点数目时说明存在负环。

其实我自己敲上去的时候改了一点点。

大神的time[g[x][i].v]当达到n+1时就返回false，这是不对的，因为点包括0嘛，所以最终应该有n+1个点，判断就应该改为达到n+2，而且这一点也从uva上得到证明，

直接交n+1的版本是过不了的，n+2，才能过。

以下是我改过大神的代码：

 #include <cstdio>

 #include <cstring>

 #include <queue>

 #include <cstdlib>

 #include <vector>

 #define N 110

 using namespace std;

 struct edgeType{

 int v, w;

 edgeType(int a, int b):v(a), w(b){}

 };

 int n, m, d[N], time[N], inq[N];

 char op[];

 vector<edgeType> g[N];

 bool spfa(void)

 {

     queue<int> q;

      time[n] = ;

      inq[n] = ;

      q.push(n);

      while(!q.empty())

      {

          int x = q.front();

          q.pop();

          inq[x] = ;

          for(int i = ; i < g[x].size(); i++)

             if(d[g[x][i].v] > d[x] + g[x][i].w)

          {

              d[g[x][i].v] = d[x] + g[x][i].w;

              time[g[x][i].v]++;

              if(time[g[x][i].v] == n+)

                 return false;

              if(!inq[g[x][i].v])

              {

                  q.push(g[x][i].v);

                  inq[g[x][i].v] = ;

              }

          }

      }

      return true;

 }

 int main(void)

 {

     int a, b, c;

     while(scanf("%d%d",&n, &m)&&n)

     {

         n++;

         memset(d, 0x0f, sizeof(d));

         memset(inq, , sizeof(inq));

         memset(time, , sizeof(time));

         d[n] = ;

         g[n].clear();

         for(int i = ; i < n;i++)

             g[n].push_back(edgeType(i, )), g[i].clear();

         for(int i = ; i < m; i++)

         {

             scanf("%d%d%s%d", &a, &b, op, &c);

             if(op[] == 'g')

                 g[a + b].push_back(edgeType(a - , -c - ));

             else g[a - ].push_back(edgeType(a + b, c - ));

         }

         if(spfa())

             puts("lamentable kingdom");

         else puts("successful conspiracy");

     }

     return ;

 }

然后我利用bellman—ford重新写了一遍，速度慢了将近一半，不知道是不是我写的姿势不对。

来自维基百科的bellman-ford的伪代码:

# initialization

for each v in V do

    d[v] ← ∞;

d[source] ← 0

# Relaxation

for i =1,...,|V|-1 do

    for each edge (u,v) in E do

        d[v] ← min{d[v], d[u]+w(u,v)}

# Negative cycle checking

for each edge (u, v) in E do

    if d[v]> d[u] + w(u,v) then

        no solution

其实就是普通bellman-ford做完之后，再检查所有的边一次，看看能不能继续松弛，如果可以的话，松弛变数会超过：|V|-1,说明必须存在负权环。

 #include <cstdio>

 #include <cstring>

 #include <queue>

 #include <cstdlib>

 #include <vector>

 #define N 110

 using namespace std;

 struct edgeType

 {

     int v, w;

     edgeType(int a, int b):v(a), w(b) {}

 };

 int n, m, d[N], inq[N];

 char op[];

 vector<edgeType> g[N];

 bool bellman_ford(void)

 {

     for(int k = ; k < n; k++)

         for(int x = ; x <= n; x++)

             for(int i = ; i < (int)g[x].size(); i++)

                 if(d[g[x][i].v] > d[x] + g[x][i].w)

                     d[g[x][i].v] = d[x] + g[x][i].w;

     for(int i = ; i <= n; i++)

     {

         for(int k = ; k < (int)g[i].size(); k++)

             if(d[g[i][k].v] > d[i] + g[i][k].w)

                 return false;

     }

     return true;

 }

 int main(void)

 {

     int a, b, c;

     while(scanf("%d",&n)&&n)

     {

         n++;

         scanf("%d", &m);

         memset(d, 0x0f, sizeof(d));

         memset(inq, , sizeof(inq));

         d[n] = ;

         g[n].clear();

         for(int i = ; i < n; i++)

             g[n].push_back(edgeType(i, )), g[i].clear();

         for(int i = ; i < m; i++)

         {

             scanf("%d%d%s%d", &a, &b, op, &c);

             if(op[] == 'g')

                 g[a + b].push_back(edgeType(a - , -c - ));

             else g[a - ].push_back(edgeType(a + b, c - ));

         }

         if(bellman_ford())

             puts("lamentable kingdom");

         else puts("successful conspiracy");

     }

     return ;

 }