dinic36ptsWA求助

fangzichang @ 2022-09-10 18:22:54

by metaphysis @ 2022-09-11 10:09:09

@fangzichang

题解的解题思路是正确的，但是实现有小问题，对于边界测试数据：

1
1

无法得到正确结果（实际上，第一篇和第二篇的题解所附的参考代码均无法获得 Accepted）。

您的代码中主要有两处小错误，原因在于对解题思路并未彻底理解就开始着手实现：

（1）题面给定的是不下降序列，则需要取等于号。

for (int i = 1; i <= n; i++)
    {
        dp[i] = 1;
        for (int j = 1; j < i; j++)
        {
            //if (a[j] < a[i])
            if (a[j] <= a[i])
            {
                if (dp[j] + 1 > dp[i])
                {
                    // v[i].clear();
                    dp[i] = dp[j] + 1;
                }
            }
        }
        ans1 = max(ans1, dp[i]);
    }

（2）建图发生错误，若 len = 1，您原来的建图逻辑就是错误的：

//if(dp[i]==1)add(s,i,1);
//else if(dp[i]==ans1)add(i+n,t,1); 
if (dp[i] == 1) add(s, i, 1);
if (dp[i] == ans1) add(i + n, t, 1);

最后再考虑如何处理一下边界测试数据就可以通过了。可以提醒下管理员，前面两篇题解的参考代码有问题，需要标注下，以免误导初学者。

by metaphysis @ 2022-09-11 10:15:50

@fangzichang

对于目前测试数据，能够获得 Accepted 的代码：

#include <bits/stdc++.h>

#define int long long
#define inf 0x3f3f3f3f

using namespace std;
const int N = 100010;

int n, m, s, t;
int head[N], to[N], nxt[N];
int dep[N], data[N], dp[N], a[N];
int cnt = 1;
int ans1, ans2;

void add(int u, int v, int w)
{
    cnt++;
    to[cnt] = v;
    data[cnt] = w;
    nxt[cnt] = head[u];
    head[u] = cnt;
    cnt++;
    to[cnt] = u;
    data[cnt] = 0;
    nxt[cnt] = head[v];
    head[v] = cnt;
}

int dfs(int u, int ru)
{
    if (u == t)
        return ru;
    int chu = 0, res = 0, v = 0;
    for (int p = head[u]; p; p = nxt[p])
    {
        v = to[p];
        if (data[p] && dep[u] + 1 == dep[v])
        {
            res = dfs(v, min(data[p], ru));
            data[p] -= res;
            data[p ^ 1] += res;
            ru -= res;
            chu += res;
        }
    }
    if (chu == 0)
        dep[u] = -1;
    //return chu;
    return chu == inf ? 0 : chu;
}

bool bfs()
{
    memset(dep, 0, sizeof(dep));
    queue<int> q;
    q.push(s);
    dep[s] = 1;
    while (q.size())
    {
        int u = q.front();
        q.pop();
        for (int p = head[u]; p; p = nxt[p])
        {
            int v = to[p];
            if (data[p] && !dep[v])
            {
                dep[v] = dep[u] + 1;
                q.push(v);
            }
        }
    }
    return dep[t];
}

signed main()
{
    scanf("%lld", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%lld", &a[i]);
    }
    for (int i = 1; i <= n; i++)
    {
        dp[i] = 1;
        for (int j = 1; j < i; j++)
        {
            //if (a[j] < a[i])
            if (a[j] <= a[i])
            {
                if (dp[j] + 1 > dp[i])
                {
                    // v[i].clear();
                    dp[i] = dp[j] + 1;
                }
            }
        }
        ans1 = max(ans1, dp[i]);
    }
    printf("%lld\n", ans1);
    s = 0, t = n * 2 + 1;
    for (int i = 1; i <= n; i++)
    {
        add(i, i + n, 1);
        //if(dp[i]==1)add(s,i,1);
        //else if(dp[i]==ans1)add(i+n,t,1); 
        if (dp[i] == 1) add(s, i, 1);
        if (dp[i] == ans1) add(i + n, t, 1);
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j < i; j++)
        {
            if (a[j] <= a[i] && dp[j] == dp[i] - 1)
                add(j + n, i, 1);
        }
    }

    int ans2 = 0;
    while (bfs())
    {
        //ans2 += dfs(s, 1e18);
        ans2 += dfs(s, inf);
    }
    printf("%lld\n", ans2);
    add(1, 1 + n, inf);
    add(s, 1, inf);
    if (dp[n] == ans1)
    {
        add(n * 2, t, inf);
        add(n, n * 2, inf);
    }
    while (bfs())
    {
        //ans2 += dfs(s, 1e18);
        ans2 += dfs(s, inf);
    }
    printf("%lld\n", ans2);
    return 0;
}

by fangzichang @ 2022-09-11 11:27:53

@metaphysis 感谢大佬，讲得很仔细，关注送上

by fangzichang @ 2022-09-11 13:24:39

@metaphysis Accepted，感谢

by Algae_qwq @ 2022-09-21 20:56:09

海亮巨佬爆切网络流紫题

by fangzichang @ 2022-09-24 21:05:11

@yc_ldh %%%每次见巨佬都会得到新的教诲

by Algae_qwq @ 2022-09-24 21:07:38

@fangzichang 您吊打我，我只会暴力