Bzoj2718_1143 [violet 4]毕业旅行

Posted by yjjr's blog on December 25, 2017

标签: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;
}

本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr