小K的农场（差分约束）

题目大意

n个点 m条描述

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

题解

差分约束裸题

可以把m条描述转换成一张图

ai-bi≥c--->bi-ai≤-c ai向bi连边权值为-c

ai-bi≤c bi向ai连边权值为c

ai-bi≥0并且ai-bi≤0所以ai和bi之间连双向边....

开始我不明白为什么要虚拟一个0点...原来图可能不连通....

判断负环...要用spfa的dfs判断效率更高

代码

#include<iostream>

#include<cstring>

#include<cstdio>

#define mmx 100003

using namespace std;

int n,m,a,b,c,od,flag,sumedge;

int dis[mmx],vis[mmx],head[mmx];

inline int read(){

    register char ch=getchar();register int x=,f=;

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&& ch<=''){x=x*+ch-'';ch=getchar();}

    return f*x;

}

struct Edge{

    int x,y,z,nxt;

    Edge(int x=,int y=,int z=,int nxt=):

        x(x),y(y),z(z),nxt(nxt){}

}edge[mmx<<];

inline void add(int x,int y,int z){

    edge[++sumedge]=Edge(x,y,z,head[x]);

    head[x]=sumedge;

}

inline void spfa(int now){

    vis[now]=;

    for(int i=head[now];i;i=edge[i].nxt){

        int v=edge[i].y ;

        if(dis[v]>dis[now]+edge[i].z){

            dis[v]=dis[now]+edge[i].z;

            if(vis[v]){flag=;return;}

            spfa(v);

        }

    }

    vis[now]=;

}

int main(){

    n=read();m=read();

    for(register int i=;i<=m;i++){

        od=read();a=read();b=read();

        if(od==){c=read();add(a,b,-*c);}

        if(od==){c=read();add(b,a,c);}

        if(od==){add(a,b,);add(b,a,);}

    }

    for(register int i=;i<=n;i++)add(,i,);

    memset(dis,/,sizeof(dis));

    dis[]=;spfa();

    if(flag)printf("No\n");

    else printf("Yes\n");

    return ;

}

巴特西

小K的农场（差分约束）

最新文章

热门文章