P2705
暂无测试数据。
小K 在MC 里面建立很多很多的农场,总共n 个,以至于他自己都忘记了每个农场中种植作物的具体数量了,他只记得一些含糊的信息(共m 个),以下列三种形式描述:
农场a 比农场b 至少多种植了c 个单位的作物,
农场a 比农场b 至多多种植了c 个单位的作物,
农场a 与农场b 种植的作物数一样多。
但是,由于小K 的记忆有些偏差,所以他想要知道存不存在一种情况,使得农场的种植作物数量与他记忆中的所有信息吻合。
#include <bits/stdc++.h>
using namespace std;
struct edge{
int to, next, cost;
}e[2000005];
int dis[2000005], vis[2000005], el[2000005], len = 0;
int n, m, u, v, l, a, b;
#define gc z == d && (d = (z = buf) + fread(buf, 1, 2000005, stdin), z == d) ? EOF : *z++
static char buf[200000005], *z = buf, *d = buf;
inline int read()
{
register int x(0);register char ch(gc);
while (ch < '0' || ch > '9')ch = gc;
while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + (ch ^ 48), ch = gc;
return x;
}
int spfa(int x)
{
vis[x] = 1;
for (int i = el[x]; i; i = e[i].next)
{
int y = e[i].to;
if (dis[y] > dis[x] + e[i].cost)
{
dis[y] = dis[x] + e[i].cost;
if (vis[y]) return 0;
if (!spfa(y)) return 0;
}
}
vis[x] = 0;
return 1;
}
int main()
{
n = read(), m = read();
for (int i = 0; i < m; ++i)
{
u = read();
if (u == 1)
{
u = read(), v = read(), l = read();
e[++len].to = v; e[len].cost = -l; e[len].next = el[u]; el[u] = len;
}
else if (u == 2)
{
u = read(), v = read(), l = read();
e[++len].to = u; e[len].cost = l; e[len].next = el[v]; el[v] = len;
}
else
{
u = read(), v = read();
e[++len].to = v; e[len].cost = 0; e[len].next = el[u]; el[u] = len;
e[++len].to = u; e[len].cost = 0; e[len].next = el[v]; el[v] = len;
}
}
for (int i = 1; i <= n; ++i)
{
e[++len].to = i; e[len].cost = 0; e[len].next = el[0]; el[0] = len;
}
for (int i = 0; i <= n; ++i) dis[i] = 999999999;
dis[0] = 0;
vis[0] = 1;
if (spfa(0)) puts("Yes");
else puts("No");
}
信息
- ID
- 1006
- 难度
- 10
- 分类
- (无)
- 标签
- (无)
- 递交数
- 1
- 已通过
- 0
- 通过率
- 0%
- 上传者