ปิดถนนกันซ้อม: ขอบเขตที่ดูเป็นของแถม คือกุญแจของทั้งข้อ

ก่อนหาทางลัด เริ่มจากวิธีที่ตรงกับนิยามของโจทย์ที่สุด ซึ่งก็คือสิ่งที่ตัวตรวจของเกมข้างบนทำ

• เลือกว่าจะเก็บถนนไม่ราดยางเส้นไหนไว้บ้าง ไล่ครบทุกแบบ
• ในแต่ละแบบ ไล่หาวงจรอย่างง่ายทุกวงในกราฟที่เหลือ
• ถ้าเจอวงยาวคู่แม้วงเดียว ทิ้งแบบนั้นไป
• แบบที่เหลือ เอาแบบที่น้ำหนักรวมของถนนที่เก็บไว้มากที่สุด คำตอบคือค่าปิดทั้งหมดลบน้ำหนักนั้น

ตั้งแต่ตรงนี้ไป น้ำหนักของถนนไม่ราดยางคือค่าปิดของมัน มองจากฝั่งที่เก็บไว้ เก็บถนนที่หนักไว้ได้มากเท่าไร ก็จ่ายค่าปิดน้อยลงเท่านั้น

บนตัวอย่างในโจทย์ วิธีนี้ลอง 16 แบบแล้วได้ 5 ตรงกับเฉลย แต่ที่ขอบเขตเต็มมันต้องลองสองยกกำลัง 4,001 แบบ ซึ่งไม่มีทางจบ

// ตัวตรวจสอบที่ไม่เชื่อทฤษฎีอะไรเลย ใช้ได้แค่กราฟจิ๋ว ๆ ตอนสุ่มเทียบก่อนส่ง
// ไล่ทุกวิธีเลือกว่าจะ "เก็บ" ถนนไม่ราดยางเส้นไหนไว้บ้าง แล้วไล่หาวงจรอย่างง่ายทุกวง
// ถ้าเจอวงยาวคู่แม้แต่วงเดียวก็ตัดทิ้ง ที่เหลือค่อยเอาน้ำหนักที่เก็บได้มากที่สุด
#include <bits/stdc++.h>
using namespace std;
int n;
vector<array<int,2>> E;                     // เส้นเชื่อมของกราฟที่กำลังตรวจ
vector<vector<pair<int,int>>> adj;          // (เพื่อนบ้าน, หมายเลขเส้น)
bool found;

void walk(int start, int cur, vector<char>& usedEdge, vector<char>& vis, int len) {
    for (auto& [w, ei] : adj[cur]) {
        if (usedEdge[ei]) continue;
        if (w == start) { if (len + 1 >= 2 && (len + 1) % 2 == 0) found = true; continue; }
        if (vis[w] || w < start) continue;   // บังคับให้ปมเล็กสุดของวงเป็นจุดเริ่ม กันนับซ้ำ
        vis[w] = 1; usedEdge[ei] = 1;
        walk(start, w, usedEdge, vis, len + 1);
        vis[w] = 0; usedEdge[ei] = 0;
        if (found) return;
    }
}
bool hasEvenCycle() {
    found = false;
    for (int s = 1; s <= n && !found; s++) {
        vector<char> usedEdge(E.size(), 0), vis(n + 1, 0);
        vis[s] = 1;
        walk(s, s, usedEdge, vis, 0);
    }
    return found;
}
int main() {
    int m; scanf("%d %d", &n, &m);
    vector<array<int,3>> tree, extra;
    long long total = 0;
    for (int i = 0; i < m; i++) {
        int a, b, c; scanf("%d %d %d", &a, &b, &c);
        if (c == 0) tree.push_back({a, b, c});
        else { extra.push_back({a, b, c}); total += c; }
    }
    long long best = 0;
    for (int mask = 0; mask < (1 << (int)extra.size()); mask++) {
        E.clear();
        for (auto& e : tree) E.push_back({e[0], e[1]});
        long long w = 0;
        for (size_t j = 0; j < extra.size(); j++)
            if (mask >> j & 1) { E.push_back({extra[j][0], extra[j][1]}); w += extra[j][2]; }
        adj.assign(n + 1, {});
        for (size_t i = 0; i < E.size(); i++) {
            adj[E[i][0]].push_back({E[i][1], (int)i});
            adj[E[i][1]].push_back({E[i][0], (int)i});
        }
        if (!hasEvenCycle()) best = max(best, w);
    }
    printf("%lld\n", total - best);
}

