就我一个
2025-01-23 19:40:07
发布于:广东
6阅读
0回复
0点赞
#include<bits/stdc++.h>
using namespace std;
const int M=1e4+5;
int n,m,x[M],ans,linkx[M],linky[M];
bool vis[M],exi[2*M];
vector<int> son[M];
int dfs(int k)
{
if(vis[k]==1||exi[k]==0) return 0;
vis[k]=1;
for(int a=0;a<son[k].size();a++)
{
int s=son[k][a];
if(exi[n+s]==0) continue;
if(linky[s]==0||dfs(linky[s])==1)
{
linkx[k]=s;
linky[s]=k;
return 1;
}
}
return 0;
}
int main()
{
scanf("%d",&n);
for(int a=1;a<=n;a++) scanf("%d",&x[a]);
for(int a=1;a<=n;a++)
{
if(a+x[a]<=n) son[a].push_back(a+x[a]);
if(a-x[a]>=1) son[a].push_back(a-x[a]);
if(a+n-x[a]<=n) son[a].push_back(a+n-x[a]);
if(a-n+x[a]>=1) son[a].push_back(a-n+x[a]);
if(son[a].size()!=0) sort(son[a].begin(),son[a].end());
}
for(int a=1;a<=2*n;a++) exi[a]=1;
for(int a=1;a<=n;a++)
{
memset(vis,0,sizeof(vis));
ans+=dfs(a);
}
if(ans<n)
{
printf("No Answer\n");
return 0;
}
for(int a=1;a<=n;a++)
{
for(int b=0;b<son[a].size();b++)
{
int s=son[a][b];
bool check=0;
if(linkx[a]==s) check=1;
else
{
exi[a]=exi[n+s]=0;
linky[linkx[a]]=0;
memset(vis,0,sizeof(vis));
if(dfs(linky[s])==1) check=1;
else linky[linkx[a]]=a;
exi[a]=exi[n+s]=1;
}
if(check==1)
{
exi[a]=exi[n+s]=0;
printf("%d ",s-1);
break;
}
}
}
}
这里空空如也
有帮助,赞一个