题目：BZOJ4160.
题目大意：给定一张$n$个点$m$条边无向图，要求给每条边定向，求定向后有向图上的最长路最短是多少.
$1\le n\le 15,1\le m\le 100$.

首先，最短的最长路并不好算，考虑利用Dilworth定理，将问题转化为求最小的最小反链划分.

然后设$dp[S]$表示点集$S$最少需要被划分为几个反链，若$S$内的点都没有直接连通则$dp[S]=1$，否则枚举子集来转移.

时间复杂度$O(2^n{n}^2+3^n)$.

代码如下：

#include<bits/stdc++.h>
using namespace std;#define Abigail inline void
typedef long long LL;const int N=15,M=100,C=26,INF=(1<<30)-1;int id[C+9];
int n,m,e[N+9][N+9];
int dp[(1<<N)+9];Abigail into(){scanf("%d",&m);for (int i=1;i<=m;++i){char s[2][2];scanf("%s%s",s[0],s[1]);int x=s[0][0]-'A',y=s[1][0]-'A';if (!id[x]) id[x]=++n;if (!id[y]) id[y]=++n;e[id[x]-1][id[y]-1]=1;}
}Abigail work(){for (int g0=1;g0<1<<n;++g0){dp[g0]=1;for (int i=0;i<n;++i)for (int j=0;j<n;++j)if (g0>>i&1&&g0>>j&1&&e[i][j]) dp[g0]=INF;for (int g1=(g0-1)&g0;g1;g1=(g1-1)&g0) dp[g0]=min(dp[g0],dp[g1]+dp[g0^g1]);}
}Abigail outo(){printf("%d\n",dp[(1<<n)-1]-2);
}int main(){into();work();outo();return 0;
}