[HNOI2005]狡猾的商人

Luogu P2294

bzoj 1202

思路

对于收益的前缀和差分约束一下即可

代码

#include <iostream>
#include <cstdio>
#include <queue>

struct Node{
    struct Edge *head;
    int dis, tim;
    bool vis;
}node[110];
struct Edge{
    Node *to;
    Edge *ne;
    int val;
    Edge(int x, int y, int z) : to(&node[y]), ne(node[x].head), val(z){}
};

int n, m;
bool fl;

void SPFA(Node *s){
    std::queue<Node *>q;
    s->dis=0;
    s->vis=true;
    q.push(s);
    s->tim++;
    while(!q.empty()){
        Node *x=q.front();
        q.pop();
        x->vis=false;
        for(Edge *i=x->head; i; i=i->ne)
            if(i->to->dis>x->dis+i->val){
                i->to->dis=x->dis+i->val;
                if(!i->to->vis){
                    i->to->vis=true;
                    i->to->tim++;
                    if(i->to->tim>n)
                        fl=false;
                    else
                        q.push(i->to);
                }
            }
    }
}

int main(){
    int w, x, y, z;
    scanf("%d", &w);
    while(w--){
        scanf("%d%d", &n, &m);
        fl=true;
        for(int i=0; i<=n; i++)
            node[i].head=NULL, node[i].dis=0x3f3f3f3f, node[i].vis=false, node[i].tim=0;
        for(int i=1; i<=m; i++){
            scanf("%d%d%d", &x, &y, &z);
            x--;
            node[x].head=new Edge(x, y, z);
            node[y].head=new Edge(y, x, -z);
        }
        for(int i=0; i<=n; i++)
            if(node[i].dis==0x3f3f3f3f)
                SPFA(&node[i]);
        puts(fl ? "true" : "false");
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注