程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> POJ 3169 Layout (差分約束系統）

POJ 3169 Layout (差分約束系統）

編輯：C++入門知識

POJ 3169 Layout (差分約束系統）

題目地址：POJ 3169

很簡單的差分約束。。公式很明顯。當輸入最大值的時候，是a-b<=c，最小值的時候是a-b>=c。然後根據這個式子用最短路求。

代碼如下：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;
const int INF=0x3f3f3f3f;
int d[2000], head[2000], cnt, source, sink, aa[2000];
struct node
{
    int u, v, w, next;
} edge[1000000];
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 berman(int n)
{
    //memset(vis,0,sizeof(vis));
    int i, j, flag;
    memset(d,INF,sizeof(d));
    d[1]=0;
    for(i=1;i<=n;i++)
    {
        flag=0;
        for(j=0;jd[edge[j].u]+edge[j].w)
            {
                d[edge[j].v]=d[edge[j].u]+edge[j].w;
                flag=1;
            }
        }
        if(!flag)
            break;
    }
    for(i=0;id[edge[i].u]+edge[i].w)
        {
            return 0;
        }
    }
    return 1;
}
int main()
{
    int n, ml, md, a, b, c, i, j, x;
    scanf("%d%d%d",&n,&ml,&md);
    memset(head,-1,sizeof(head));
    cnt=0;
    while(ml--)
    {
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
        //add(b,a,c);
    }
    while(md--)
    {
        scanf("%d%d%d",&a,&b,&c);
        add(b,a,-c);
        //add(a,b,-c);
    }
    x=berman(n);
    if(!x)
        printf("-1\n");
    else
    {
        if(d[n]==INF)
            printf("-2\n");
        else
        printf("%d\n",d[n]);
    }
    return 0;
}