[CF Round603 Div2 F]Economic Difficulties

题目：Economic Difficulties

传送门:https://codeforces.com/contest/1263/problem/F

题意：给了两棵tree:Ta（拥有a个节点，节点编号为[n+1, n+a]) Tb（拥有b个节点，节点编号: [n+ a + 1, n + a + b]) 其中两颗tree的叶子节点按照dfs序依次连续连向 $ i, i \in [1, n] $节点，询问最多可以去掉多少的tree上节点，使得每一个$i , i \in [1, n]$ 仍然可以连通Ta,或者Tb的根节点。

分析：

1.做法一：https://codeforces.com/blog/entry/71844?locale=en

类似泛化背包，每个物品要么选择a，要么选择b，连续选择有额外贡献，假设cost_a[i,j]代表[i,j]区间选择a的贡献，cost_b[i,j]代表[i,j]区间选择b的贡献。

dp[i]代表前i个节点，方程：$$ dp[i] = max\{dp[j] + cost[j+1,i] \}$$

 #include <bits/stdc++.h>

 using namespace std;

 vector< vector<int> > calc_cost(int vn, int n, vector<int> fa, vector<int> tg) {

     vector< vector<int> > res(n+, vector<int>(n+));

     for (int l = ; l <= n; l++) {

         vector<int> deg(vn+);

         for (int i = ; i <= vn ; i++) deg[fa[i]]++;

         int val = ;

         for (int r = l; r <= n; r++) {

             for(int v = tg[r]; v !=  && deg[v] == ; --deg[v = fa[v]])

                 val++;

             res[l][r] = val;

         }

     }

     return res;

 }

 int main() {

     int n;

     scanf("%d", &n);

     vector< vector<int> > cost[];

     for (int j = ; j < ; j++) {

         int vn;

         scanf("%d", &vn);

         vector<int> fa(vn+);

         vector<int> tg(n+);

         for (int i = ; i <= vn; i++) scanf("%d", &fa[i]);

         for (int i = ; i <= n;  i++)  scanf("%d", &tg[i]);

         cost[j] = calc_cost(vn, n, fa, tg);

     }

     vector<int> dp(n + , );

     for (int i = ; i <= n; i++)

         for (int j = ; j < i; j++)

             dp[i] = max(dp[i], dp[j] + max(cost[][j+][i], cost[][j+][i]));

     printf("%d", dp[n]);

     return ;

 }

2.基于最后的结果，我们肯定是选择Ta和Tb的一些节点，去除这些节点及其后代节点，考虑到这里，我们只要把每个节点控制的区间算出来，然后按照左端点或者有端点排序，然后做限制背包dp。

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e4 + ;

const int INF = 1e9 + ;

vector< pair<pair<int,int>, int> > vec;

int sz[MAXN], st[MAXN], ed[MAXN], tg[MAXN];

vector<int> G[MAXN];

void dfs(int u) {

    sz[u] = ;

    st[u] = INF; ed[u] = -INF;

    if(tg[u]) st[u] = ed[u] = tg[u];

    for(auto v : G[u]) {

        dfs(v);

        sz[u] += sz[v];

        st[u] = min(st[u], st[v]);

        ed[u] = max(ed[u], ed[v]);

    }

    vec.push_back(make_pair(make_pair(ed[u], st[u] - ), sz[u]-(u == )));

}

int dp[MAXN];

int main() {

    int n, a, x;

    scanf("%d", &n);

    for(int j = ; j < ; j++) {

        scanf("%d", &a);

        for(int i = ;i <= a; i++) {

            scanf("%d", &x);

            G[x].push_back(i);

        }

        for(int i = ; i <= n; i++) {

            scanf("%d", &x);

            tg[x] = i;

        }

        dfs();

        for(int i = ; i <= a; i++) {

            G[i].clear();

            tg[i] = ;

        }

    }

    sort(vec.begin(), vec.end());

    for(auto it : vec) {

        int l = it.first.second, r = it.first.first;

        dp[r] = max(dp[r], dp[l] + it.second);

    }

    printf("%d", dp[n]);

    return ;

}

3.和文理分科类似，该题也可以用网络流求解，然而我到现在都不知道为啥是对的。

#include <bits/stdc++.h>

using namespace std;

typedef int LL;

const int MAXN = 1e5 + ;

const int MAXM = 1e5 + ;

const int INF = 1e9 + ;

namespace NWF {

    struct Edge {

        int to, nxt;LL f;

    } e[MAXM << ];

    int S, T, tot;

    int ecnt, head[MAXN], cur[MAXN], dis[MAXN];

    queue<int> q;

    void init(int _S, int _T, int _tot){

        ecnt = ; S = _S; T = _T; tot = _tot;

        memset(head, , (tot + ) * sizeof(int));

    }

    void addEdge(int u, int v, LL f) {

        e[++ecnt] = (Edge) {v, head[u], f}; head[u] = ecnt;

        e[++ecnt] = (Edge) {u, head[v], }; head[v] = ecnt;

    }

    bool bfs() {

        memset(dis, , (tot + ) * sizeof(int));

        q.push(S); dis[S] = ;

        while (!q.empty()) {

            int u = q.front(), v; q.pop();

            for (int i = cur[u] = head[u]; i ; i = e[i].nxt) {

                if (e[i].f && !dis[v = e[i].to]) {

                    q.push(v);

                    dis[v] = dis[u] + ;

                }

            }

        }

        return dis[T];

    }

