二分图最小字典序匹配
倒过来dfs匈牙利就行了
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 |
// <1562.cpp> - Fri Sep 23 08:10:53 2016 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef long long lol; int gi(){ int res=0,fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); return fh*res; } const int MAXN=20010; const int MAXM=80010; const int INF=1e9; int bt=1,b[MAXN],next[MAXM],to[MAXM]; inline void add(int x,int y){ next[++bt]=b[x];b[x]=bt;to[bt]=y; next[++bt]=b[y];b[y]=bt;to[bt]=x; } int match[MAXN]; bool in[MAXN]; bool dfs(int x){ if(in[x])return 0; in[x]=1; for(int i=b[x];i;i=next[i]) if(!match[to[i]]||dfs(match[to[i]])){ match[x]=to[i]; match[to[i]]=x; in[x]=0; return 1; } in[x]=0; return 0; } int main(){ int n=gi(); for(int i=1;i<=n;i++){ int d=gi(); int x=(i+d-1)%n+1,y=(i-d+n-1)%n+1; if(x>y)swap(x,y); add(i,n+y); add(i,n+x); } int ans=0; for(int i=n;i;i--)if(!match[i]&&dfs(i))ans++; if(ans!=n){printf("No Answer");return 0;} for(int i=1;i<n;i++)printf("%d ",match[i]-n-1); printf("%d",match[n]-n-1); return 0; } |
说点什么