\u5224\u65ad\u6d41\u7f51\u7edc\u5272\u662f\u5426\u552f\u4e00\u3002
\n<\/p>\n
\u6700\u5927\u6d41\u5b8c\u4e8b\u4ee5\u540e\uff0c\u4ece\u6e90\u70b9\u548c\u6c47\u70b9\u5904\u5206\u522b\u67d3\u8272\u3002<\/p>\n
\r\n\/*\r\n Author: xiaodao \r\n Prob: ZOJ 2587. Unique Attack \r\n Date: GMT +8 Aug.19th 02:36\r\n Status: Accepted \r\n Tags: Network-Flow\r\n*\/\r\n\r\n#include \r\n#include \r\n#include \r\nusing namespace std;\r\nconst int INF = 0x7fffffff, BLACK = 0, RED = 1, BLUE = 2;\r\nconst int N = 1001;\r\nint C[N][N], D[N];\r\nint n, m, s, t;\r\n\r\nvoid bfs(){\r\n int Q[N], head, tail;\r\n memset(D, -1, sizeof(D));\r\n head = 0; tail = 1; Q[0] = s; D[s] = 0;\r\n\r\n int u, v;\r\n while (headn) D[u] = -1, top--;\r\n else {\r\n cur[u] = v + 1;\r\n stack[++top] = v;\r\n }\r\n }\r\n bfs();\r\n }\r\n}\r\n\r\n\r\n\r\nvoid init(){\r\n memset(C, 0, sizeof(C));\r\n int x, y, c;\r\n for (int i=1;i<=m;i++){\r\n scanf(\"%d%d%d\", &x, &y, &c);\r\n C[x][y] += c; C[y][x] += c;\r\n }\r\n}\r\n\r\nbool unique(){\r\n int queue[N]; int color[N];\r\n int head, tail, u, v;\r\n memset(color, BLACK, sizeof(color));\r\n head = 0; tail = 1; queue[0] = s; color[s] = RED;\r\n\r\n\r\n while (head0){\r\n queue[tail++] = v;\r\n color[v] = RED;\r\n }\r\n }\r\n head++;\r\n }\r\n\r\n head = 0; tail = 1; queue[0] = t; color[t] = BLUE;\r\n while (head=1;u--){\r\n if (color[u]!=BLUE && C[u][v]>0){\r\n if (color[u] == RED) return false;\r\n queue[tail++] = u;\r\n color[u] = BLUE;\r\n }\r\n }\r\n head++;\r\n }\r\n\r\n for (int i=1;i<=n;i++)\r\n if (color[i] == BLACK) return false;\r\n return true;\r\n}\r\n\r\n\r\n\r\nint main(){\r\n while (scanf(\"%d%d%d%d\", &n, &m, &s, &t) != EOF && n > 0){\r\n init(); Dinitz();\r\n puts(unique() ? \"UNIQUE\" : \"AMBIGUOUS\");\r\n }\r\n}\r\n<\/pre>\n<\/bk><\/p>\n
Further discuss :<\/h3>\n
\u597d\u4e86\u6211\u6765\u8bf4\u70b9\u6b63\u4e8b\u3002\u3002\u3002\u6211\u8fd9\u51e0\u5929\u7206\u5199\u4e86\u5341\u51e0\u4e2a\uff08\u51e0\u4e2a\u5566\uff09\u5404\u79cd\u7f51\u7edc\u6d41\u7684\u9898\u3002
\n\u3002\u3002\u3002\u6bd4\u5982\u8bf4\u50cf\u662f\u8fd9\u4e2a\u3002\u3002\u6628\u665a\u5c31\u5199\u5b8c\u4e86\u3002\u3002\u7136\u540e\u4e00\u76f4WA\u4e00\u76f4WA\u3002\u3002\u5fc3\u60f3\u3002\u3002\u96be\u4e0d\u6210\u6211\u7684 Relabel \u6709BUG\uff1f#\u3002 \uff08\u4e8e\u662f\u51e0\u4e2a\u6df1\u591c\u53c8\u5b66\u4e60\u4e86 Dinitz … Sap … \u76ee\u524d\u6309\u7167\u8ba1\u5212\u53ea\u5dee\u4e00\u4e2a HLPP \u4e86\u3002\u3002\uff09<\/p>\n
\u4f46\u662f\u6211\u7ee7\u7eed\u7206WA..<\/p>\n
\u4e8e\u662f\u6211\u53d1\u73b0\u6211WA\u7684\u51e0\u4e2a\u7f51\u7edc\u6d41\u90fd\u6709\u4e00\u4e9b\u5171\u540c\u70b9\u3002\u3002\u3002
\n\uff08\u5feb\u8bf4\u554a\u3002\u3002\u3002#\uff09<\/p>\n
\u4e8b\u5b9e\u4e0a\u3002\u3002\u56e0\u4e3a\u6211\u4eba\u5de5\u5c06\u6e90\u70b9\u548c\u6c47\u70b9\u56fa\u5b9a\u6210 1 && n \u4f1a\u6709\u8bb8\u591a\u8bf4\u4e0d\u6e05\u7684\u597d\u5904\u3002\u3002\u3002\uff08\u4f8b\u5982\u3002\u3002\u6211\u603b\u662f\u53ef\u4ee5\u4f18\u5316\u3002\u3002#\u3002#\uff09<\/p>\n
\r\n...\r\n if (s!=1){\r\n for (int i=1;i<=n;i++){\r\n if (i==1||i==s) continue;\r\n swap(C[1][i], C[s][i]);\r\n swap(C[i][1], C[i][s]);\r\n }\r\n swap(C[1][s], C[s][1]);\r\n }\r\n\r\n if (t!=n){\r\n for (int i=1;i<=n;i++){\r\n if (i==n||i==t) continue;\r\n swap(C[n][i], C[t][i]);\r\n swap(C[i][n], C[i][t]);\r\n }\r\n swap(C[n][t], C[t][n]);\r\n }\r\n s = 1; t = n;\r\n ....\r\n<\/pre>\n\u5b9e\u9645\u4e0a\u3002\u3002\u6211\u4e4b\u524d\u7684\u65b9\u6848\u66f4\u66b4\u529b\u3002\u3002\u5c31\u662f\u4e00\u4e2a\u5faa\u73af\u91cc\u9762\u5d4c\u4e24\u4e2a\u4ea4\u6362\u3002\u3002
\n\uff08\u4f46\u662f\u6211\u5df2\u7ecf\u53d1\u73b0\u90a3\u6837\u662f\u9519\u8bef\u7684\u4e86\u3002\u3002\u3002\u4f46\u662f\u6211\u4e0d\u80fd\u53d1\u73b0\u3002\u3002\u8fd9\u4e2a\u9519\u5728\u54ea\u3002\uff09<\/p>\n","protected":false},"excerpt":{"rendered":"
Brief description : \u5224\u65ad\u6d41\u7f51\u7edc\u5272\u662f\u5426\u552f\u4e00\u3002<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false}}},"categories":[1],"tags":[],"class_list":["post-119","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-1V","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/119","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/comments?post=119"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/119\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=119"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=119"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=119"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}