M_sea

洛谷1993 小 K 的农场
题目描述小 K 在 Minecraft 里面建立很多很多的农场,总共 n 个,以至于他自己都忘记了每个农场中种植作...
扫描右侧二维码阅读全文
06
2018/01

洛谷1993 小 K 的农场

题目描述

小 K 在 Minecraft 里面建立很多很多的农场,总共 n 个,以至于他自己都忘记了每个农场中种植作物的具体数量了,他只记得一些含糊的信息(共 m 个),以下列三种形式描述:

  1. 农场 a 比农场 b 至少多种植了 c 个单位的作物。
  2. 农场 a 比农场 b 至多多种植了 c 个单位的作物。
  3. 农场 a 与农场 b 种植的作物数一样多。

但是,由于小 K 的记忆有些偏差,所以他想要知道存不存在一种情况,使得农场的种植作物数量与他记忆中的所有信息吻合。

传送门

算法

差分约束裸题。。。

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

然后跑SPFA判负环即可。把负环的板子copy过来即可。

更详细的差分约束请戳这里

代码

#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 月 09 日 04 : 35 PM

发表评论