首页 > 代码库 > BZOJ3436 小K的农场
BZOJ3436 小K的农场
首先这是个查分约束系统。。。(那是啥来着←_←)
然后判断可行解的话,直接spfa判负圈。
bfs版spfa要记录每个点的进队次数,如果大于点数就代表有负圈。。。但是好慢Σ( ° △ °|||)︴
于是改用dfs版的spfa(还以为会很慢。。。,其实速度极快Orz)
1 /************************************************************** 2 Problem: 3436 3 User: rausen 4 Language: C++ 5 Result: Accepted 6 Time:36 ms 7 Memory:1236 kb 8 ****************************************************************/ 9 10 #include <cstdio>11 12 using namespace std;13 const int N = 10005;14 const int M = N;15 const int Maxlen = 20 * M;16 17 struct edges {18 int next, to, v;19 edges() {}20 edges(int _n, int _t, int _v) : next(_n), to(_t), v(_v) {}21 } e[M];22 23 int n, m;24 int first[N], tot;25 int d[N];26 int v[N], flag;27 char buf[Maxlen], *c = buf;28 int Len;29 30 inline int read() {31 int x = 0;32 while (*c < ‘0‘ || ‘9‘ < *c) ++c;33 while (‘0‘ <= *c && *c <= ‘9‘)34 x = x * 10 + *c - ‘0‘, ++c;35 return x;36 }37 38 inline void add_edge(int x, int y, int z) {39 e[++tot] = edges(first[x], y, z);40 first[x] = tot;41 }42 43 void spfa(int p) {44 if (v[p]) {45 flag = 1;46 return;47 }48 int x, y;49 v[p] = 1;50 for (x = first[p]; x; x = e[x].next)51 if (d[p] + e[x].v < d[y = e[x].to]) {52 d[y] = d[p] + e[x].v;53 spfa(y);54 if (flag) return;55 }56 v[p] = 0;57 }58 59 int main() {60 Len = fread(c, 1, Maxlen, stdin);61 buf[Len] = ‘\0‘;62 int i, oper, x, y, z;63 n = read(), m = read();64 for (i = 1; i <= m; ++i) {65 oper = read(), x = read(), y = read();66 if (oper == 3) add_edge(x, y, 0);67 else {68 z = read();69 if (oper == 1) add_edge(x, y, -z);70 else add_edge(y, x, z);71 }72 }73 for (i = 1; i <= n; ++i) {74 spfa(i);75 if (flag) break;76 }77 puts(flag ? "No" : "Yes");78 return 0;79 }
BZOJ3436 小K的农场
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。