{"id":379,"date":"2023-03-16T10:18:24","date_gmt":"2023-03-16T02:18:24","guid":{"rendered":"https:\/\/www.xgnd.net\/?p=379"},"modified":"2023-03-16T10:18:24","modified_gmt":"2023-03-16T02:18:24","slug":"cf1687b-railway-system-%e9%a2%98%e8%a7%a3","status":"publish","type":"post","link":"https:\/\/www.xgnd.net\/index.php\/2023\/03\/16\/cf1687b-railway-system-%e9%a2%98%e8%a7%a3\/","title":{"rendered":"CF1687B Railway System \u9898\u89e3"},"content":{"rendered":"

\u849f\u84bb\u7684\u7b2c\u4e00\u9053\u4ea4\u4e92\u9898\uff0c\u7b2c\u4e8c\u7bc7\u9898\u89e3\uff0c\u53ef\u80fd\u5199\u7684\u4e0d\u597d\uff0c\u8f7b\u55b7\u3002<\/p>\n

\u9898\u76ee\u4f20\u9001\u95e8<\/a><\/p>\n

\u9898\u610f\u7b80\u8ff0<\/h2>\n

\u4ea4\u4e92\u9898\uff0c\u4e00\u4e2a $n$ \u4e2a\u70b9 $m$ \u6761\u8fb9\u7684\u65e0\u5411\u5e26\u6743\u56fe\u3002\u521d\u59cb\u7ed9\u5b9a $n$\uff0c$m$\uff0c\u6bcf\u6b21\u53ef\u4ee5\u8be2\u95ee\u4e00\u4e2a\u8fb9\u96c6\uff0c\u8fd4\u56de\u7531\u8fd9\u4e9b\u8fb9\u7ec4\u6210\u7684\u6700\u5927\u751f\u6210\u68ee\u6797\u7684\u8fb9\u6743\u548c\u3002\u8981\u6c42\u5728 $2m$ \u6b21\u8be2\u95ee\u5185\u6c42\u51fa\u6700\u5c0f\u751f\u6210\u68ee\u6797\u7684\u6743\u503c\u548c\u3002<\/p>\n

\uff08$2 \\leq n \\leq 200$\uff0c$1 \\leq m \\leq 500$\uff09<\/p>\n

\u9898\u76ee\u5206\u6790<\/h2>\n

\u4e00\u4e2a\u663e\u7136\u7684\u60f3\u6cd5\uff0c\u524d $m$ \u6b21\u8be2\u95ee\u6bcf\u6b21\u53ea\u8be2\u95ee\u4e00\u6761\u8fb9\uff0c\u77e5\u9053\u6bcf\u6761\u8fb9\u7684\u8fb9\u6743\uff0c\u4f46\u8fd8\u4e0d\u77e5\u9053\u56fe\u7684\u5f62\u6001\u3002<\/p>\n

\u8003\u8651\u4e00\u4e0b Kruskal \u7684\u8fc7\u7a0b\uff1a<\/p>\n

    \n
  • \n

    \u6309\u8fb9\u6743\u4ece\u5c0f\u5230\u5927\u6392\u5e8f<\/p>\n<\/li>\n

  • \n

    \u4f9d\u6b21\u5c1d\u8bd5\u52a0\u8fb9\uff0c\u5e76\u67e5\u96c6\u5224\u65ad\u662f\u5426\u4f1a\u6210\u73af<\/p>\n<\/li>\n<\/ul>\n

    \u6211\u4eec\u53ef\u4ee5\u53d1\u73b0\uff0c\u95ee\u9898\u5c31\u5728\u80fd\u5426\u5224\u65ad\u73af\uff0c\u4e8e\u662f\u53ef\u4ee5\u8003\u8651\u80fd\u4e0d\u80fd\u901a\u8fc7\u8be2\u95ee\u4ee3\u66ff\u5e76\u67e5\u96c6\u7684\u8fc7\u7a0b\u3002<\/p>\n

    \u8003\u8651\u5c06\u65b0\u52a0\u7684\u8fb9\u4e0e\u539f\u6765\u5df2\u77e5\u7684\u6700\u5c0f\u751f\u6210\u6811\uff08\u6216\u68ee\u6797\uff09\u7684\u8fb9\u96c6\u8fdb\u884c\u4e00\u6b21\u8be2\u95ee\uff0c\u5176\u6700\u5927\u751f\u6210\u6811\uff08\u6216\u68ee\u6797\uff09\u53ef\u80fd\u53d1\u751f\u4e86\u4ee5\u4e0b\u51e0\u79cd\u60c5\u51b5\uff1a<\/p>\n

      \n
    • \u65b0\u52a0\u7684\u8fb9\u4e0e\u539f\u6700\u5927\u751f\u6210\u6811\uff08\u6216\u68ee\u6797\uff09\u6784\u6210\u4e86\u73af\uff0c\u4e3a\u4e86\u4fdd\u6301\u8fde\u901a\u6027\uff0c\u4ece\u73af\u4e0a\u8e22\u6389\u4e86\u4e00\u6761\u8fb9\u6743\u66f4\u5c0f\u7684\u8fb9\uff0c\u8fb9\u6743\u548c\u53d8\u5316\u91cf\u5c0f\u4e8e\u65b0\u52a0\u8fb9\u7684\u8fb9\u6743<\/strong>\u3002<\/li>\n
    • \u65b0\u52a0\u7684\u8fb9\u76f4\u63a5\u52a0\u5165\u539f\u6700\u5927\u751f\u6210\u6811\uff08\u6216\u68ee\u6797\uff09\uff0c\u8fb9\u6743\u548c\u53d8\u5316\u91cf\u7b49\u4e8e\u65b0\u52a0\u8fb9\u7684\u8fb9\u6743<\/strong>\u3002<\/li>\n<\/ul>\n

      \u663e\u7136\uff0c\u7b2c\u4e00\u79cd\u60c5\u51b5\u7684\u8fb9\u662f\u4e0d\u80fd\u9009\u7684\uff0c\u56e0\u4e3a\u65b0\u52a0\u8fd9\u6761\u8fb9\u4f1a\u4f7f\u5f97\u6700\u5c0f\u751f\u6210\u6811\uff08\u6216\u68ee\u6797\uff09\u6709\u73af\u3002\u53ea\u6709\u7b2c\u4e8c\u79cd\u60c5\u51b5\u6ee1\u8db3\u3002<\/p>\n

      \u540c\u65f6\u4e0d\u96be\u53d1\u73b0\uff0c\u6bcf\u6b21\u8be2\u95ee\u540e\u6700\u5927\u751f\u6210\u6811\uff08\u6216\u68ee\u6797\uff09\u7684\u5f62\u6001\u4e0e\u6700\u5c0f\u751f\u6210\u6811\uff08\u6216\u68ee\u6797\uff09\u7684\u5f62\u6001\uff08\u8fb9\u548c\u70b9\uff09\u90fd\u662f\u4e00\u81f4\u7684\u3002\u8fd9\u4e5f\u662f\u80fd\u8fd9\u4e48\u505a\u7684\u4e00\u4e2a\u4f9d\u636e\u3002<\/p>\n

      \u7efc\u4e0a\uff0c\u524d $m$ \u6b21\u8be2\u95ee\u5f97\u5230\u6bcf\u6761\u8fb9\u8fb9\u6743\u3002\u540e $m-1$ \u6b21\u8be2\u95ee\uff0c\u6bcf\u6b21\u6211\u4eec\u7528\u65b0\u52a0\u7684\u8fb9\u4e0e\u539f\u6765\u5df2\u77e5\u7684\u6700\u5c0f\u751f\u6210\u6811\uff08\u6216\u68ee\u6797\uff09\u7684\u8fb9\u96c6\u8fdb\u884c\u4e00\u6b21\u8be2\u95ee\uff0c\u82e5\u8fb9\u6743\u548c\u53d8\u5316\u91cf\u5c0f\u4e8e\u65b0\u52a0\u8fb9\u7684\u8fb9\u6743\uff0c\u5219\u8fd9\u6761\u8fb9\u4e0d\u53ef\u9009\uff1b\u82e5\u8fb9\u6743\u548c\u53d8\u5316\u91cf\u7b49\u4e8e\u65b0\u52a0\u8fb9\u7684\u8fb9\u6743\uff0c\u5219\u9009\u3002\u8fd9\u6837\u5c31\u80fd\u5728 $2m$ \u6b21\u8be2\u95ee\u5185\u5f97\u51fa\u7b54\u6848\u3002<\/p>\n

      Code<\/h2>\n
      #include<bits\/stdc++.h>\nusing namespace std;\ntypedef long long ll;\nconst int maxn=505;\nint n,m;\nbool bj[maxn];  \/\/\u8bb0\u5f55\u5df2\u77e5\u6700\u5c0f\u751f\u6210\u6811\uff08\u6216\u68ee\u6797\uff09\u7684\u8fb9\n\nstruct edge{\n    int p,v;\n}c[maxn];\n\nbool cmp(edge x,edge y){\n    return x.v<y.v;\n}\n\nint main(){\n    ios::sync_with_stdio(0);\n    cin>>n>>m;\n    for(int i=1;i<=m;i++){\n        cout<<"? ";\n        for(int j=1;j<=m;j++){\n            if(j!=i)cout<<bj[i];\n            else cout<<1;\n        }\n        cout<<endl;\n        fflush(stdout);\n        c[i].p=i;\n        cin>>c[i].v;\n    }\n\n    sort(c+1,c+1+m,cmp);\n\n    int cnt=0;\n    ll ans=0;\n    int x=c[1].v,y;\n    bj[c[1].p]=1;\n    ans+=c[1].v;\n\n    for(int i=2;i<=m;i++){\n        cout<<"? ";\n        bj[c[i].p]=1;\n        for(int j=1;j<=m;j++){\n            cout<<bj[j];\n        }\n        cout<<endl;\n        fflush(stdout);\n\n        cin>>y;\n        int d=y-x;\n        if(d<c[i].v){   \/\/\u82e5\u8fb9\u6743\u548c\u53d8\u5316\u91cf\u5c0f\u4e8e\u65b0\u52a0\u8fb9\u7684\u8fb9\u6743\uff0c\u4e0d\u9009\n            bj[c[i].p]=0;\n        }\n        else{\n            ans+=c[i].v;\n            x=y;\n            if(++cnt==n-1)break;\n        }\n    }\n    cout<<"! "<<ans;\n\n    return 0;\n}\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
      \u849f\u84bb\u7684\u7b2c\u4e00\u9053\u4ea4\u4e92\u9898\uff0c\u7b2c\u4e8c\u7bc7\u9898\u89e3\uff0c\u53ef\u80fd\u5199\u7684\u4e0d\u597d\uff0c\u8f7b\u55b7\u3002 \u9898\u76ee\u4f20\u9001\u95e8 \u9898\u610f\u7b80\u8ff0 \u4ea4\u4e92\u9898\uff0c\u4e00\u4e2a $n$ \u4e2a\u70b9 $m$ […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[2,3,10],"tags":[],"class_list":["post-379","post","type-post","status-publish","format-standard","hentry","category-c","category-oi","category-10"],"_links":{"self":[{"href":"https:\/\/www.xgnd.net\/index.php\/wp-json\/wp\/v2\/posts\/379","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.xgnd.net\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.xgnd.net\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.xgnd.net\/index.php\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.xgnd.net\/index.php\/wp-json\/wp\/v2\/comments?post=379"}],"version-history":[{"count":0,"href":"https:\/\/www.xgnd.net\/index.php\/wp-json\/wp\/v2\/posts\/379\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.xgnd.net\/index.php\/wp-json\/wp\/v2\/media?parent=379"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.xgnd.net\/index.php\/wp-json\/wp\/v2\/categories?post=379"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.xgnd.net\/index.php\/wp-json\/wp\/v2\/tags?post=379"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}