ต้องหาทางตัดสินถนนทีละเส้นแทนการไล่เซต ไล่จากช้าไปเร็วมีสามวิธี วิธีที่ 1 คือตอนนี้ วิธีที่ 2 ใช้สองกฎจากตอนที่ 2 ถึง 4 และวิธีเต็มคือดีพีในตอนที่ 5 กับโค้ดในตอนที่ 6

ดูถนนไม่ราดยางทีละเส้นก่อน ถ้าเส้นทางบนต้นไม้ของมันยาว len สาย วงของมันยาว len + 1

ส่วนเส้นที่ len เป็นเลขคู่ วงของมันยาวคี่ ถ้าอยู่คนเดียวก็ไม่ผิดกฎ ชุดที่ 3 ของเกมคือกรณีนี้

กฎที่ 1 ยังไม่พอ ถนนสองเส้นที่วงยาวคี่ทั้งคู่ อยู่คนเดียวได้ แต่เปิดพร้อมกันอาจเกิดวงคู่ (เกมชุดที่ 4 คือกรณีนี้)

ตัวอย่างในโจทย์ก็มีคู่แบบนั้น คือถนน 1-3 กับ 2-4 เส้นทางบนต้นไม้ของทั้งสองใช้ถนนราดยาง 2-3 ร่วมกัน

ส่วนที่ทับถูกลบสองครั้ง (ครั้งละวง) จึงหักออกเป็นเลขคู่เสมอ คี่บวกคี่ได้คู่ หักคู่ออกก็ยังคู่ วงใหม่จึงยาวคู่ทุกครั้ง ไม่ว่าจะทับกันกี่สาย

บนต้นไม้ สองเส้นทางพบกันเป็นช่วงเดียวต่อกันเสมอ (ต้นไม้ไม่มีทางแยกแล้วมาบรรจบกันใหม่) ส่วนที่ไม่ทับของสองเส้นทางจึงไม่มีเมืองร่วมกันเลยนอกจากปลายช่วงนั้น ตัดช่วงที่ทับออกแล้วได้วงเดียวที่ไม่ผ่านเมืองซ้ำ

แตะกันแค่เมืองเดียวไม่นับว่าทับ เช่น 1-3 กับ 3-5 พบกันที่เมือง 3 อย่างเดียว วงสองวงนี้ต่อกันได้แค่แบบเดินผ่านเมือง 3 สองรอบ ซึ่งไม่นับเป็นเส้นทางซ้อม

โจทย์บอกแค่ว่าปลายสองข้างของถนนเป็นคนละเมือง ไม่ได้ห้ามถนนสองเส้นเชื่อมคู่เมืองเดียวกัน สองกฎยังใช้ได้ครบ ถนนที่ขนานกับถนนราดยางมีเส้นทางยาว 1 จึงถูกปิดตามกฎที่ 1 ส่วนถนนไม่ราดยางสองเส้นที่ขนานกันมีเส้นทางเดียวกัน จึงทับกันตามกฎที่ 2 (สองเส้นนี้เองก็เป็นวงยาว 2)

ถึงตรงนี้ ปัญหาเหลือแค่นี้: เลือกถนนจากเส้นที่ผ่านกฎที่ 1 โดยเส้นทางไม่ทับกัน ให้น้ำหนักรวมมากที่สุด แล้วคำตอบคือค่าปิดทั้งหมดลบน้ำหนักที่เก็บได้

