P1993 小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。

思路

　　差分约束，有三种情况

　　1、a - b >= c，连正边

　　2、a - b <= c，连反边

　　3、a - b = 0，边权为0，且是 a -> b = b -> a = 0;

CODE

  1 #include <bits/stdc++.h>
  2 #define dbg(x) cout << #x << "=" << x << endl
  3 #define eps 1e-8
  4 #define pi acos(-1.0)
  5 
  6 using namespace std;
  7 typedef long long LL;
  8 
  9 template<class T>inline void read(T &res)
 10 {
 11     char c;T flag=1;
 12     while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
 13     while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
 14 }
 15 
 16 namespace _buff {
 17     const size_t BUFF = 1 << 19;
 18     char ibuf[BUFF], *ib = ibuf, *ie = ibuf;
 19     char getc() {
 20         if (ib == ie) {
 21             ib = ibuf;
 22             ie = ibuf + fread(ibuf, 1, BUFF, stdin);
 23         }
 24         return ib == ie ? -1 : *ib++;
 25     }
 26 }
 27 
 28 int qread() {
 29     using namespace _buff;
 30     int ret = 0;
 31     bool pos = true;
 32     char c = getc();
 33     for (; (c < '0' || c > '9') && c != '-'; c = getc()) {
 34         assert(~c);
 35     }
 36     if (c == '-') {
 37         pos = false;
 38         c = getc();
 39     }
 40     for (; c >= '0' && c <= '9'; c = getc()) {
 41         ret = (ret << 3) + (ret << 1) + (c ^ 48);
 42     }
 43     return pos ? ret : -ret;
 44 }
 45 
 46 const int maxn = 1e4 + 7;
 47 const int inf = 0x3f3f3f3f;
 48 
 49 int n,m;
 50 
 51 int head[maxn << 1], edge[maxn << 1], nxt[maxn << 1];
 52 int c[maxn << 1];
 53 int cnt;
 54 int dis[maxn], in[maxn];
 55 bool vis[maxn];
 56 
 57 void BuildGraph(int u, int v, int w) {
 58     cnt++;
 59     edge[cnt] = v;
 60     nxt[cnt] = head[u];
 61     c[cnt] = w;
 62     head[u] = cnt;
 63 }
 64 
 65 bool spfa(int u) {
 66     //memset(dis, -1, sizeof(dis));
 67     vis[u] = 1;
 68     dis[u] = 0;
 69     in[u] = 1;
 70     queue <int> q;
 71     q.push(u); 
 72     while(!q.empty()) {
 73         u = q.front();
 74         q.pop();
 75         vis[u] = 0;
 76         for (int i = head[u]; i ; i = nxt[i]) {
 77             int v = edge[i];
 78             int w = c[i];
 79             if(dis[v] < dis[u] + w) {
 80                 dis[v] = dis[u] + w;
 81                 if(!vis[v]) {
 82                     q.push(v);
 83                     vis[v] = 1;
 84                     ++in[v];
 85                     if(in[v] > n + 1) {
 86                         return true;
 87                     }
 88                 }
 89             }
 90         }
 91     }
 92     return false;
 93 }
 94 
 95 int main()
 96 {
 97     scanf("%d %d",&n, &m);
 98     for ( int i = 1; i <= m; ++i ) {
 99         int opt;
100         int u, v, w;
101         scanf("%d",&opt);
102         if(opt == 1) {
103             scanf("%d %d %d",&u, &v, &w);
104             BuildGraph(u, v, w);
105         }
106         else if(opt == 2) {
107             scanf("%d %d %d",&u, &v, &w);
108             BuildGraph(u, v, -w);
109         }
110         else {
111             scanf("%d %d",&u, &v);
112             BuildGraph(u, v, 0);
113             BuildGraph(v, u, 0);
114         }
115     }
116     for ( int i = 1; i <= n; ++i ) {
117         BuildGraph(0, i, 0);
118         dis[i] = -inf;
119     }
120     if(spfa(0)) {
121         puts("No");
122     }
123     else {
124         puts("Yes");
125     }
126     return 0;
127 }

View Code