P1993 小 K 的农场

涛帝發表於 2026-3-28 12:57:00

<h1 id="p1993-小-k-的农场">P1993 小 K 的农场</h1>
<h2 id="题意">题意</h2>
第一行两个整数 $n$ 和 $m$ ，分别表示农场数目和小K记忆中的信息数目。
每行先输入一个数 $opt$ ，可为1,2,3。
每个数字代表一种条件，共3类条件：
$opt = 1$ ：农场 a 比农场 b 至少多种植了 c 个单位的作物；
$opt = 2$ ：农场 a 比农场 b 至多多种植了 c 个单位的作物；
$opt = 3$ ：农场 a 种植的的数量和 b 一样多。
问是否存在满足这些条件的数列，若满足输出 $Yes$ ，否则输出 $No$ 。
<h2 id="思路">思路</h2>
先看条件，发现我们似乎可以用式子把它表示出来：
注：$x_{i}$ 表示农场 $i$ 种植的作物数量
$opt = 1$ ：农场 a 比农场 b 至少多种植了 c 个单位的作物；
式子1表示：$x_{a} - x_{b} \ge c $
$opt = 2$ ：农场 a 比农场 b 至多多种植了 c 个单位的作物；
式子2表示：$x_{a} - x_{b} \le c $
$opt = 3$ ：农场 a 种植的的数量和 b 一样多。
式子3表示：$x_{a} - x_{b} = 0 $
发现这题就是差分约束，尝试转换一下
式子1转换：
$x_{a} - x_{b} \ge c $ —— > $x_{b} - x_{a} \le -c $
式子2转换：
$x_{a} - x_{b} \le c $（无需转换）
式子3转换：
$x_{a} - x_{b} = 0 $ 且 $x_{b} - x_{a} = 0 $
然后就可以发现这似乎可以建边了：
式子1： $x_{a}$ —> $x_{b}$ 边权为 $-c$
式子2： $x_{b}$ —> $x_{a}$ 边权为 $c$
式子3： $x_{b}$ —> $x_{a}$ 边权为 0且$x_{a}$ —> $x_{b}$ 边权为 0
建边操作做完后开始考虑：什么样的情况才会不满足上面的条件？
<img src="https://images.cnblogs.com/cnblogs_com/blogs/861950/galleries/2498535/o_260328002712_TJ.png" alt="TJ" loading="lazy">
若像这样，肯定是满足所有条件的。
若是负环那还满不满足呢？差分约束有解的条件之一就是无负环，负环会导致约束矛盾，使点之间的距离无限缩小。所以这题就成了一个判负环的简单题。需要注意的是，图可能不连通，所以还需要一个超级源点联通所有点，让每个图都可判段到。
注意 ：因为有超级源点，所以判负环应该多一个点。
<h2 id="代码">代码</h2>
<h3 id="有注释版">有注释版</h3>
<pre><code class="language-cpp">#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5 + 5;

// n:农场数量m:记忆信息数量
// dis[]:存储最短路径（差分约束中代表农场作物数量的解）
// cnt[]:记录每个节点入队次数，用于判断负环
// vis[]:标记节点是否在SPFA队列中，防止重复入队
int n, m, dis, cnt;
bool vis;
// 邻接表存图：e存储所有从u出发的边，pair<终点v, 边权w>
vector<pair<int, int>> e;

// 加边函数：添加一条 u → v 的有向边，边权为 w
void add(int u, int v, int w) {
e.push_back({v, w});
}

