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
3 3 3 1 2 1 1 3 1 2 2 3 2
输出 #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 }
得物app公司福利 402人发布
