luogu 1993 小k的农场

题目描述

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

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

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

输入格式

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

接下来 m 行：

如果每行的第一个数是 1，接下来有 3 个整数 a,b,c，表示农场 a 比农场 b 至少多种植了 c 个单位的作物。

如果每行的第一个数是 2，接下来有 3 个整数 a,b,c，表示农场 a 比农场 b 至多多种植了 c 个单位的作物。如果每行的第一个数是 3，接下来有 2 个整数 a,b，表示农场 a 种植的的数量和 b 一样多。

输出格式

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

输入输出样例

输入 #1

输出 #1

Yes

说明/提示

对于 100% 的数据保证：1 ≤ n，m，a，b，c ≤ 10000。

分析

差分约束，和糖果很像有木有

至多那个加成负权就好，0那个要连双向

跑一个最长路，看有没有环

这题竟然卡SPFA，加优化就好

代码

  1 /**************************
  2 User:Mandy.H.Y
  3 Language:c++
  4 Problem:luogu1993
  5 Algorithm:
  6 **************************/
  7 #include<bits/stdc++.h>
  8 
  9 using namespace std;
 10 
 11 const int maxn = 1e4 + 5;
 12 
 13 int n,m,size;
 14 int dis[maxn],cnt[maxn];
 15 bool vis[maxn];
 16 int first[maxn];
 17 int q[100005],l,r;
 18 
 19 struct Edge{
 20     int v,w,nt;
 21 }edge[maxn << 1];
 22 
 23 template<class T>inline void read(T &x){
 24     x = 0;bool flag = 0;char ch = getchar();
 25     while(!isdigit(ch)) flag |= ch == '-',ch = getchar();
 26     while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48),ch = getchar();
 27     if(flag) x = -x;
 28 }
 29 
 30 void file(){
 31     freopen("testdata.in","r",stdin); 
 32 //    freopen("1993.out","w",stdout); 
 33 }
 34 
 35 void eadd(int u,int v,int w){
 36     edge[++size].v = v;
 37     edge[size].w = w;
 38     edge[size].nt = first[u];
 39     first[u] = size;
 40 }
 41 
 42 void readdata(){
 43     read(n);read(m);
 44     for(int i = 1;i <= m; ++ i){
 45         int opt,a,b,c;
 46         read(opt);
 47         switch(opt){
 48             case 1:{
 49                 read(a);read(b);read(c);
 50                 eadd(b,a,c);
 51                 break;
 52             }
 53             case 2:{
 54                 read(a);read(b);read(c);
 55                 eadd(a,b,-c);
 56                 break;
 57             }
 58             default:{
 59                 read(a);read(b);
 60                 eadd(a,b,0);
 61                 eadd(b,a,0);
 62                 break;
 63             }
 64         }
 65         if(opt == 1 && a == b && c != 0) {
 66             puts("No");
 67             exit(0);
 68         }
 69     }
 70 }
 71 
 72 void work(){
 73 //    queue<int>q;
 74     for(int i = 1;i <= n ; ++ i){
 75         q[r++] = i;
 76         vis[i] = 1;
 77     }
 78     while(l != r){
 79         int u = q[l];
 80         l++;
 81         l %= 100000;
 82         vis[u] = 0;
 83         int rr = (r-1 + 100000) % 100000;
 84         if(l != r) if(dis[q[l]] < dis[q[rr]]) swap(q[l],q[rr]);
 85         if(cnt[u] > n) {
 86             puts("No");
 87             return;
 88         } 
 89         for(int i = first[u];i;i = edge[i].nt){
 90             int v = edge[i].v;
 91             int w = edge[i].w;
 92             
 93             if(dis[v] < dis[u] + w){
 94                 dis[v] = dis[u] + w;
 95                 cnt[v] = cnt[u] + 1;
 96                 if(!vis[v]) {
 97                     q[r++] = v;
 98                     r %= 100000;
 99                     int rr = (r-1 + 100000) % 100000;
100                     if(l != r) if(dis[q[l]] < dis[q[rr]]) swap(q[l],q[rr]);
101                     vis[v] = 1;
102                 }
103             }
104         }
105     }
106     puts("Yes");
107 }
108 
109 int main(){
110 //    file();
111     readdata();
112     work();
113     return 0;
114 }

View Code