{"id":415,"date":"2018-08-04T19:29:00","date_gmt":"2018-08-04T19:29:00","guid":{"rendered":"https:\/\/www.haoyuan.info\/?p=415"},"modified":"2018-08-04T19:29:00","modified_gmt":"2018-08-04T19:29:00","slug":"%e7%89%9b%e5%ae%a2%e5%a4%9a%e6%a0%a1%e7%ac%ac%e4%b8%80%e5%9c%ba-problem-d-two-graphs","status":"publish","type":"post","link":"https:\/\/haoyuan.info\/?p=415","title":{"rendered":"\u725b\u5ba2\u591a\u6821\u7b2c\u4e00\u573a Problem D Two Graphs"},"content":{"rendered":"

\u9898\u610f<\/h2>\n

n\u4e2a\u70b9\uff0cm1\u6761\u8fb9\u7684\u56feE1\uff0cn\u4e2a\u70b9\uff0cm2\u6761\u8fb9\u7684\u56feE2\u3002\u6c42\u56feE2\u6709\u591a\u5c11\u5b50\u56fe\u8ddf\u56feE1\u540c\u6784\u3002<\/p>\n

\u9898\u89e3<\/h2>\n

\u7531\u4e8e\u9898\u76ee\u6570\u636e\u8303\u56f4\u4e0d\u5927\u8003\u8651\u66b4\u529b\u679a\u4e3e$n!$\u8303\u56f4\u7684\u6240\u6709\u7ed3\u679c\u3002
\n\u7b54\u6848\u9664\u4ee5\u81ea\u540c\u6784\u6570\u3002<\/p>\n

AC\u4ee3\u7801<\/h2>\n
#include <iostream>\n#include <cstring>\n#include <algorithm>\n#include <numeric>\n\nusing namespace std;\nint n, m1, m2, u[100], v[100], g1[10][10], g2[10][10], a[10];\n\nint main() {\n    ios::sync_with_stdio(false);\n    cin.tie(0);\n    cout.tie(0);\n    while (cin >> n >> m1 >> m2) {\n        memset(g1, 0, sizeof(g1));\n        memset(g2, 0, sizeof(g2));\n        for (int i = 1; i <= m1; i++) {\n            cin >> u[i] >> v[i];\n            g1[u[i]][v[i]] = g1[v[i]][u[i]] = 1;\n        }\n        for (int i = 1; i <= m2; i++) {\n            int x, y;\n            cin >> x >> y;\n            g2[x][y] = g2[y][x] = 1;\n        }\n        iota(a + 1,a + 1 + n,1);\n        int ans = 0, num = 0;\n        do {\n            int flag1 = 1, flag2 = 1;\n            for (int i = 1; i <= m1; i++) {\n                int x = a[u[i]], y = a[v[i]];\n                if (!g1[x][y])flag1 = 0;\n                if (!g2[x][y])flag2 = 0;\n            }\n            ans += flag2;\n            num += flag1;\n        } while (next_permutation(a + 1, a + n + 1));\n        cout << ans \/ num << \"\\n\";\n    }\n}\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
\u9898\u610f n\u4e2a\u70b9\uff0cm1\u6761\u8fb9\u7684\u56feE1\uff0cn\u4e2a\u70b9\uff0cm2\u6761\u8fb9\u7684\u56feE2\u3002\u6c42\u56feE2\u6709\u591a\u5c11\u5b50\u56fe\u8ddf\u56feE1\u540c\u6784\u3002 \u9898\u89e3 \u7531\u4e8e\u9898\u76ee\u6570\u636e […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"spay_email":"","footnotes":"","jetpack_publicize_message":"","jetpack_is_tweetstorm":false},"categories":[39,49,22],"tags":[24,52],"class_list":["post-415","post","type-post","status-publish","format-standard","hentry","category-c","category-49","category-22","tag-cpp","tag-52"],"jetpack_featured_media_url":"","jetpack_publicize_connections":[],"jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/p8UC2c-6H","jetpack_likes_enabled":true,"jetpack-related-posts":[],"_links":{"self":[{"href":"https:\/\/haoyuan.info\/index.php?rest_route=\/wp\/v2\/posts\/415","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/haoyuan.info\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/haoyuan.info\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/haoyuan.info\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/haoyuan.info\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=415"}],"version-history":[{"count":0,"href":"https:\/\/haoyuan.info\/index.php?rest_route=\/wp\/v2\/posts\/415\/revisions"}],"wp:attachment":[{"href":"https:\/\/haoyuan.info\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=415"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/haoyuan.info\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=415"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/haoyuan.info\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=415"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}