【题解】最长递增子序列问题 Luogu2766 最大流

传送门：https://www.luogu.org/problemnew/show/P2766
从WC2017讲义上看到的这题，然后发现luogu上有。。。
对于第一问，先是直接一个二维的DP（虽然可以优化），然后将一个数拆成两个点，中间连一条容量为1的边。对于\(dp[i]=1\)的点，从源点向它连边，对于\(dp[i]=ans\)的点，从它向汇点连边，然后跑Dinic即可。最后一问应该取消相关的容量限制，但是搞了我好久。。。我好弱啊QAQ
AC代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int MAXN = 1010;
const int INF = 20000000;
struct Edge {
    int from,to,cap,flow;
    Edge() {}
    Edge(int from,int to,int cap,int flow): from(from),to(to),cap(cap),flow(flow) {}
};
struct Dinic{
    int n,m,s,t;
    vector <Edge> edges;
    vector <int> g[MAXN];
    bool visit[MAXN];
    int dist[MAXN];
    int cur[MAXN];
    void addedge(int from,int to,int cap)
    {
        edges.push_back(Edge(from,to,cap,0));
        edges.push_back(Edge(to,from,0,0));
        m = edges.size();
        g[from].push_back(m-2);
        g[to].push_back(m-1);
    }
    bool bfs() {
        memset(visit,0,sizeof visit);
        queue<int> q;
        q.push(s);
        dist[s] = 0;
        visit[s] = 1;
        while(!q.empty())
        {
            int now = q.front();
            q.pop();
            for(int i = 0; i < g[now].size(); ++i)
            {
                Edge &e = edges[g[now][i]];
                if(!visit[e.to] && e.cap > e.flow)
                {
                    visit[e.to] = 1;
                    dist[e.to] = dist[now] + 1;
                    q.push(e.to);
                }
            }
        }
        return visit[t];
    }
    int dfs(int x,int res)
    {
        if(x == t || !res) return res;
        int flow = 0,f;
        for(int i = 0; i < g[x].size(); ++i)
        {
            Edge &e = edges[g[x][i]];
            if(dist[x] + 1 == dist[e.to] && (f = dfs(e.to,min(res,e.cap - e.flow))) > 0)
            {
                e.flow += f;
                edges[g[x][i]^1].flow -= f;
                flow += f;
                res -= f;
                if(!res) break;
            }
        }
        return flow;
    }
}dinic;
int n;
int xu[MAXN],dp[MAXN];
int get_1(int i)
{
    return 2*i-1;
}
int get_2(int i)
{
    return 2*i;
}
int main()
{
    scanf("%d",&n);
    for(int i = 1; i <= n; ++i)
        scanf("%d",xu+i);
    dp[1] = 1;
    for(int i = 2; i <= n; ++i)
    {
        dp[i] = 1;
        for(int j = 1; j < i; ++j)
            if(xu[j] <= xu[i]) dp[i] = max(dp[i],dp[j]+1);
    }
    int ans = -1;
    for(int i = 1; i <= n; ++i) ans = max(ans,dp[i]);
    printf("%d\n",ans);
    for(int i = 1; i <= n; ++i)
        dinic.addedge(get_1(i),get_2(i),1);
    for(int i = 1; i <= n; ++i)
    {
        if(dp[i] == 1)
        {
            dinic.addedge(0,get_1(i),1);
        }
        if(dp[i] == ans)
        {
            dinic.addedge(get_2(i),2*n+1,1);
        }
    }
    for(int i = 1; i <= n; ++i)
        for(int j = i+1; j <= n; ++j)
            if(xu[i] <= xu[j] && dp[i]+1 == dp[j]) {dinic.addedge(get_2(i),get_1(j),1);}
    dinic.s = 0;
    dinic.t = 2*n+1;
    int ans1 = 0;
    while(dinic.bfs()) ans1 += dinic.dfs(0,INF);
    printf("%d\n",ans1);
    dinic.addedge(get_1(1),get_2(1),INF);
    dinic.addedge(0,get_1(1),INF);
    if(dp[n] == ans) dinic.addedge(get_1(n),get_2(n),INF),dinic.addedge(get_2(n),2*n+1,INF);
    while(dinic.bfs()) ans1 += dinic.dfs(0,2*n+1);
    printf("%d\n",ans1);
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <vector>

#include <queue>

using namespace std;

const int MAXN = 1010;

const int INF = 20000000;

struct Edge {

int from,to,cap,flow;

Edge() {}

Edge(int from,int to,int cap,int flow): from(from),to(to),cap(cap),flow(flow) {}

};

struct Dinic{

int n,m,s,t;

vector <Edge> edges;

vector <int> g[MAXN];

bool visit[MAXN];

int dist[MAXN];

int cur[MAXN];

void addedge(int from,int to,int cap)

{

edges.push_back(Edge(from,to,cap,0));

edges.push_back(Edge(to,from,0,0));

m = edges.size();

g[from].push_back(m-2);

g[to].push_back(m-1);

}

bool bfs() {

memset(visit,0,sizeof visit);

queue<int> q;

q.push(s);

dist[s] = 0;

visit[s] = 1;

while(!q.empty())

{

int now = q.front();

q.pop();

for(int i = 0; i < g[now].size(); ++i)

{

Edge &e = edges[g[now][i]];

if(!visit[e.to] && e.cap > e.flow)

{

visit[e.to] = 1;

dist[e.to] = dist[now] + 1;

q.push(e.to);

}

return visit[t];

}

int dfs(int x,int res)

{

if(x == t || !res) return res;

int flow = 0,f;

for(int i = 0; i < g[x].size(); ++i)

{

Edge &e = edges[g[x][i]];

if(dist[x] + 1 == dist[e.to] && (f = dfs(e.to,min(res,e.cap - e.flow))) > 0)

{

e.flow += f;

edges[g[x][i]^1].flow -= f;

flow += f;

res -= f;

if(!res) break;

}

return flow;

}

}dinic;

int n;

int xu[MAXN],dp[MAXN];

int get_1(int i)

{

return 2*i-1;

}

int get_2(int i)

{

return 2*i;

}

int main()

{

scanf("%d",&n);

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

scanf("%d",xu+i);

dp[1] = 1;

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

{

dp[i] = 1;

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

if(xu[j] <= xu[i]) dp[i] = max(dp[i],dp[j]+1);

}

int ans = -1;

for(int i = 1; i <= n; ++i) ans = max(ans,dp[i]);

printf("%d\n",ans);

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

dinic.addedge(get_1(i),get_2(i),1);

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

{

if(dp[i] == 1)

{

dinic.addedge(0,get_1(i),1);

}

if(dp[i] == ans)

{

dinic.addedge(get_2(i),2*n+1,1);

}

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

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

if(xu[i] <= xu[j] && dp[i]+1 == dp[j]) {dinic.addedge(get_2(i),get_1(j),1);}

dinic.s = 0;

dinic.t = 2*n+1;

int ans1 = 0;

while(dinic.bfs()) ans1 += dinic.dfs(0,INF);

printf("%d\n",ans1);

dinic.addedge(get_1(1),get_2(1),INF);

dinic.addedge(0,get_1(1),INF);

if(dp[n] == ans) dinic.addedge(get_1(n),get_2(n),INF),dinic.addedge(get_2(n),2*n+1,INF);

while(dinic.bfs()) ans1 += dinic.dfs(0,2*n+1);

printf("%d\n",ans1);

return 0;

}