标签：floyd，最大流，匈牙利算法
题目
Description
Input
Output
最多可选多少景点
Sample Input 7 6
1 2
2 3
5 4
4 3
3 6
6 7
Sample Output 2
HINT
Source
Ctsc2008 River & ural 1533. Fat Hobbits
分析
在DAG（有向无环图）中，有如下的一些定义和性质：
-
链是点集，这个集合中任意两个元素u,v，要么u能走到v，要么v能走到u。
-
反链也是点集，这个集合中任意两点谁也不能走到谁。
最长反链就是反链中最长的那个
- Dilworth定理：最长反链=最小路径覆盖
关于证明可以参照vfk犇犇的博客 链接
-
最长反链长度=最小链覆盖（用最少的链覆盖所有顶点）
-
对偶定理：最长链长度=最小反链覆盖
那么题目中要求我们求DAG的最小链覆盖，这个就是路径可以相交的最小路径覆盖
将原图做一次floyd传递闭包
所谓传递性，可以这样理解：对于一个节点i，如果j能到i，i能到k，那么j就能到k。求传递闭包，就是把图中所有满足这样传递性的节点都弄出来，计算完成后，我们也就知道任意两个节点之间是否相连。
这题后面操作我使用了比较奇葩的dinic//别问我为什么用网络流，我闲的去写网络流
如果两个点 x, y，满足 x 可以到达 y ，那么就在图中建边（x1,y2）（同样是拆点操作）
只要x可以到达y，就直接连一条边 (x1, y2)，这样就可以“绕过”原图的一些被其他路径占用的点，直接构造新路径
之后n-二分图最大匹配数就是答案
双倍经验题滋磁啊！
code
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
#define inf 0x3f3f3f
using namespace std;
inline ll read()
{
ll f=1,x=0;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;
}
const int maxn=406;
int n,m,T,cnt=1,ans,que[maxn],h[maxn],last[maxn],Map[maxn][maxn];
struct edge{int to,next,v;}e[maxn*maxn];
void insert(int u,int v,int w){
e[++cnt]=(edge){v,last[u],w};last[u]=cnt;
e[++cnt]=(edge){u,last[v],0};last[v]=cnt;
}
void floyd()
{
rep(k,1,n)
rep(i,1,n)
rep(j,1,n)
Map[i][j]|=(Map[i][k]&Map[k][j]);
}
bool bfs()
{
int head=0,tail=1,now;
rep(i,0,T)h[i]=-1;
que[0]=0;h[0]=0;
while(head<tail){
now=que[head++];
reg(now)
if(h[e[i].to]==-1&&e[i].v){
h[e[i].to]=h[now]+1;
que[tail++]=e[i].to;
}
}
return h[T]!=-1;
}
int dfs(int x,int f)
{
if(x==T)return f;
int w,used=0;
reg(x)
if(h[e[i].to]==h[x]+1){
w=dfs(e[i].to,min(e[i].v,f-used));
e[i].v-=w;e[i^1].v+=w;
used+=w;if(used==f)return f;
}
if(!used)h[x]=-1;
return used;
}
void dinic(){while(bfs())ans+=dfs(0,inf);}
void build(){
rep(i,1,n){insert(0,i,1);insert(i+n,T,1);}
rep(i,1,n)
rep(j,1,n)
if(Map[i][j])insert(i,j+n,inf);
}
int main()
{
n=read(),m=read(),T=2*n+1;
rep(i,1,m){
int u=read(),v=read();
Map[u][v]=1;
}
floyd();build();dinic();
cout<<n-ans<<endl;
return 0;
}
