【洛谷 1993】 小 K 的农场

题目描述

小 K 在 MC 里面建立很多很多的农场，总共 nnn 个，以至于他自己都忘记了每个农场中种植作物的具体数量了，他只记得一些含糊的信息（共 mmm 个），以下列三种形式描述：

• 农场 aaa 比农场 bbb 至少多种植了 ccc 个单位的作物；
• 农场 aaa 比农场 bbb 至多多种植了 ccc 个单位的作物；
• 农场 aaa 与农场 bbb 种植的作物数一样多。

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

输入格式

第一行包括两个整数 nnn 和 mmm，分别表示农场数目和小 K 记忆中的信息数目。

接下来 mmm 行：

• 如果每行的第一个数是 111，接下来有三个整数 a,b,ca,b,ca,b,c，表示农场 aaa 比农场 bbb 至少多种植了 ccc 个单位的作物；
• 如果每行的第一个数是 222，接下来有三个整数 a,b,ca,b,ca,b,c，表示农场 aaa 比农场 bbb 至多多种植了 ccc 个单位的作物;
• 如果每行的第一个数是 333，接下来有两个整数 a,ba,ba,b，表示农场 aaa 种植的的数量和 bbb 一样多。

输出格式

如果存在某种情况与小 K 的记忆吻合，输出 Yes，否则输出 No。

输入输出样例

输入 #1 复制

3 3
3 1 2
1 1 3 1
2 2 3 2

输出 #1 复制

Yes

说明/提示

对于 100%100\%100% 的数据，保证 1≤n,m,a,b,c≤5×1031 le n,m,a,b,c le 5 imes 10^31≤n,m,a,b,c≤5×103。

题解：一道很水的差分约束 但我调试好久。。。。头都炸了

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N=10002;
int n,m,x,y,z,yc;

struct node{
    int to,next,w;
}e[N*2];

int dis[N],vis[N],tot[N],cnt,head[N];

void add(int x,int y,int z){
    e[++cnt].to=y;
    e[cnt].w=z;
    e[cnt].next=head[x];
    head[x]=cnt;
} 

string spfa(){
    queue<int>q;
    memset(tot,0,sizeof(tot));
    memset(dis,0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    vis[n+1]=1; dis[n+1]=0; q.push(n+1); tot[n+1]=1;
    while(!q.empty()){
        int u=q.front(); vis[u]=0; q.pop();
        for(int i=head[u];i;i=e[i].next){
            int v=e[i].to;
            if(dis[v]>dis[u]+e[i].w){
                dis[v]=dis[u]+e[i].w;
                if(!vis[v]){
                    vis[v]=1; tot[v]++; 
                    q.push(v); 
                    if(tot[v]>=n+1) return "No";
                }
                
            }
        } 
    } 
    return "Yes";
}

int main(){
    freopen("1993.in","r",stdin);
    freopen("1993.out","w",stdout);
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d",&yc);
        if(yc==3){
            scanf("%d %d",&x,&y);
            add(x,y,0); 
            add(y,x,0);
        }
        if(yc==1){
            scanf("%d %d %d",&x,&y,&z);
            add(x,y,-z);
        }
        if(yc==2){
            scanf("%d %d %d",&x,&y,&z);
            add(y,x,z);
        }
    }
    for(int i=1;i<=n;i++)
        add(n+1,i,0);
    cout<<spfa();
    return 0;
}