差分约束系统的可行性问题啊……

按照要求连边然后SPFA判负环即可。

代码：

/**************************************************************
    Problem: 3436
    User: danihao123
    Language: C++
    Result: Accepted
    Time:9224 ms
    Memory:1488 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
const int maxn=10005,maxm=30005;
typedef long long ll;
#define REP(i,n) for(i=1;i<=(n);i++)
#define CL_ARR(i,x) memset(i,x,sizeof(i))
#define GRAPH_REP(i,u) for(i=first[(u)];i;i=next[i])
 
int n;
namespace Graph{
    int first[maxn];
    int next[maxm],to[maxm];
    ll dist[maxm];
    int tot=0;
    inline void AddEdge(int u,int v,ll d){
        tot++;
        next[tot]=first[u];
        first[u]=tot;
        to[tot]=v;
        dist[tot]=d;
    }
 
    bool inQueue[maxn];
    ll d[maxn];
    int cnt[maxn];
    bool SPFA(){
        register int i,u;
        queue<int> Q;
        REP(i,n){
            inQueue[i]=true;
            Q.push(i);
        }
        while(!Q.empty()){
            u=Q.front();
            Q.pop();
            inQueue[u]=false;
            GRAPH_REP(i,u){
                if(d[to[i]]>d[u]+dist[i]){
                    d[to[i]]=d[u]+dist[i];
                    if(!inQueue[to[i]]){
                        Q.push(to[i]);
                        inQueue[to[i]]=true;
                        if(++cnt[to[i]]>n)
                            return false;
                    }
                }
            }
        }
        return true;
    }
};
 
int main(){
    int m,opt,a,b,c;
    register int i;
    scanf("%d%d",&n,&m);
    REP(i,m){
        scanf("%d%d%d",&opt,&a,&b);
        if(opt==1){
            scanf("%d",&c);
            Graph::AddEdge(a,b,-c);
        }else{
            if(opt==2){
                scanf("%d",&c);
                Graph::AddEdge(b,a,c);
            }else{
                Graph::AddEdge(a,b,0);
                Graph::AddEdge(b,a,0);
            }
        }
    }
    if(Graph::SPFA())
        puts("Yes");
    else
        puts("No");
    return 0;
}

• 相关文章
• 全局相关文章