## Title Description

Little K has built lots and lots of farms in MC, a total of N, so that he has forgotten the specific amount of crops planted on each farm. He only remembered some vague information (a total of M), described in the following three forms:

- Farm a has at least planted more than C units of crop than farm B.
- Farms a planted more than C units of crops from farms B to more.
- Farm a and farm B grow a lot of crops.

However, because the memory of the little K was somewhat deviant, he wanted to know that there was no existence and that the number of crops planted on the farm coincided with all the information in his memory.

## Input-output format

Input format:

The first line consists of two integers n and m, respectively, representing the number of farms and the number of information in small K memory.

Next M line:

If the first number of rows is 1, then there are 3 integers a, B, C, indicating that farm a is at least more planted than farm B.

A crop of C units.

If the first number of rows is 2, then there are 3 integers a, B, C, which indicate farm a is more than B.

A crop of C units. If the first number of rows is 3, the family has 2 integers a, B, indicating the termination of farm a.

The number is as much as B.

Output format:

If there is a certain case that coincides with the memory of small K, output “Yes” or output “No”.

## Input and output sample

```
3 3
3 1 2
1 1 3 1
2 2 3 2
```

```
Yes
```

## Explain

For data assurance of 100%: 1 or less N, m, a, B, C = 10000.

Ideas:Let d[i] represent the value of point I.

So for constraints

1:d[a]-d[b]>=c

2:d[a]-d[b]<=c

3:d[a]=d[b]

Let’s change the way a little.

1:d[b]<=d[a]-c

2:d[a]<=d[b]+c

3:d[a]<=d[b]+0,d[b]<=d[a]+0

Isn’t this exactly like the definition of dist in the shortest path? The distance between each point is less than equal to the distance + edge weight that can reach his point.

So we turn it into a shortest path model.

For constraints

1:We are a (B, -c).

2:We are B (a, c).

3:We connect the edge (a, B, 0), (B, a, 0).

Because d[i]> =0, so we build a starting point s, to all points connected to a (s, I, 0) edge.

Then d[s] obviously =0.

We find that running a shortest path can determine the D value of each point.

When is it unsolved? Of course, it is impossible to determine the shortest path at each point, that is, a negative weight loop exists in the graph.

After we finish the map, we can judge whether there is a negative ring.

#include<queue> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define MAXN 100010 using namespace std; queue<int>que; int n,m,tot,flag; int dis[MAXN],vis[MAXN]; int to[MAXN],cap[MAXN],net[MAXN],head[MAXN]; void add(int u,int v,int w){ to[++tot]=v;cap[tot]=w;net[tot]=head[u];head[u]=tot; } void spfa(int x){ if(flag) return ; vis[x]=1; for(int i=head[x];i;i=net[i]) if(dis[to[i]]>dis[x]+cap[i]){ dis[to[i]]=dis[x]+cap[i]; if(vis[to[i]]){ flag=1;return ; } spfa(to[i]); } vis[x]=0; } int main(){ freopen("farm.in","r",stdin); freopen("farm.out","w",stdout); scanf("%d%d",&n,&m); for(int i=1;i<=m;i++){ int opt,x,y,z; scanf("%d",&opt); if(opt==1){ scanf("%d%d%d",&x,&y,&z); add(x,y,-z); } else if(opt==2){ scanf("%d%d%d",&x,&y,&z); add(y,x,z); } else if(opt==3){ scanf("%d%d",&x,&y); add(x,y,0); add(y,x,0); } } for(int i=1;i<=n;i++) add(0,i,0); memset(dis,0x7f,sizeof(dis)); dis[0]=0;spfa(0); if(flag) printf("No"); else printf("Yes"); } /* 3 3 3 1 2 1 1 3 1 2 2 3 2 */ /* 10 10 3 9 5 1 6 1 1 1 2 8 0 1 2 8 1 2 4 5 0 1 1 2 1 1 10 5 0 1 10 1 0 2 6 7 0 2 9 3 0 */

### Similar Posts:

- P1993 small K farm
- P1993 small K farm
- P1546 shortest network Agri-Net
- P1546 shortest network Agri-Net
- POJ 3268 Silver Cow Party
- BZOJ1827[USACO 2010 Mar Gold 1.Great Cow Gathering] — traversal of trees
- BZOJ1827[USACO 2010 Mar Gold 1.Great Cow Gathering] — traversal of trees
- Agri-Net (minimum spanning tree)
- Agri-Net (minimum spanning tree)
- POJ Layout