Brief description:

。。树的路径覆盖。

Analysis:

const int N = 10009;

int hd[N], suc[N*2], to[N*2], deg[N]; VI adj[N];
int f0[N], f1[N], p0[N], p1[N]; bool vis[N];
int n;

#define v to[i]
void dfs(int p = 0, int u = 1){

    REP_G(i, u) if (v != p){
        dfs(u, v), f0[u] += f0[v];
    }

    if (!f0[u]){ // is leaf .. .
        f0[u] = f1[u] = 1;
    }
    else {
        f1[u] = f0[u];

        int t1 = INF; REP_G(i, u) if (v != p){
            if (f1[v] - f1[v] < t1){
                t1 = f1[v] - f0[v];
                p1[u] = v;
            }
        }

        int t0 = INF; REP_G(i, u) if (v != p && v != p1[u]){
            if (f1[v] - f1[v] < t0){
                t0 = f1[v] - f0[v];
                p0[u] = v;
            }
        }
        f1[u] += t1, f0[u] += t0 + t1 - 1;
        checkMin(f0[u], f1[u]);
    }
}

void gao(int u = 1, bool flag = false){ // 是否允许分岔。

    vis[u] = true;

    if (p0[u] && !flag){
        adj[u].PB(p0[u]);
        adj[p0[u]].PB(u);
        gao(p0[u], 1);
    }

    if (p1[u]){
        adj[u].PB(p1[u]);
        adj[p1[u]].PB(u);
        gao(p1[u], 1);
    }

    REP_G(i, u) if (!vis[v]) gao(v) ;
}


#undef v
#define v (*it)
void out(int u){
    vis[u] = true; ECH(it, adj[u]) if (!vis[v]){
        printf(" %d" , v);
        out(v) ;
    }
}

int main(){

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif

#define a to[i^1]
#define b to[i]

    Rush{

        RST(hd, f0, f1, p0, p1);

        FOR_C(i, 2, RD(n)<<1){
            RD(a, b);
            suc[i] = hd[a], hd[a] = i++;
            suc[i] = hd[a], hd[a] = i;
        }

        dfs(); OT(f0[1]);

        REP_1(i, n) CLR(adj[i]);

        RST(vis); gao(); RST(vis); REP_1(u, n) if (!vis[u] && SZ(adj[u]) <= 1){
            printf("%d", u); out(u);
            puts("");
        }
    }
}

const int N = 10009;

int hd[N], suc[N*2], to[N*2], deg[N];
bool vis[N];
int n;

#define v to[i]

VVI path; VI cur;

void gao(int u){
    vis[u] = true; cur.PB(u);
    REP_G(i, u) if (!vis[v]) gao(v);
}

void dfs(int p = 0, int u = 1){

    //cout << " " << u << endl;

    REP_G(i, u) if (v != p){
        dfs(u, v);
    }

    //cout << u << " " << deg[u] << endl;

    if (deg[u] <= 1 && p) ++deg[p];
    else {
        int c = 0; CLR(cur); vis[u] = true;
        REP_G(i, u) if (v != p && deg[v] <= 1){

            /*cout << "--" << u << " " << v << endl;
            cout << "--"; REP(i, SZ(cur)) cout << cur[i] << " ";
            cout << endl;*/

            if (!c) gao(v), reverse(ALL(cur)), cur.PB(u);
            else if (c == 1) gao(v);
            else{
                if (SZ(cur)) path.PB(cur), CLR(cur);
                gao(v);
            }
            ++c;
        }
        //cout << c << endl;

        if (SZ(cur)) path.PB(cur);
        else if (!c) cur.PB(u), path.PB(cur);
    }
}


int main(){

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif

#define a to[i^1]
#define b to[i]

    Rush{

        RST(hd, deg, vis); CLR(path);

        FOR_C(i, 2, RD(n)<<1){
            RD(a, b);
            suc[i] = hd[a], hd[a] = i++;
            suc[i] = hd[a], hd[a] = i;
        }

        dfs();

        OT(SZ(path)); REP(i, SZ(path)){
            printf("%d", path[i][0]); FOR(j, 1, SZ(path[i])) printf(" %d", path[i][j]);
            puts("");
        }
    }
}

（无论从哪方面看。。这题似乎。。贪心都要更优越一些。。/w\。。

External link:

http://www.spoj.com/problems/PT07F/

Posted by xiaodao
Category: Play with trees, SPOJ