285484026

「网络流 24 题」最长递增子序列
「网络流 24 题」最长递增子序列题解:留坑#include <bits/stdc++.h> con...
扫描右侧二维码阅读全文
07
2018/10

「网络流 24 题」最长递增子序列

「网络流 24 题」最长递增子序列

题解:留坑

#include <bits/stdc++.h>

const int MAXN = 1000000,INF = 10000000;

using namespace std;

int n,t,s,Max = 1,e = 2,ans,tmp;
int d[MAXN],cur[MAXN],head[MAXN],dp[MAXN],a[MAXN];

struct node{
    int v,c,f,next;
}edge[MAXN];

inline void addedge(int u,int v,int w){
    edge[e] = (node){v,w,0,head[u]};head[u] = e++;
    edge[e] = (node){u,0,0,head[v]};head[v] = e++; 
}

inline void init(){
    scanf("%d",&n);
    for(int i = 1;i <= n;i++) scanf("%d",&a[i]);
    
    for(int i = 1;i <= n;i++) dp[i] = 1;
    
    for(int i = 1;i <= n;i++)
        for(int j = 1;j < i;j++)
            if(a[j] <= a[i])
                dp[i] = max(dp[i],dp[j]+1),
                    Max = max(Max,dp[i]);
    
    s = 0;t = 2*n+1;
    
    for(int i = 1;i <= n;i++)
        if(dp[i] == 1) addedge(s,i,1);
    
    for(int i = 1;i <= n;i++)
        if(dp[i] == Max) addedge(i+n,t,1);
    
    for(int i = 1;i <= n;i++) addedge(i,i+n,1);
    
    for(int i = 1;i <= n;i++)
        for(int j = i+1;j <= n;j++)
            if(a[i] <= a[j] && dp[i] + 1 == dp[j])
                addedge(i+n,j,1);
}

queue<int>Q;

inline bool bfs(){
    memset(d,0,sizeof(d));
    Q.push(s);d[s] = 1;
    while(!Q.empty()){
        int x = Q.front();Q.pop();
        for(int i = head[x];i;i = edge[i].next){
            node E = edge[i];
            if(!d[E.v] && E.c > E.f){
                d[E.v] = d[x] + 1;
                Q.push(E.v);
            }
        }
    }
    return d[t] ? true : false;
}

int dfs(int x,int a){
    if(x == t || a == 0) return a;
    int flow = 0,f;
    for(int &i = cur[x];i;i = edge[i].next){
        node &E = edge[i];
        if(d[E.v] == d[x] + 1 && (f = dfs(E.v,min(E.c-E.f,a))) > 0){
            E.f += f;
            edge[i^1].f -= f;
            a -= f;
            flow += f;
            if(a == 0) break;
        }
    }
    return flow;
}

inline int max_flow()
{
    int flow = 0;
    while(bfs())
    {
        for(int i = s;i <= t;i++) cur[i] = head[i];
        flow += dfs(s,INF);
    }
    return flow;
}

int main()
{
    #ifdef hi_archer
      freopen("input.txt", "r", stdin);
    #endif
    init();
    printf("%d\n",Max);
    ans = max_flow();
    printf("%d\n",ans);
    
    for(int i = head[1];i;i = edge[i].next) if(edge[i].v == 1 + n) edge[i].c = INF;
    for(int i = head[n];i;i = edge[i].next) if(edge[i].v == n + n) edge[i].c = INF;
    
    for(int i = head[n+1];i;i = edge[i].next) if(edge[i].v == t) edge[i].c = INF;
    for(int i = head[n+n];i;i = edge[i].next) if(edge[i].v == t) edge[i].c = INF;    
    
    for(int i = head[s];i;i = edge[i].next) 
        if(edge[i].v == 1 || edge[i].v == n)
            edge[i].c = INF;
            
    tmp = max_flow();
    if(tmp < INF) ans += tmp;
    printf("%d\n",ans);
    return 0;
}
Last modification:October 7th, 2018 at 11:45 am
If you think my article is useful to you, please feel free to appreciate

Leave a Comment