【codevs1906】[网络流24题]最长递增子序列问题

2019-11-08 03:00:27

字体：大中小

来源：转载

供稿：网友

一开始没想出来= =，只会DP，后来想想其实挺简单的，应该是好久没写网络流了。其实这道题求得的是最长不下降子序列。拆点，保证每个点只取一次，所以流量为1 然后直接建图就好了源点向dp[i]=1的点连一条容量为1的边 dp[i]=ans的点向汇点连容量为1的边然后在dp的时候判断当前点是由前面那个点转移过来的，从前面的点向当前的点连一条容量为1的边，然后跑最大流可以求出第二问. 第三问把第一个点的边和第n的点的两条边（共四条）改成inf就好了，直接跑最大流求出第三问.

#include<iostream>#include<cstdio>#include<cstring>#include<string>#include<algorithm>#include<queue>using namespace std;const int N=10010,inf=0x3f3f3f3f;int ans,s,t,n,m,te;int head[N],dp[N],val[N],cur[N],p[N],num[N],d[N];struct edge{ int u,v,cap,flow,next;}e[200010];queue<int>q;void add(int u,int v,int cap){ e[++te].cap=cap; e[te].flow=0; e[te].u=u; e[te].v=v; e[te].next=head[u]; head[u]=te;}void bfs(){ memset(d,0,sizeof(d)); while(!q.empty())q.pop(); q.push(t); while(!q.empty()) { int v=q.front();q.pop(); for (int i=head[v];i;i=e[i].next) { int u=e[i].v; if (e[i].cap==0&&!d[u]) { d[u]=d[v]+1; q.push(u); } } }}int augment(){ int x=t,a=inf; while(x!=s) { a=min(a,e[p[x]].cap-e[p[x]].flow);// cout<<e[p[x]].u<<' '; x=e[p[x]].u; }// cout<<endl; x=t; while(x!=s) { e[p[x]].flow+=a; e[p[x]^1].flow-=a; x=e[p[x]].u; } return a;}int isap(){ int x=s,flow=0; memset(num,0,sizeof(num)); copy(head,head+n+1,cur); bfs(); for (int i=1;i<=n;i++) ++num[d[i]]; while(d[s]<n) {// cout<<x<<endl; if (x==t) { flow+=augment(); x=s; } int ok=0; for(int i=cur[x];i;i=e[i].next) { int v=e[i].v; if (e[i].cap>e[i].flow&&d[v]+1==d[x]) { p[v]=i; ok=1; cur[x]=i; x=v; break; } } if (!ok) { if (--num[d[x]]==0)break; int mx=n-1; for (int i=head[x];i;i=e[i].next) { int v=e[i].v; if (e[i].cap>e[i].flow) mx=min(mx,d[v]); } ++num[d[x]=mx+1]; cur[x]=head[x]; if (x!=s)x=e[p[x]].u; } } return flow;}int main(){ te=1;ans=1; memset(head,0,sizeof(head)); cin>>n; int k=n<<1,nn=n; for (int i=1;i<=n;++i) scanf("%d",&val[i]); for (int i=1;i<=n;++i) { dp[i]=1; for (int j=1;j<i;++j) if (val[i]>=val[j]) dp[i]=max(dp[i],dp[j]+1); for (int j=1;j<i;++j) if (dp[j]==dp[i]-1&&val[i]>=val[j]) add(j+n,i,1),add(i,j+n,0); ans=max(ans,dp[i]); } cout<<ans<<endl; if (ans==1) { cout<<n<<endl<<n<<endl; return 0; } for (int i=1;i<=n;++i) { add(i,i+n,1),add(i+n,i,0); if (dp[i]==1)add(k+1,i,1),add(i,k+1,0); else if(dp[i]==ans)add(i+n,k+2,1),add(k+2,i+n,0); }// for (int i=1;i<=te;++i)// cout<<e[i].u<<' '<<e[i].v<<' '<<e[i].cap<<endl; n=k+2;s=k+1,t=k+2; cout<<isap()<<endl; for (int i=1;i<=te;++i) { e[i].flow=0; if ((e[i].u==s&&e[i].v==1)||(e[i].u==1&&e[i].v==nn+1)|| (e[i].u==nn&&e[i].v==k)||(e[i].u==k&&e[i].v==t&&dp[nn]==ans)) e[i].cap=inf; } cout<<isap()<<endl;}

上一篇：用c语言实现进度条

下一篇：【bzoj1257】[CQOI2007]余数之和sum