第一问入门题：dp[i]表示:以i结尾的LIS。
后面要用到这个dp思想:
为了让选择的每条IS长度等于mx_dp[i],我们可以这样建模：
以所有dp[i]==1为非递减序列的起点，源点连向这些点S，边权为1.
以所有dp[i]==mx为非递减序列的终点，这些点连向汇点T,边权为1.
所有i，j满足：a[i] <= a[j] && i < j && dp[i]+1 == dp[j] , 从i 向j连边，边权为1。
以上方法建模刚好满足从S到T的每一条路径的长度都为mx+2,(多的2是起点和终点的边)，由于每条边的边权都是1，这限制了每个点只能选择一次。刚好满足题意！！
这就是利用了分层图的思想建边。
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int M = 250000+7; const int N = 500+7; struct Dinic{ //N个点，M条边 //add建双向边，然后D.gao ,最后输出maxflow #define inf 0x3f3f3f3f ll maxflow;int s,t,n; int v[N],pre[N],d[N],now[N]; ll incf[N]; int head[N],cnt=1; struct EDGE{int to,nxt;ll w;}ee[M*2]; inline void AD(int x,int y,ll w){ee[++cnt].nxt=head[x],ee[cnt].w=w,ee[cnt].to=y,head[x]=cnt;} inline void add(int x,int y,ll w){AD(x,y,w);AD(y,x,0);} inline bool bfs()//在残量网络上构造分层图 { memset(d,0,sizeof(d)); queue<int>q; q.push(s);d[s]=1; while(q.size()) { int x=q.front();q.pop(); for(int i=head[x];i;i=ee[i].nxt) { int y=ee[i].to;ll w=ee[i].w; if(w&&!d[y]) { q.push(y); d[y]=d[x]+1; if(y==t)return 1; } } } return false; } inline int dinic(int x,int flow) { if(x==t)return flow; ll rest = flow,k; for(int i=now[x];i&&rest;i=ee[i].nxt) { int y=ee[i].to;ll w= ee[i].w; now[x]=i; if(w&&d[y]==d[x]+1) { k=dinic(y,min(rest,w)); if(!k)d[y]=0;//剪枝，去掉增广完毕的点 ee[i].w-=k; ee[i^1].w+=k; rest-=k; } } return flow - rest; } inline void gao() { int flow=0; while(bfs()) { for(int i=0;i<=n;i++)now[i]=head[i]; while(flow=dinic(s,inf))maxflow+=flow; } } inline void init(int nn,int S,int T) { cnt=1;maxflow=0; for(int i=0;i<=n;i++)head[i]=0; s=S,t=T,n=nn; } }D; //求解二分图匹配问题时的复杂度是：m*sqrt(n)的 int id[507][507]; int a[507],dp[507]; int main() { int n,m,s,t,x; cin>>n; int N = n+2,mx=0; s=n+1,t=n+2; D.init(N,s,t);//初始化节点个数，起点，终点 for(int i=1;i<=n;i++)cin>>a[i]; for(int i=1;i<=n;i++) for(int j=0;j<i;j++) if(a[i]>=a[j])dp[i]=max(dp[i],dp[j]+1),mx=max(mx,dp[i]); cout<<mx<<endl; for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) if(dp[i]+1==dp[j]&&a[i]<=a[j]){//每个点只连其后继 D.add(i,j,1); // cout<<i<< " "<<j<<endl; } for(int i=1;i<=n;i++){ if(dp[i]==1)D.add(s,i,1);//该数做为起点 if(dp[i]==mx)D.add(i,t,1);//该数做为终点 //流量设为1，即每个数只能用一次，由于我们每个点都连其后继， //则网络上每条 路径最终长度都是2！ } D.gao(); cout<<D.maxflow<<endl; D.add(s,1,inf); if(dp[n]==mx)D.add(n,t,inf);//注意终点必须是dp长度为n，否则不加 D.gao(); if(n==1)cout<<1<<endl; else cout<<D.maxflow<<endl; /* for(int x=1;x<=n;x++)/打印最大流的边 for(int i=D.head[x];i;i=D.ee[i].nxt){ int y=D.ee[i].to,w=D.ee[i].w; if(x<y&&w==0&&y!=24) cout<<x<<" -> "<<y<<" = "<<w<<endl; }*/ return 0; } /* 23 18 21 7 22 8 23 3 16 14 11 19 4 20 6 15 13 12 5 2 10 9 17 1 6 2 3 1 5 2 3 */
