Haywire （随机数大法好）

54 阅读 0 评论 36 点赞

我是靠谱客的博主迷路犀牛，最近开发中收集的这篇文章主要介绍Haywire （随机数大法好），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题意：给你n个牛牛，n<=12，每一个牛有三个朋友，他必须和他的伙伴连一条线（线的权值为他俩之间的距离），问怎样排序母牛使得总权值和最小。

思路：首先n=12，所以全排列的话数虽然不大但也不小，正解给了个装压dp我不会，但随机数了一波直接过了。就是我们随机一个序列，初始化为1.到n，然后每次更换其中的两个数使得序列发生变化，然后跑1e6次就可以了。

Farmer John's N cows (4 <= N <= 12, N even) have built a primitive system for communicating between pairs of friendly cows by building wires protected by wrappings made of hay.

Each cow has exactly 3 other friends in the barn, and the cows must arrange themselves to occupy N stalls lined up in a row. A wire of length L requires exactly L units of hay to build, so for example if the cows in stalls 4 and 7 are friends, it would take 3 units of hay to construct a wire to connect them.

Assuming every pair of friends must be connected by a separate wire, please determine the minimum possible amount of hay required to build these wires if the cows order themselves in the best possible way.

输入

* Line 1: The integer N. FJ's cows are conveniently numbered 1..N.
* Lines 2..1+N: Each line contains three space-separated integers in the range 1..N. Line i+1 contains the numeric identifiers of the three friends of cow i. If cow i is a friend of cow j, then j will also be a friend of i.

输出

* Line 1: The minimum total amount of hay required to connect all pairs of friendly cows.

样例输入 Copy

样例输出 Copy

提示

There are 6 cows. Cow 1 is friends with cows 6, 2, and 5, etc.A best ordering of the cows is 6, 5, 1, 4, 2, 3, which requires only 17 units of hay.

[提交][状态]

#include<bits/stdc++.h>
using namespace std;
const int maxx=1e5+12;
#define ll long long
const ll mod=1000000007;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
ll n;
ll pos[13];
int dp[13][13]={0};
const ll inf=1e18+4;
int bian[13][13]={0};
int a[13]={0};
ll f()
{
	ll ans=0;
	for(int i=1;i<=n;i++) pos[a[i]]=i;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=3;j++)
		{
			ans+=abs(pos[dp[a[i]][j]]-i);				
		}		
	}
	return ans;
}
int main()
{
	ll i,j,k,m,s,x,y,t,l,r;
	ll sum=0;
	cin>>n;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=3;j++) 
		{
			dp[i][j]=read();
		}
	}
	if(n==4)
	{
		printf("10n");
		return 0;
	}
	for(i=1;i<=n;i++)
	{
		a[i]=i;
	}
	int cishu=1;
	ll minl=100000000000;
	while(cishu<=1000000)
	{
		//for(i=1;i<=n;i++) printf("%d ",a[i]);
		//printf("n");
		//printf("%lldn",f());
		l=rand()%n+1;
		r=rand()%n+1;
		swap(a[l],a[r]);
		minl=min(minl,f());
		cishu++;
	}
	
	printf("%lldn",minl/2);
	return 0;
}