ส่วนเหตุผลแบบไม่ต้องสุ่ม มองวงเป็นเซตของถนน แล้วไปทีละขั้น

สองกฎกับทิศกลับรวมกันคือวิธีที่ 2 ของบันได ไม่ต้องหาวงอีกแล้ว แต่ถ้าเลือกชุดที่ไม่ทับกันโดยไล่ทุกเซต ก็ยังช้าเกินไป

ตอนที่ 3 เหลือโจทย์ข้อเดียว คือเลือกถนนที่เส้นทางไม่ทับกันให้น้ำหนักมากสุด ไล่เซตไม่ได้ (ตอนที่ 1) ต้องตัดสินทีละเมือง

เริ่มจากปักรากต้นไม้ไว้ที่เมือง 1 แล้วแขวนเมืองอื่นลงมาเป็นชั้น ๆ คำที่ใช้ตลอดตอนนี้มีสี่คำ

• พ่อ ของเมืองหนึ่ง คือเมืองที่อยู่ติดกันและอยู่ชั้นบนกว่า (รากไม่มีพ่อ)
• ลูก คือเมืองที่อยู่ติดกันและอยู่ชั้นล่างกว่า หนึ่งเมืองมีลูกได้หลายคน
• ใบ คือเมืองที่ไม่มีลูก
• ต้นไม้ย่อย (subtree) ของเมือง v คือ v กับทุกเมืองที่อยู่ใต้มันลงไป

เราจะคิดจากล่างขึ้นบน เมืองหนึ่งถูกคิดหลังลูกของมันทุกคนคิดเสร็จแล้วเสมอ ลำดับแบบนี้เรียกว่าลำดับหลังลูก (post-order)

เส้นทางของถนนแต่ละเส้นไต่ขึ้นจากปลายทั้งสองข้าง ไปพบกันที่เมืองที่สูงที่สุดบนเส้นทาง เมืองนั้นเรียกว่าปมร่วมที่ต่ำที่สุด (lowest common ancestor ย่อว่า LCA) ของปลายทั้งสอง

เส้นทางไม่ขึ้นเหนือปมร่วมเลย ถนนแต่ละเส้นจึงตัดสินที่ปมร่วมของมันได้ และเพราะคิดจากล่างขึ้นบน ถึงตอนนั้นทุกเมืองบนเส้นทางก็คิดเสร็จไปแล้ว

ตัวอย่างในโจทย์ใช้ตรงนี้ไม่ได้ ต้นไม้ของมันเป็นเส้นตรง ทุกเมืองมีลูกไม่เกินหนึ่งคน จึงไม่มีอะไรให้เลือกจอง ตอนนี้จึงใช้ตัวอย่างเล็กอีกชุดตลอดทั้งตอน ต้นไม้ 12 เมือง กับถนนไม่ราดยาง 7 เส้น ทุกเส้นยาวคู่ เพราะเส้นคี่ถูกกฎที่ 1 ตัดไปแล้ว

ทำไม dp[2][{4}] ได้ 2: เมือง 2 ถูกจองลูก 4 ไปแล้ว ถนน 4-5 ต้องผ่านลูกคนนั้นจึงใช้ไม่ได้ เหลือ 2-8 น้ำหนัก 2 ที่ยังเก็บได้

ลองเดินทั้งต้นไม้ทีละเมืองตามลำดับหลังลูก แต่ละขั้นเส้นสีคือเส้นทางของถนนที่ตัดสินที่เมืองนั้น บรรทัดที่ขึ้นต้นด้วย [ ] บอกว่ากำลังเติม mask ไหน

ในโค้ด d0[j] คือ dp[ลูกคนที่ j][∅], cs คือถนนที่ปมร่วมอยู่ที่ v และ se คือบิตของลูกที่ถนนนั้นจอง ส่วน g คือแถว dp[v] ที่กำลังเติม

