zoj 2770 Burn the Linked Camp 差分约束

简介:

  最近状态太散漫,一天才写了这一题,很基础的差分约束,直接写出关系式即可。注意边数开大点


/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#define INF 1E9
using namespace std;
int Dis[1005];
int U[100005];
int next[100005];
int W[100005];
int cnt;
int first[1005];
int n,m;
int add(int v,int u,int w)
{
    next[cnt]=first[v];
    first[v]=cnt;
    U[cnt]=u;
    W[cnt]=w;
    cnt++;
}
bool inq[1005];
int dq[1005];
bool spfa(int v)
{
    memset(Dis,63,sizeof(Dis));
    memset(inq,0,sizeof(inq));
    memset(dq,0,sizeof(dq));
    queue<int> q;
    q.push(v);
    Dis[v]=0;
    int i,u,now,t;
    while(!q.empty())
    {
        v=q.front();q.pop();
        inq[v]=0;dq[v]++;
        if(dq[v]>=n)return 1;
        for(i=first[v];i!=-1;i=next[i])
        {
            u=U[i];
            t=Dis[v]+W[i];
            if(t>=Dis[u])continue;
            Dis[u]=t;
            if(inq[u])continue;
            inq[u]=1;
            q.push(u);
        }
    }
    return 0;
}
int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        cnt=0;
        memset(first,-1,sizeof(first));
        int i,v,u,s;
        for(i=1;i<=n;i++)
        {
            scanf("%d",&s);
            add(i-1,i,s);
            add(i,i-1,0);
        }
        for(i=0;i<m;i++)
        {
            scanf("%d%d%d",&u,&v,&s);
            add(v,u-1,-s);
        }
        if(spfa(n))printf("Bad Estimations\n");
        else printf("%d\n",-Dis[0]);
    }
}


目录
相关文章
ZOJ - Summer 2018 - Contest 2 by Astolfo - Problems - 1002: Hazard and The Triangle
ZOJ - Summer 2018 - Contest 2 by Astolfo - Problems - 1002: Hazard and The Triangle
115 0
ZOJ - Summer 2018 - Contest 2 by Astolfo - Problems - 1002: Hazard and The Triangle
ZOJ - Problem Set - 3960 What Kind of Friends Are You?
ZOJ - Problem Set - 3960 What Kind of Friends Are You?
91 0
ZOJ - Problem Set - 3960 What Kind of Friends Are You?
ZOJ - Summer 2018 - Contest 1 by SBconscious - Problems - 1001: Saber
ZOJ - Summer 2018 - Contest 1 by SBconscious - Problems - 1001: Saber
104 0
|
人工智能 Go
ZOJ 3635 Cinema in Akiba
题意:一群人到电影院看电影,该电影的门票计算比较特殊,如:甲第一个拿到1号门票则位置为1,乙第二个拿票,票号也是1,则位置为2,因为1号位置已经被甲占了,乙的位置为剩下位置中的1号位置。
125 0
ZOJ Problem Set - 3758 素数
ZOJ Problem Set - 3758 素数
103 0

热门文章

最新文章