// SPFA算法：判断从起点s出发的图中是否存在**负环**
// 返回值：true=存在负环(无解)false=无负环(有解)
bool spfa(int s) {
// 初始化：vis全为false（未入队）
// dis初始化为无穷大（0x3f是int类型的极大值）
// cnt初始化为0（入队次数清零）
memset(vis, 0, sizeof(vis));
memset(dis, 0x3f, sizeof(dis));
memset(cnt, 0, sizeof(cnt));

// 队列：SPFA的核心数据结构，存储待松弛的节点
queue<int> q;
// 起点入队
q.push(s);
// 起点到自身的距离为0
dis = 0;

// 队列不为空，循环松弛
while (!q.empty()) {
// 取出队首节点u
int u = q.front();
q.pop();
// 标记u不在队列中
vis = 0;

// 遍历u的所有邻边（u→v，边权w）
for (auto : e) {
// 松弛操作：如果能通过u到达v，让路径更短
if (dis + w < dis) {
// 更新v的最短路径
dis = dis + w;
// v的入队次数 = u的入队次数 + 1
cnt = cnt + 1;

// 关键：如果一个节点入队次数 > 总节点数n
// 说明图中存在**负环**，差分约束无解
if (cnt > n)
return 1;

// 如果v不在队列中，入队并标记
if (!vis) {
q.push(v);
vis = 1;
}
}
}
}
// 遍历完所有节点，无负环，返回false
return 0;
}

int main() {
// 加速cin/cout（大数据输入必备）
ios::sync_with_stdio(false);
cin.tie(nullptr);

// 输入农场数n和信息数m
cin >> n >> m;

// 处理m条记忆信息
for (int i = 1; i <= m; i++) {
int op;// op=1/2/3 代表三种信息类型
cin >> op;

if (op == 1) {
// 类型1：a比b至少多种c → 数学式：a - b ≥ c
// 转化为差分约束标准式：b ≤ a - c
// 对应建边：a → b，边权 -c
int a, b, c;
cin >> a >> b >> c;
add(a, b, -c);
} else if (op == 2) {
// 类型2：a比b至多多种c → 数学式：a - b ≤ c
// 转化为差分约束标准式：a ≤ b + c
// 对应建边：b → a，边权 c
int a, b, c;
cin >> a >> b >> c;
add(b, a, c);
} else {
// 类型3：a和b数量相等 → 数学式：a = b
// 等价于：a ≤ b 且 b ≤ a
// 对应建双向边：a→b(0)b→a(0)
int a, b;
cin >> a >> b;
add(a, b, 0);
add(b, a, 0);
}
}

// 建【超级源点0】：向所有农场(1~n)连一条权值为0的边
// 作用：保证图连通，避免多个连通分量导致SPFA漏判负环
for (int i = 1; i <= n; i++) {
add(0, i, 0);
}

// 从超级源点0跑SPFA
// 无负环(spfa(0)=false) → 有解 → 输出Yes
// 有负环(spfa(0)=true) → 无解 → 输出No
if (!spfa(0))
cout << "Yes\n";
else
cout << "No\n";

return 0;
}
</code></pre>
<h3 id="无注释版">无注释版</h3>
<pre><code class="language-cpp">#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e5+5;
int n,m,dis,cnt;
bool vis;
vector<pair<int,int> >e;
void add(int u,int v,int w){e.push_back({v,w});}
bool spfa(int s)
{
memset(vis,0,sizeof vis); memset(dis,0x3f,sizeof dis); memset(cnt,0,sizeof cnt);
queue<int>q;
q.push(s);
dis=0;
while (!q.empty())
{
int u=q.front(); q.pop();
vis=0;
for (auto : e)
{
if (dis+w<dis)
{
dis=dis+w,cnt=cnt+1;
if (cnt>n) return 1;
if (!vis) {q.push(v); vis=1;}
}
}
}
return 0;
}
int main()
{

cin >>n>>m;
for (int i=1;i<=m;i++)
{
int x; cin >>x;
if (x==1)
{
int u,v,w; cin >>u>>v>>w;
add(u,v,-w);
}
else if(x==2)
{
int u,v,w; cin >>u>>v>>w;
add(v,u,w);
}
else
{
int u,v,w=0; cin >>u>>v;
add(u,v,w); add(v,u,w);
}
}
for (int i=1;i<=n;i++){add(0,i,0);}
if (!spfa(0)) cout <<"Yes"<<endl;
else cout <<"No"<<endl;
return 0;
}
</code></pre> 
来源：https://www.cnblogs.com/CJRcn/p/19785468

頁: [1]

琼殿技术论坛's Archiver

P1993 小 K 的农场