Is the Information Reliable?(差分约束系统)

题意：给出M条信息，判断这些信息的正确性。(1)V A B ：表示A，B之间的距离>=1; (2)P A B X :表示A B之间的距离为x。

思路：dis[i]表示i到原点的距离，由(1)知 dis[A]<=dis[B]-1 即B->A之间有一条边，权值为-1；由(2)知: dis[A]<=dis[B]-x && dis[B] <= dis[A]+x,即A->B的权值为-x，B->A的权值为x。增加一个超级源点，与所有的点相连且权值为0.建图，spfa判断是否有负环(即判断进站次数，若大于点数则存在负环)。若存在负环则信息为假，否则为真。

 #include <stdio.h>

 #include <string.h>

 #include <queue>

 using namespace std;

 const int N=;

 const int INF=<<;

 int head[],vis[];

 int dis[N],num[];

 int cnt,n;

 struct node

 {

     int u,v,w;

     int next;

 } edge[N];

 void init()

 {

     cnt = ;

     memset(head,-,sizeof(head));

     memset(vis,,sizeof(vis));

     memset(num,,sizeof(num));

 }

 void add(int u,int v,int w)

 {

     edge[cnt].u = u;

     edge[cnt].v = v;

     edge[cnt].w = w;

     edge[cnt].next = head[u];

     head[u] = cnt++;

 }

 int spfa()

 {

     queue<int>q;

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

         dis[i] = INF;

     dis[] = ;

     q.push();

     vis[] = ;

     while(!q.empty())

     {

         int u = q.front();

         vis[u] = ;

         q.pop();

         for (int j = head[u]; j!=-; j=edge[j].next)

         {

             int v = edge[j].v;

             int w = edge[j].w;

             if (dis[v] > dis[u]+w)

             {

                 dis[v] = dis[u]+w;

                 if (!vis[v])

                 {

                     q.push(v);

                     vis[v] = ;

                     ++num[v];

                     if (num[v] > n)

                         return ;

                 }

             }

         }

     }

     return ;

 }

 int main()

 {

     int m,u,v,w;

     char s[];

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

     {

         init();

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

             add(,i,);

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

         {

             scanf("%s",s);

             if (s[]=='P')

             {

                 scanf("%d %d %d",&u,&v,&w);

                 add(u,v,w);

                 add(v,u,-w);

             }

             if (s[]=='V')

             {

                 scanf("%d %d",&u,&v);

                 add(v,u,-);

             }

         }

         if (spfa())

             printf("Reliable\n");

         else

             printf("Unreliable\n");

     }

     return ;

 }

巴特西

Is the Information Reliable?(差分约束系统)

最新文章

热门文章