【luogu P1993 小K的农场】题解

题目链接：https://www.luogu.org/problemnew/show/P1993

1.差分约束：

对于a - b <= c 有一条 b——>a 权值为c

对于a - b >= c 有一条 a——>b 权值为-c

对于一个差分约束系统，若存在负环则无解

2.dfs版SPFA判负环

#include <queue>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#define ri register

using namespace std;

const int maxn = 100000 + 10;

const int inf = 0x7fffffff;

int n, m, dis[maxn], vis[maxn];

queue<int> q;

struct edge{

	int from, to, next, len;

}e[maxn<<2];

int head[maxn], cnt;

void add(int u, int v, int w)

{

	e[++cnt].from = u;

	e[cnt].len = w;

	e[cnt].next = head[u];

	e[cnt].to = v;

	head[u] = cnt;

}

bool SPFA(int now)

{

    vis[now] = 1;

    for(int i = head[now]; i != -1; i = e[i].next)

    {

        if(dis[e[i].to] > dis[now] + e[i].len)

        {

            dis[e[i].to] = dis[now] + e[i].len;

            if(!vis[e[i].to])

			{

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

			}

            else return 0;

        }

    }

    vis[now] = 0;

    return 1;

}

int main()

{

	memset(head, -1, sizeof(head));

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

	for(ri int i = 1; i <= n; i++)

	{

		add(0, i, 0);dis[i] = inf;

	}

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

	{

		int u, v, w, opt;

		scanf("%d",&opt);

		if(opt == 1)

		{

			scanf("%d%d%d",&u,&v,&w);

			add(u, v, -w);

		}

		if(opt == 2)

		{

			scanf("%d%d%d",&u,&v,&w);

			add(v, u, w);

		}

		if(opt == 3)

		{

			scanf("%d%d",&u,&v);

			add(v, u, 0);

			add(u, v, 0);

		}

	}

	if(!SPFA(0))

	printf("No\n");

	else

	printf("Yes\n");

	return 0;

}

巴特西

【luogu P1993 小K的农场】题解

最新文章

热门文章

巴特西

【luogu P1993 小K的农场】 题解

最新文章

热门文章

【luogu P1993 小K的农场】题解