小K的农场

wjh15101051's space

卧薪尝胆，厚积薄发。

小K的农场

Date: Sun Sep 09 23:42:25 CST 2018

In Category: NoCategory

Description：

有 $n$ 个数和 $m$ 个信息： $a$ 比 $b$ 至少大 $x$ ， $a$ 比 $b$ 至多大 $c$ ， $a=b$ ，问是否有一组解。

$1\le n,m \le10000$

Solution：

差分约束 $+$ 深搜 $SPFA$ 判负环。

$a$ 比 $b$ 至少大 $x$ ： $a\xrightarrow{-x}c$

$a$ 比 $b$ 至多大 $c$ ： $b\xrightarrow x a$

$a=b$ ： $a\xrightarrow 0 b,b\xrightarrow 0a$

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 10010

struct edge

{

	int to,nxt,v;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b,int c)

{

	++edgenum;e[edgenum].to = b;e[edgenum].v = c;e[edgenum].nxt = lin[a];lin[a] = edgenum;

	return;

}

bool vis[MAXN];

int d[MAXN];

bool SPFA(int k)

{

	vis[k] = true;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(d[e[i].to] > d[k] + e[i].v)

		{

			d[e[i].to] = d[k] + e[i].v;

			if(vis[e[i].to])return false;

			if(!SPFA(e[i].to))return false;

		}

	}

	vis[k] = false;

	return true;

}

int main()

{

	scanf("%d%d",&n,&m);

	int type,a,b,c;

	for(int i = 1;i <= m;++i)

	{

		scanf("%d",&type);

		if(type == 1)

		{

			scanf("%d%d%d",&a,&b,&c);

			add(a,b,-c);

		}

		if(type == 2)

		{

			scanf("%d%d%d",&a,&b,&c);

			add(b,a,c);

		}

		if(type == 3)

		{

			scanf("%d%d",&a,&b);

			add(a,b,0);

			add(b,a,0);

		}

	}

	memset(d,0x3f,sizeof(d));d[0] = 0;

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

	if(SPFA(0))puts("Yes");

	else puts("No");

	return 0;

}

In tag: 图论-差分约束

wjh15101051