M_sea

洛谷1993 小 K 的农场
Luogu算法差分约束裸题。。。对于1操作,从$a$到$b$建$-c$的边。对于2操作,从$b$到$a$建$c$的...
扫描右侧二维码阅读全文
06
2018/01

洛谷1993 小 K 的农场

Luogu

算法

差分约束裸题。。。

对于1操作,从$a$到$b$建$-c$的边。
对于2操作,从$b$到$a$建$c$的边。
对于3操作,$a$和$b$连权值为$0$的双向边。

然后跑SPFA判负环即可。

代码

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#define re register
using namespace std;
typedef int mainint;
#define int long long
inline int read() { //快读
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}

struct Edge { int v,w,nxt; } e[20010]; //图
int head[10010],cnt=0;
inline void addEdge(int u,int v,int w) {
    e[++cnt].v=v; e[cnt].w=w;
    e[cnt].nxt=head[u]; head[u]=cnt;
}

bool if_=false,vis[10010]; //if_是有负环的标志
int dis[10010];
inline void SPFA(int u) { //Dfs版SPFA,判负环
    vis[u]=true;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v,w=e[i].w;
        if (dis[u]+w<dis[v]) {
            if (vis[v]||if_) { if_=true; break; }
            dis[v]=dis[u]+w; SPFA(v);
        }
    }
    vis[u]=false;
}
mainint main() {
    int n,m; n=read(); m=read();
    for (re int i=1;i<=m;i++) { //输入建图
        int opt=read(),a=read(),b=read(),c;
        if (opt==1) { c=read(); addEdge(a,b,-c); }
        if (opt==2) { c=read(); addEdge(b,a,c); }
        if (opt==3) { addEdge(a,b,0); addEdge(b,a,0); }
    }
    for (re int i=1;i<=n;i++) { //判负环
        dis[i]=0; SPFA(i);
        if (if_) break;
    }
    if (if_) puts("No");
    else puts("Yes");
    return 0;
}
最后修改:2018 年 11 月 30 日 09 : 43 PM

发表评论