首页 > 代码库 > [BZOJ3532] [Sdoi2014]Lis
[BZOJ3532] [Sdoi2014]Lis
...................................................................................
说起这道题,我的唯一感受是:该死,TM卡常.
这卡常卡的我不要不要的,反正我最后没卡过去.
.....................................................愤怒的分割线..............
这道题的主要思路是求字典序最小的最小割,做完最小割后,按照贪心原则选取,每选中一条边,那么做T->V和U->S的最大流,消除这条边的影响.
代码感觉在什么地方死循环了,一直TLE,但并没有什么发现.
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<ctime> #include<cmath> #include<algorithm> #include<queue> #include<set> #include<map> #include<iomanip> using namespace std; #define ll long long #define db double #define up(i,j,n) for(int i=j;i<=n;i++) #define pii pair<int,int> #define uint unsigned int #define FILE "dealing" #define eps 1e-4 int read(){ int x=0,f=1,ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=(x<<1)+(x<<3)+ch-‘0‘;ch=getchar();} return x*f; } template<class T> bool cmax(T& a,T b){return a<b?a=b,true:false;} template<class T> bool cmin(T& a,T b){return a>b?a=b,true:false;} const int maxn=100550,limit=50100,inf=(int)(2e9),mod=(int)1e9+7; int n; int a[maxn],b[maxn],c[maxn]; namespace dinic{ struct node{ int y,next,rev;int flow; }e[maxn<<1];int len,linkk[maxn]; void insert(int x,int y,int flow){ e[++len].y=y; e[len].next=linkk[x]; linkk[x]=len; e[len].flow=flow; e[len].rev=len+1; e[++len].y=x; e[len].next=linkk[y]; linkk[y]=len; e[len].flow=0; e[len].rev=len-1; } int S,T,SS,TT,q[maxn],d[maxn],head,tail; bool makelevel(){ head=tail=0; up(i,0,n*2+2)d[i]=-1; d[S]=0;q[++tail]=S; while(++head<=tail){ int x=q[head]; for(int i=linkk[x];i;i=e[i].next) if(d[e[i].y]==-1&&e[i].flow)d[e[i].y]=d[x]+1,q[++tail]=e[i].y; } return d[T]!=-1; } int makeflow(int x,int flow){ if(x==T||!flow)return flow; int maxflow=0,dis; for(int i=linkk[x];i&&maxflow<flow;i=e[i].next){ if(e[i].flow&&d[e[i].y]==d[x]+1) if(dis=makeflow(e[i].y,min(e[i].flow,flow-maxflow))){ e[i].flow-=dis; e[e[i].rev].flow+=dis; maxflow+=dis; } } if(!maxflow)d[x]=-1; return maxflow; } int dinic(){ int ans=0,d; while(makelevel()) while(d=makeflow(S,inf)) ans+=d; return ans; } int f[maxn],Max; pii k[maxn]; void prepare(){ up(i,0,n*2+2)linkk[i]=f[i]=0; len=0; } void makeedge(){ prepare(); Max=0;SS=S=n*2+1,TT=T=S+1; up(i,1,n)insert(i*2-1,i*2,b[i]); up(i,1,n)up(j,0,i-1)if(a[i]>a[j])cmax(f[i],f[j]+1); up(i,1,n)up(j,i+1,n)if(a[j]>a[i]&&f[j]==f[i]+1)insert(i*2,j*2-1,inf); up(i,1,n)cmax(Max,f[i]); up(i,1,n){ if(Max==f[i])insert(i*2,T,inf); if(f[i]==1)insert(S,i*2-1,inf); } } int po[maxn],cnt=0; void solve(){ up(i,1,n)k[i].first=c[i],k[i].second=i; sort(k+1,k+n+1);cnt=0; int ans=dinic(); up(i,1,n){ int x=k[i].second; S=x*2-1,T=x*2; if(!makelevel()){ po[++cnt]=x; S=TT,T=x*2; dinic(); S=x*2-1,T=SS; dinic(); e[x*2].flow=0; } } printf("%d %d\n",ans,cnt); sort(po+1,po+cnt+1); up(i,1,cnt)printf("%d%c",po[i],i==cnt?‘\n‘:‘ ‘); } }; int main(){ freopen(FILE".in","r",stdin); freopen(FILE".out","w",stdout); int T; scanf("%d",&T); while(T--){ scanf("%d",&n); up(i,1,n)scanf("%d",&a[i]); up(i,1,n)scanf("%d",&b[i]); up(i,1,n)scanf("%d",&c[i]); dinic::makeedge(); dinic::solve(); } //cout<<clock()<<endl; return 0; }
[BZOJ3532] [Sdoi2014]Lis
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。