Description

给出 N 个点M 条边的无向图，定向得到有向无环图，使得最长路最短。
N ≤ 15, M ≤ 100

Solution

大家都知道Dilworth定理的其中一个内容：最小路径覆盖=最长反链。
实际上与之相似的是：最长路=最小反链划分数。
这个东西虽然比较显然，但是之前没有接触过的话可能还是比较难想到。
有了这个，直接状压DP就行了。

Code

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define pa pair<int,int>
const int inf=2147483647;
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<<3)+(x<<1)+(ch^48),ch=getchar();return x*f;
}
int n=0,m,to[16],v[16];
bool ok[1<<15];
int f[1<<15];
char s1[3],s2[3];
struct Edge{int x,y;}e[110];
int main()
{m=read();for(int i=1;i<=m;i++){scanf("%s%s",s1,s2);int x=s1[0]-'L'+1,y=s2[0]-'L'+1;if(!v[x])v[x]=++n;if(!v[y])v[y]=++n;e[i].x=v[x],e[i].y=v[y];}for(int S=1;S<(1<<n);S++){ok[S]=true;for(int i=1;i<=m;i++)if((1<<(e[i].x-1))&S&&(1<<(e[i].y-1))&S){ok[S]=false;break;}}f[0]=0;for(int S=1;S<(1<<n);S++){f[S]=inf;for(int T=S;T;T=(T-1)&S)if(ok[T]&&f[S^T]!=inf)f[S]=min(f[S],f[S^T]+1);}printf("%d",f[(1<<n)-1]-2);
}