P1993 小K的农场 （差分约束-最短/长路模型）

题目描述

小 K 在 MC 里面建立很多很多的农场，总共 n 个，以至于他自己都忘记了每个农场中种植作物的具体数量了，他只记得一些含糊的信息（共 m 个），以下列三种形式描述：

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

但是，由于小 K 的记忆有些偏差，所以他想要知道存不存在一种情况，使得农场的种植作物数量与他记忆中的所有信息吻合。

输入格式

第一行包括两个整数 n 和 m，分别表示农场数目和小 K 记忆中的信息数目。

接下来 mm 行：

• 如果每行的第一个数是 1，接下来有三个整数 a,b,c，表示农场 a 比农场 b 至少多种植了 c 个单位的作物；
• 如果每行的第一个数是 2，接下来有三个整数 a,b,c，表示农场 a 比农场 b 至多多种植了 c 个单位的作物;
• 如果每行的第一个数是 3，接下来有两个整数 a,b，表示农场 a 种植的的数量和 b 一样多。

输出格式

如果存在某种情况与小 K 的记忆吻合，输出 Yes，否则输出 No。

输入输出样例

输入 #1复制

3 3
3 1 2
1 1 3 1
2 2 3 2

输出 #1复制

Yes

说明/提示

数据规模与约定

对于 100% 的数据，保证 1 ≤n,m,a,b,c≤10000。

题意：中文题，不过多叙述题意。

思路1：这道题的话，是我做的第一道差分约束的题目。

题里给你三个显而易见的约束条件。

a-b>=c   1
a-b<=c   2
a==b     3

 如果我们要用最长路的做法的话：

1式：a-b>=c

2式：a-b<=c，即b-a>=-c

3式：a=b即a-b<=0且b-a<=0

然后我们设1式中的c为w{b,a}；设2式中的-c为w{a,b}；设3式中的c为w{a,b}=w{b,a}=0。然后从0向i=1→n每个点连边w{0,i}=0；最后跑spfa求最长路，出现环则输出No，否则输出Yes。

AC代码---最长路：

#include 
typedef long long ll;
const int maxx=50010;
const int inf=0x3f3f3f3f;
using namespace std;
struct node
{int v;int w;int next;
} edge[maxx];
int head[maxx],dis[maxx];
bool vis[maxx];
int cnt,n,m;
void add(int u,int v,int w)
{edge[cnt].v=v;edge[cnt].w=w;edge[cnt].next=head[u];head[u]=cnt++;
}
int spfa(int u)
{vis[u]=1;for(int i=head[u]; i!=-1; i=edge[i].next){int v=edge[i].v;int w=edge[i].w;if(dis[v]

a-b>=c   1
a-b<=c   2
a==b     3

#include 
typedef long long ll;
const int maxx=50010;
const int inf=0x3f3f3f3f;
using namespace std;
struct node
{int v;int w;int next;
} edge[maxx];
int head[maxx],dis[maxx];
bool vis[maxx];
int cnt,n,m;
void add(int u,int v,int w)
{edge[cnt].v=v;edge[cnt].w=w;edge[cnt].next=head[u];head[u]=cnt++;
}
int spfa(int u)
{vis[u]=1;for(int i=head[u]; i!=-1; i=edge[i].next){int v=edge[i].v;int w=edge[i].w;if(dis[v]>dis[u]+w){dis[v]=dis[u]+w;if(vis[v])return 0;if(!spfa(v))return 0;}}vis[u]=0;return 1;
}
int main()
{scanf("%d%d",&n,&m);memset(head,-1,sizeof(head));int falg,a,b,c;while(m--){scanf("%d%d%d",&falg,&a,&b);if(falg==1){scanf("%d",&c);add(a,b,-c);}else if(falg==2){scanf("%d",&c);add(b,a,c);}else if(falg==3){add(a,b,0);add(b,a,0);}}for(int i=1; i<=n; i++){add(0,i,0);dis[i]=inf;}if(!spfa(0))printf("No\n");elseprintf("Yes\n");return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！