C++11(clang++ 3.9) 解法, 执行用时: 288ms, 内存消耗: 1132K, 提交时间: 2018-10-02 13:07:26

#include<bits/stdc++.h>
using namespace std;
int b[15][15],n,m,i,j,k,l,d[32768],f[32768],g[32768],o[32768],a[32768];
int A(int x)
{
    if(x<0)return -x;
    return x;
}
int main()
{
    scanf("%d",&n);
    for(i=0;i<n*(n-1)*2;i++)
    {
        scanf("%d%d",&j,&k);
        if(j&&k)b[j-1][k-1]++;
    }
    for(i=1;i<n;i++)o[1<<i]=i;
    for(i=1;i<1<<n;i++)for(d[i]=d[i^(i&-i)],j=0;j<n;j++)if((i^(i&-i))>>j&1)d[i]+=A(b[j][o[i&-i]]-b[o[i&-i]][j]);
    memset(f,127,sizeof(f));
    for(f[0]=i=0;i<1<<n;i++)
    {
        for(j=m=(1<<n)-1^i,k=0;j;j=j-1&m)a[k++]=j;
        reverse(a,a+k);
        for(j=0;j<k;j++)
        {
            for(g[a[j]]=g[a[j]^(a[j]&-a[j])],l=0;l<n;l++)if(i>>l&1)g[a[j]]+=b[l][o[a[j]&-a[j]]];
            f[i^a[j]]=min(f[i^a[j]],f[i]+g[a[j]]+d[a[j]]);
        }
    }
    cout<<f[(1<<n)-1]<<endl;
    return 0;
}

C++14(g++5.4) 解法, 执行用时: 473ms, 内存消耗: 988K, 提交时间: 2018-10-02 20:18:22

#include<bits/stdc++.h>
using namespace std;
int b[15][15],n,m,i,j,k,l,d[32768],f[32768],g[32768],o[32768],a[32768];
int A(int x) {
	if(x<0)return -x;
	return x;
}
int main() {
	scanf("%d",&n);
	for(i=0; i<n*(n-1)*2; i++) 
	{
		scanf("%d%d",&j,&k);
			b[j-1][k-1]++;
	}
	for(i=1; i<n; i++)
		o[1<<i]=i;
		
	for(i=1; i<1<<n; i++)
		for(d[i]=d[i^(i&-i)], j=0; j<n; j++)
			if((i^(i&-i))>>j&1)
				d[i]+=A(b[j][o[i&-i]]-b[o[i&-i]][j]);
				
	memset(f,127,sizeof(f));
	
	for(f[0]=i=0; i<1<<n; i++) 
	{
		for(j=m=(1<<n)-1^i,k=0; j; j=j-1&m)
			a[k++]=j;
		reverse(a,a+k);
		for(j=0; j<k; j++) 
		{
			for(g[a[j]]=g[a[j]^(a[j]&-a[j])],l=0; l<n; l++)
				if(i>>l&1)g[a[j]]+=b[l][o[a[j]&-a[j]]];
				
			f[i^a[j]]=min(f[i^a[j]],f[i]+g[a[j]]+d[a[j]]);
		}
	}
	
	cout<<f[(1<<n)-1]<<endl;
	return 0;
}