首页 > 代码库 > bzoj1562: [NOI2009]变换序列
bzoj1562: [NOI2009]变换序列
二分图匹配求最小字典序。从后面往前搞就可以了。然后因为我邻接表的写法不能add(i,v)再add(i,d)!!!注意邻接表的顺序
#include<cstdio>#include<cstring>#include<cctype>#include<algorithm>#include<bitset>using namespace std;#define rep(i,s,t) for(int i=s;i<=t;i++)#define dwn(i,s,t) for(int i=s;i>=t;i--)#define clr(x,c) memset(x,c,sizeof(x))#define qwq(x) for(edge *o=head[x];o;o=o->next)int read(){ int x=0;char c=getchar(); while(!isdigit(c)) c=getchar(); while(isdigit(c)) x=x*10+c-‘0‘,c=getchar(); return x;}const int nmax=1e4+5;struct edge{ int to;edge *next;};edge es[nmax<<1],*pt=es,*head[nmax];void add(int u,int v){ pt->to=v;pt->next=head[u];head[u]=pt++;}bitset<nmax>vis;int ans[nmax],match[nmax];bool dfs(int x){ qwq(x) if(!vis[o->to]){ vis[o->to]=1; if(!match[o->to]||dfs(match[o->to])){ ans[x]=o->to;match[o->to]=x; return 1; } } return 0;}int main(){ int n=read(),u,v,d; rep(i,1,n) { u=read();v=i+u-1;d=i-1-u; if(v>=n) v-=n;if(d<0) d+=n; if(v>d) swap(v,d);add(i,d);add(i,v); } dwn(i,n,1){ vis.reset(); if(!dfs(i)) { puts("No Answer");return 0; } } rep(i,1,n-1) printf("%d ",ans[i]);printf("%d",ans[n]); return 0;}
1562: [NOI2009]变换序列
Time Limit: 5 Sec Memory Limit: 64 MBSubmit: 1717 Solved: 871
[Submit][Status][Discuss]
Description
Input
Output
Sample Input
5
1 1 2 2 1
1 1 2 2 1
Sample Output
1 2 4 0 3
HINT
30%的数据中N≤50;
60%的数据中N≤500;
100%的数据中N≤10000。
Source
bzoj1562: [NOI2009]变换序列
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。