Tag:SPFA differential constraint system
Article From:https://www.cnblogs.com/cangT-Tlan/p/9063498.html

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

Input sample #1: replication

3 3
3 1 2
1 1 3 1
2 2 3 2
Output sample #1: replication

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
*/     

 

Link of this Article: P1993 small K farm in La Valley

Leave a Reply

Your email address will not be published. Required fields are marked *