BZOJ1562: [NOI2009]变换序列【二分图匹配】

1562: [NOI2009]变换序列

【题目描述】

传送门

【题解】

这题主要是怎么让字典序最小,那么我们可以先处理位置在后的,然后让位置在前的抢掉这个。

代码如下

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=10005;
int n,tim,grl[MAXN],vis[MAXN],OU[MAXN];
struct Edge{
    int tot,lnk[MAXN],son[MAXN<<2],nxt[MAXN<<2];
    void Add(int x,int y){son[++tot]=y;nxt[tot]=lnk[x];lnk[x]=tot;}
}E;
bool Fnd(int x){
    for(int j=E.lnk[x];j;j=E.nxt[j])
    if(vis[E.son[j]]!=tim){
        vis[E.son[j]]=tim;
        if(grl[E.son[j]]==-1||Fnd(grl[E.son[j]])){grl[E.son[j]]=x;return 1;}
    }
    return 0;
}
int main(){
    memset(grl,-1,sizeof(grl));
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        int T,que[10],Top=0;scanf("%d",&T);
        if(i+T<n) que[++Top]=i+T;
        if(i-T>=0) que[++Top]=i-T;
        T=n-T;
        if(i+T<n) que[++Top]=i+T;
        if(i-T>=0) que[++Top]=i-T;
        sort(que+1,que+1+Top);
        for(int j=Top;j;j--) E.Add(i,que[j]);
    }
    int Ans=0;
    for(int i=n-1;i>=0;i--) tim++,Ans+=Fnd(i);
    if(Ans<n) printf("No Answer\n");
    else{
        for(int i=0;i<n;i++) OU[grl[i]]=i;
        for(int i=0;i<n;i++){
            printf("%d",OU[i]);
            if(i==n-1) putchar('\n');else putchar(' ');
        }
    }
    return 0;
}

发表评论

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部