    LL dfs(int u, LL maxf) {

        if (u == T) return maxf;

        LL sumf = maxf;

        for (int &i = cur[u]; i; i = e[i].nxt) {

            if (e[i].f && dis[e[i].to] > dis[u]) {

                LL tmpf = dfs(e[i].to, min(sumf, e[i].f));

                e[i].f -= tmpf; e[i ^ ].f += tmpf;

                sumf -= tmpf;

                if (!sumf) return maxf;

            }

        }

        return maxf - sumf;

    }

    LL dinic() {

        LL ret = ;

        while (bfs()) ret += dfs(S, INF);

        return ret;

    }

}

int faa[MAXN], fab[MAXN], tga[MAXN], tgb[MAXN];

int main() {

    int n, A, B;

    scanf("%d", &n);

    scanf("%d", &A);

    for(int i = ;i <= A; i++) scanf("%d", faa+i);

    for(int i = ; i <= n; i++) scanf("%d", tga + i);

    scanf("%d", &B);

    for(int i = ;i <= B; i++) scanf("%d", fab+i);

    for(int i = ; i <= n; i++) scanf("%d", tgb + i);

    NWF::init(A+B+,A+B+, A+B+);

    for (int i = ; i <= A; i++) {

        NWF::addEdge(NWF::S, i, );

        NWF::addEdge(faa[i], i, INF);

    }

    for (int i = ; i <= B; i++) {

        NWF::addEdge(A + i, A + fab[i], INF);

        NWF::addEdge(A + i, NWF::T, );

    }

    for (int i = ; i <= n; i++)

        NWF::addEdge(tga[i], A + tgb[i], INF);

    int ans = A -  + B -  - NWF::dinic();

    printf("%d", ans);

    return ;

}

#include <bits/stdc++.h>

using namespace std;

typedef int LL;

const int MAXN = 1e5 + ;

const int MAXM = 1e5 + ;

const int INF = 1e9 + ;

namespace NWF {

    struct Edge{

        int to, nxt;LL f;

    }e[MAXM << ];

    int S, T, tot;

    int ecnt, head[MAXN], cur[MAXN], pre[MAXN], num[MAXN], dis[MAXN];

    queue<int> q;

    void init(int _S, int _T, int _tot){

        ecnt = ; S = _S; T = _T; tot = _tot;

        memset(num,  , (tot + ) * sizeof(int));

        memset(head, , (tot + ) * sizeof(int));

    }

    inline void addEdge(int u, int v, LL f) {

        e[++ecnt] = (Edge) {v, head[u], f}; head[u] = ecnt;

        e[++ecnt] = (Edge) {u, head[v], }; head[v] = ecnt;

    }

    void bfs() {

        memset(dis, , (tot + ) * sizeof(int));

        q.push(T);

        dis[T] = ;

        while(!q.empty()) {

            int u = q.front(), v; q.pop();

            num[dis[u]]++;

            for(int i = cur[u] = head[u]; i; i = e[i].nxt) {

                if(!dis[v = e[i].to]) {

                    dis[v] = dis[u] + ;

                    q.push(v);

                }

            }

        }

    }

    LL augment() {

        LL flow = INF;

        for(int i = S; i != T; i = e[cur[i]].to)

            flow = min(flow, e[cur[i]].f);

        for(int i = S; i != T; i = e[cur[i]].to) {

            e[cur[i]].f -= flow;

            e[cur[i] ^ ].f += flow;

        }

        return flow;

    }

    LL isap() {

        bfs();

        int u = S, v;

        LL flow = ;

        while(dis[S] <= tot) {

            if(u == T) {

                flow += augment();

                u = S;

            }

            bool fg = ;

            for(int i = cur[u]; i; i = e[i].nxt) {

                if(e[i].f && dis[u] > dis[v = e[i].to]) {

                    pre[v] = u;

                    cur[u] = i;

                    u = v;

                    fg = ;

                    break;

                }

            }

            if(fg) continue;

            if(!--num[dis[u]]) break;

            int maxDis = tot;

            for(int i = head[u]; i; i = e[i].nxt) {

                if(e[i].f && maxDis > dis[v = e[i].to]) {

                    maxDis = dis[v];

                    cur[u] = i;

                }

            }

            num[dis[u] = maxDis + ]++;

            if(u != S) u = pre[u];

        }

        return flow;

    }

}

int faa[MAXN], fab[MAXN], tga[MAXN], tgb[MAXN];

int main() {

    int n, A, B;

    scanf("%d", &n);

    scanf("%d", &A);

    for(int i = ;i <= A; i++) scanf("%d", faa+i);

    for(int i = ; i <= n; i++) scanf("%d", tga + i);

    scanf("%d", &B);

    for(int i = ;i <= B; i++) scanf("%d", fab+i);

    for(int i = ; i <= n; i++) scanf("%d", tgb + i);

    NWF::init(A+B+,A+B+, A+B+);

    for (int i = ; i <= A; i++) {

        NWF::addEdge(NWF::S, i, );

        NWF::addEdge(faa[i], i, INF);

    }

    for (int i = ; i <= B; i++) {

        NWF::addEdge(A + i, A + fab[i], INF);

        NWF::addEdge(A + i, NWF::T, );

    }

    for (int i = ; i <= n; i++)

        NWF::addEdge(tga[i], A + tgb[i], INF);

    int ans = A -  + B -  - NWF::isap();

    printf("%d", ans);

    return ;

}

巴特西

[CF Round603 Div2 F]Economic Difficulties

最新文章

热门文章