mipt 003

开始作mipt了
大意:
给一个竞赛图(有向图,x和y要么x到y有边,要么y到x有边)。。
求哈密顿回路。。
图很密。。暴力dfs2.00s。。
我直接随机了。。0.02s。。
就是说随机一个序列,然后如果其中有两个相邻的没边的话,
交换一下位置就有边了。。但是可能导致其他的没边。。
但多随机调整几次就OK了。。
#include<cstdio>
#include<utility>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cstdlib>
using namespace std;
int n;const int maxn=200;
bool beat[maxn][maxn]={0};
void init()
{
cin>>n;char c;bool w;scanf("n");
for(int i=0;i<n;i++)
{
for(int j=0;j<i;j++)
{
cin>>c;w=(c==’+’);
beat[i][j]=w;
beat[j][i]=!w;
}
scanf("#n");
}
}
int t;
inline void swap(int&x,int&y)
{t=x;x=y;y=t;}
void print(int A[])
{
for(int i=0;i<n;i++)
cout<<A[i]+1<<" ";
cout<<endl;
exit(0);
}
void solve()
{
int A[maxn];
for(int i=0;i<n;i++)
A[i]=i;
int test=100;
while(test–)
{
random_shuffle(A,A+n);
int ti=100;
while(ti–)
{
bool can=true;
for(int i=0;i<n-1;i++)
if(!beat[A[i]][A[i+1]])
swap(A[i],A[i+1]),can=false;
if(can)
print(A);
}
}
}
int main()
{
srand(199581);
init();
solve();
}

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>