// g[mask] = น้ำหนักมากที่สุดในต้นไม้ย่อยของ v เมื่อลูกในเซต mask ถูกจองไปแล้ว
for (int mk = 0; mk < full; mk++) {
    long long s = sum;                         // ค่าเริ่มต้นคือปล่อยลูกทุกคนทำงานของตัวเอง
    for (int j = 0; j < k; j++) if (mk >> j & 1) s -= d0[j];
    g[mk] = s;
}
// ลูปนอกไล่ mk จากค่ามากลงมาหาค่าน้อย (เหตุผลอยู่ในข้อ 3 ของเช็กความเข้าใจ)
for (int mk = full - 1; mk >= 0; mk--)
    for (auto& c : cs)                         // cs = ถนนไม่ราดยางที่มีจุดร่วมสูงสุดอยู่ที่ v
        if (!(c.se & mk)) g[mk] = max(g[mk], c.val + g[mk | c.se]);

ที่ N ไม่เกิน 1000 การหาปมร่วมไม่ต้องใช้ท่าหรู ไต่ขึ้นตามพ่อทีละชั้นก็พอ ถนนแต่ละเส้นไต่ไม่เกิน N ชั้น ทั้งการหาปมร่วมและการรวม dp ตามเส้นทาง

• ไต่ตามเส้นทาง: ไม่เกิน M × N = 5,000,000 ก้าว
• ลองเก็บถนน: แต่ละเส้นถูกลองกับทุก mask ของปมร่วม ซึ่งมี 2^{จำนวนลูก} แบบ เพดานคือ M × 2¹⁰ = 5,120,000 ก้าว ปมร่วมส่วนใหญ่ลูกน้อยกว่านั้น ของจริงจึงน้อยกว่ามาก
• เติมค่าไม่เก็บ: เมืองที่มีลูก k คนใช้ราว 2^k × k ก้าว จำนวนลูกรวมทั้งต้นไม้คือ N − 1 จึงไม่เกิน (N − 1) × 2¹⁰ = 1,022,976 ก้าว
• งบเวลา 0.3 วินาที ใช้กฎหยาบ ๆ ว่าเครื่องทำได้ราว 10⁸ ก้าวต่อวินาที ได้ราว 30,000,000 ก้าว ทั้งสามก้อนอยู่ในงบ

#include <bits/stdc++.h>
using namespace std;
int n,mE;
vector<int> ch[1005];              // ลูกของแต่ละปม
int par[1005],dep[1005],idxInPar[1005];
vector<vector<int>> dp;            // dp[v][mask]
struct Ex{ int a,b,w,lca,sa,sb; }; // sa,sb = บิตของลูกที่เส้นทางใช้ (0 ถ้าไม่มี)
vector<Ex> exAt[1005];
vector<pair<int,int>> tadj[1005];

