标签：opt int 赛场 枚举 Split 505
- 赛场上想到了n方枚举n方检验的4方做法，提前想好了实现细节一点点实现，最后一遍过了样例，还是很感动的
- 赛场上超时了，但是交到Codeforces上能以900ms通过
- 正解的确是n^3的，考虑优化枚举，确定1号节点在A后，对于每个1->x->y->1的三元环，要么x在B，y在C，要么x,y都在A，无论如何，x和y都不用被访问第二遍
点击查看代码
#include <bits/stdc++.h>
using namespace std;
bool e[505][505],v[505];
vector<int>c[3];
int p[3],n;
void pr(int p)
{
cout<<c[p][0];
for(int i=1;i<c[p].size();i++)
{
cout<<' '<<c[p][i];
}
cout<<endl;
}
void shuchu()
{
cout<<c[0].size()<<' '<<c[1].size()<<' '<<c[2].size()<<endl;
pr(0);
pr(1);
pr(2);
}
bool check()
{
for(int i=0;i<3;i++)
{
int j=(i+1)%3;
for(int k=0;k<c[i].size();k++)
{
for(int l=0;l<c[j].size();l++)
{
if(!e[c[i][k]][c[j][l]])
{
return false;
}
}
}
}
return true;
}
int getin(int id)
{
for(int i=0;i<3;i++)
{
if(e[id][p[i]])
{
return i;
}
}
}
int getout(int id)
{
for(int i=0;i<3;i++)
{
if(e[p[i]][id])
{
return i;
}
}
}
bool pd()
{
for(int i=1;i<=n;i++)
{
if(i!=p[0]&&i!=p[1]&&i!=p[2])
{
int tot=e[p[0]][i]+e[p[1]][i]+e[p[2]][i];
if(tot==0||tot==3)
{
return false;
}
else if(tot==1)
{
int t=getout(i);
c[(t+1)%3].push_back(i);
}
else
{
int t=getin(i);
c[(t+2)%3].push_back(i);
}
}
}
return check();
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
int opt;
cin>>opt;
if(opt)
{
e[i][j]=1;
}
else
{
e[j][i]=1;
}
}
}
p[0]=1;
for(int i=2;i<=n;i++)
{
if(!v[i])
{
p[1]=i;
for(int j=2;j<=n;j++)
{
if(!v[j])
{
p[2]=j;
if(j!=i)
{
if(e[p[0]][p[1]]&&e[p[1]][p[2]]&&e[p[2]][p[0]])
{
v[i]=v[j]=true;
c[0].clear();c[0].push_back(1);
c[1].clear();c[1].push_back(i);
c[2].clear();c[2].push_back(j);
if(pd())
{
shuchu();
return 0;
}
}
}
}
}
}
}
cout<<0<<" "<<0<<" "<<0<<endl;
return 0;
}
标签：opt,
int,
赛场,
枚举,
Split,
505
From： https://www.cnblogs.com/watersail/p/18403602