/ PZOJ / 题库 /

P2705

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%
上传者