void bfsTree(){
    vector<int> st{1}; par[1]=0; dep[1]=0;
    vector<char> vis(n+1,0); vis[1]=1;
    for(size_t i=0;i<st.size();i++){ int u=st[i];
        for(auto&[v,w]:tadj[u]) if(!vis[v]){ vis[v]=1; par[v]=u; dep[v]=dep[u]+1; idxInPar[v]=(int)ch[u].size(); ch[u].push_back(v); st.push_back(v); }
    }
}
int lcaOf(int a,int b){ while(dep[a]>dep[b]) a=par[a]; while(dep[b]>dep[a]) b=par[b]; while(a!=b){ a=par[a]; b=par[b]; } return a; }
// ผลรวม dp ของปมบนเส้นทางจาก x ขึ้นไปหา v (ไม่รวม v) โดยแต่ละปมห้ามใช้ลูกที่เส้นทางเพิ่งผ่านมา
long long pathSum(int x,int v,int&firstChild){
    long long s=0; int prev=-1; firstChild=0;
    while(x!=v){ int mask = prev<0 ? 0 : (1<<idxInPar[prev]); s+=dp[x][mask]; prev=x; x=par[x]; }
    if(prev>=0) firstChild = 1<<idxInPar[prev];
    return s;
}
int main(){
    scanf("%d %d",&n,&mE);
    vector<array<int,3>> extra;
    long long total=0;
    for(int i=0;i<mE;i++){ int a,b,c; scanf("%d %d %d",&a,&b,&c);
        if(c==0){ tadj[a].push_back({b,0}); tadj[b].push_back({a,0}); }
        else { extra.push_back({a,b,c}); total+=c; } }
    bfsTree();
    for(auto&e:extra){
        int a=e[0],b=e[1],w=e[2],l=lcaOf(a,b);
        int len=dep[a]+dep[b]-2*dep[l];
        if(len%2==1) continue;                       // เส้นทางยาวคี่ วงจะเป็นคู่ ต้องตัดทิ้งเสมอ
        exAt[l].push_back({a,b,w,l,0,0});
    }
    dp.assign(n+1,{});
    // ไล่แบบ post-order ด้วยสแต็ก
    vector<int> order; order.reserve(n); { vector<int> st{1}; while(!st.empty()){ int u=st.back(); st.pop_back(); order.push_back(u); for(int c:ch[u]) st.push_back(c); } }
    for(int i=(int)order.size()-1;i>=0;i--){
        int v=order[i]; int k=(int)ch[v].size(); int full=1<<k;
        vector<long long> d0(k); long long sum=0;
        for(int j=0;j<k;j++){ d0[j]=dp[ch[v][j]][0]; sum+=d0[j]; }
        vector<long long> g(full);
        for(int mk=0;mk<full;mk++){ long long s=sum; for(int j=0;j<k;j++) if(mk>>j&1) s-=d0[j]; g[mk]=s; }
        // เตรียมค่าของเส้นพิเศษที่มี lca = v
        struct Cand{ int se; long long val; };
        vector<Cand> cs;
        for(auto&e:exAt[v]){
            int ca=0,cb=0;
            long long s=pathSum(e.a,v,ca)+pathSum(e.b,v,cb);
            cs.push_back({ca|cb, s+e.w});
        }
        for(int mk=full-1;mk>=0;mk--)
            for(auto&c:cs) if(!(c.se&mk)) g[mk]=max(g[mk],c.val+g[mk|c.se]);
        dp[v]=vector<int>(full);
        for(int mk=0;mk<full;mk++) dp[v][mk]=(int)g[mk];
    }
    printf("%lld\n", total - dp[1][0]);
}

• ผ่านตัวอย่างทั้งสองชุดของโจทย์ (ชุดที่ 2 ได้ 48 ตรงกับเฉลย)
• สุ่มเทียบกับตัวตรวจของตอนที่ 1 สามแบบ ไม่มีชุดไหนต่างกัน: ต้นไม้ไม่เกิน 7 เมืองกับถนนไม่ราดยางไม่เกิน 5 เส้น 1,000 ชุด · แบบเดียวกันแต่ยอมให้ถนนซ้ำคู่เมือง (ไม่เกิน 6 เส้น) 1,000 ชุด · ต้นไม้ 11 ถึง 14 เมืองที่เมืองหนึ่งมีลูกได้ถึง 10 คน ถนนไม่ราดยางไม่เกิน 10 เส้น 400 ชุด
• ขอบเขตของการสุ่มเทียบมีแค่กราฟเล็ก เพราะตัวตรวจไล่ทุกเซตและทุกวง กราฟใหญ่ตรวจได้แค่เวลา ไม่ได้ตรวจคำตอบ
• เคสใหญ่ 9 ชุด (N = 1,000 ถนนเกือบ 5,000 สาย ทุกเมืองไม่เกิน 10 สาย ต้นไม้สามรูปทรง: ลึก แตกกิ่ง และสุ่ม) ช้าที่สุด 11 มิลลิวินาที จากงบ 300

เวลาวัดบนเครื่องที่ใช้เขียน รวมเวลาเปิดโปรแกรมแล้ว ยังไม่ได้ส่งเข้าเครื่องตรวจของ programming.in.th