题解：独占访问2 Exclusive Access 2

题目链接

怎么唯一一篇题解这么抽象，完全看不懂

给定一张无向图，求给这张图定向成 DAG 之后的最长路最短是多少。转化一下变成对 DAG 进行分层，每一层之间的点没有连边，使得层数尽可能少，那么最后的层数就是答案。

那么就求出若干个独立集，让独立集总数尽可能少。这是经典的色数问题，我们使用状压 DP，可以在 \(\mathcal O(3^n)\) 的复杂度下解决。

具体方法是设 \(f_S\) 表示当前选择的点的集合为 \(S\) 最少需要分成几个独立集。转移式子是平凡的，即 \(f_{S} = \min_{T \subseteq S \wedge T \text{是独立集}}~~~~ \{ f_{S \oplus T} \} + 1\)。还需要做的就是预处理出哪些集合状态是独立集，暴力枚举集合，枚举集合中的两两点判断有无连边即可，这部分复杂度是 \(\mathcal O(2^n \times n^2)\)。

至于具体的定向方案，我们只需要给几个独立集每个分配一个层数，然后让层数小的统一指向层数大的即可，于是我们需要知道钦定出来的每个独立集具体包含哪些元素，记一个前驱数组看是由什么状态转移而来即可。

代码实现用了记搜，总复杂度是 \(\mathcal O(n + 2^n \times n^2 + 3^n)\)。

#include<bits/stdc++.h>
#define ld long double
#define ui unsigned int
#define ull unsigned long long
#define int long long
#define eb emplace_back
#define pb pop_back
#define mp make_pair
#define fi first
#define se second
#define pii pair<int,int> 
using namespace std;
 
template<typename T=int> inline T read()
{
	T s=0,w=1; char c=getchar();
	while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
	while(isdigit(c)) s=(s<<1)+(s<<3)+(c^48),c=getchar();
	return s*w;
}
template<typename T=long long> inline void write(T x,char ch)
{
	if(x<0) x=-x,putchar('-');
	static char stk[25]; int top=0;
	do {stk[top++]=x%10+'0',x/=10;} while(x);
	while(top) putchar(stk[--top]);
	putchar(ch);
	return;
}
 
namespace MyTool
{
	static const int Mod=998244353;
	template<typename T> inline void Swp(T &a,T &b) {T t=a;a=b;b=t;}
	template<typename T> inline void cmax(T &a,T b) {a=a>b?a:b;}
	template<typename T> inline void cmin(T &a,T b) {a=a<b?a:b;}
	inline void Madd(int &a,int b) {a=a+b>Mod?a+b-Mod:a+b;}
	inline void Mdel(int &a,int b) {a=a-b<0?a-b+Mod:a-b;}
	inline void Mmul(int &a,int b) {a=1ll*a*b%Mod;}
	inline void Mmod(int &a) {a=(a%Mod+Mod)%Mod;}
	inline int  Cadd(int a,int b)  {return a+b>=Mod?a+b-Mod:a+b;}
	inline int  Cdel(int a,int b)  {return a-b<0?a-b+Mod:a-b;}
	inline int  Cmul(int a,int b)  {return a*b%Mod;}
	inline int  Cmod(int a)  {return (a%Mod+Mod)%Mod;}
	inline int  gcd(int a,int b)   {return b?gcd(b,a%b):a;}
	inline int  qpow(int a,int b)  {int res=1; while(b) {if(b&1) Mmul(res,a); Mmul(a,a); b>>=1;} return res;}
	inline int  qmul(int a,int b)  {int res=0; while(b) {if(b&1) Madd(res,a); Madd(a,a); b>>=1;} return res;}
	template<typename T> inline T power(T x)    {return x*x;}
}
using namespace MyTool;
 
inline void file()
{
	freopen(".in","r",stdin);
	freopen(".out","w",stdout);
	return;
}
 
bool Mbe;

namespace LgxTpre
{
	static const int MAX=16;
	static const int inf=2147483647;
	static const int INF=4557430888798830399;
	static const int mod=1e9+7;
	static const int bas=131;
	
	static const int N=15;
	int n,G[MAX][MAX],d[MAX],k;
	struct edge{char x,y;}e[MAX<<3];
	int all,f[1<<MAX],g[1<<MAX],pre[1<<MAX];
	
	void dfs(int S)
	{
		if(!S) return f[S]=0,void();
		if(~f[S]) return;
		f[S]=INF;
		for(int T=S;T;T=S&(T-1)) if(!g[T])
		{
			dfs(S^T);
			if(f[S^T]+1<f[S]) f[S]=f[S^T]+1,pre[S]=S^T;
		}
		return;
	}
	
	inline void lmy_forever()
	{
		while(scanf("%lld",&n)!=EOF)
		{
			all=0,k=0;
			memset(G,0,sizeof G),memset(f,-1,sizeof f);
			memset(d,0,sizeof d),memset(g,0,sizeof g);
			for(int i=1;i<=n;++i)
			{
				scanf(" %c %c",&e[i].x,&e[i].y);
				all|=1<<(e[i].x-'L'),all|=1<<(e[i].y-'L');
				G[e[i].x-'L'][e[i].y-'L']=G[e[i].y-'L'][e[i].x-'L']=1;
			}
			for(int S=all;S;S=all&(S-1))
				for(int i=0;i<N;++i) if(S>>i&1)
					for(int j=0;j<N;++j) if(S>>j&1)
						if(i!=j&&G[i][j]) 
							g[S]=1;
			dfs(all),write(f[all]-2,'\n');
			while(all)
			{
				for(int i=0;i<N;++i) if(all>>i&1) d[i]=k;
				all=pre[all],++k;
			}
			for(int i=1;i<=n;++i)
			{
				if(d[e[i].x-'L']>d[e[i].y-'L']) Swp(e[i].x,e[i].y);
				putchar(e[i].x),putchar(' '),putchar(e[i].y),putchar('\n');
			}
		}
		return;
	}
}
 
bool Med;
 
signed main()
{
//	file();
	fprintf(stderr,"%.3lf MB\n",(&Med-&Mbe)/1048576.0);
	LgxTpre::lmy_forever();
	cerr<<1e3*clock()/CLOCKS_PER_SEC<<" ms\n";
	return (0-0);
}