「题解」小K的农场

(未完待续)

题目链接:BZOJ 3436/Luogu P1993/信息学奥赛一本通 T1724

题目

题目描述

小 K 建立了 $n$ 个农场,他忘记了每个农场中种植作物的具体数量,只记得一些含糊的信息(共 $m$ 个),以下列三种形式描述:

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

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

数据范围

变量数据范围
$n,m,a,b,c$$1\leq n,m,a,b,c\leq 10^4$

时空限制

题解

思路

显然是差分约束系统,具体方法就不展开讲了。

因为这道题是判断负环(求最长路的话是正环),所以推荐使用 $\texttt{DFS}$ 版本的 $\texttt{SPFA}$。

代码

$\texttt{DFS}$ 版本的 $\texttt{SPFA}$,没什么好说的。

#include<cstdio>
const int MAXN=10000+5;
bool inStack[MAXN],vis[MAXN];
int n,m;
int cnt,head[MAXN],to[MAXN<<2],w[MAXN<<2],Next[MAXN<<2];
int dis[MAXN];
void Add_Edge(int,int,int);
bool SPFA(int);
int main(void){
    register int i;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;++i){//确保图的连通性
        Add_Edge(i,0,0);
        Add_Edge(n+1,i,0);
    }
    for(i=1;i<=m;++i){//信息数目为m
        static int opt,a,b,c;
        scanf("%d%d%d",&opt,&a,&b);
        if(opt==3){
            Add_Edge(a,b,0);
            Add_Edge(b,a,0);
        }
        else{
            scanf("%d",&c);
            if(opt==1)
                Add_Edge(a,b,c);
            if(opt==2)
                Add_Edge(b,a,-c);
        }
    }
    puts(SPFA(n+1)?"Yes":"No");//从n+1出发,求最短路,判断负环
    return 0;
}
void Add_Edge(int u,int v,int len){
    Next[++cnt]=head[u];
    to[cnt]=v;
    w[cnt]=len;
    head[u]=cnt;
    return;
}
bool SPFA(int ID){//超级压行的DFS版本的SPFA
    register int i;
    for(inStack[ID]=true,i=head[ID];i;i=Next[i])
        if((!vis[to[i]]||dis[to[i]]<dis[ID]+w[i])&&(inStack[to[i]]||(vis[to[i]]=true,dis[to[i]]=dis[ID]+w[i],!SPFA(to[i]))))
            return false;
    return !(inStack[ID]=false);
}