BZOJ-1143 [CTSC2008]祭祀

Description
  在遥远的东方,有一个神秘的民族,自称Y族。他们世代居住在水面上,奉龙王为神。每逢重大庆典, Y族都
会在水面上举办盛大的祭祀活动。我们可以把Y族居住地水系看成一个由岔口和河道组成的网络。每条河道连接着
两个岔口,并且水在河道内按照一个固定的方向流动。显然,水系中不会有环流(下图描述一个环流的例子)。
BZOJ-1143 [CTSC2008]祭祀

由于人数众多的原因,Y族的祭祀活动会在多个岔口上同时举行。出于对龙王的尊重,这些祭祀地点的选择必
须非常慎重。准确地说,Y族人认为,如果水流可以从一个祭祀点流到另外一个祭祀点,那么祭祀就会失去它神圣
的意义。族长希望在保持祭祀神圣性的基础上,选择尽可能多的祭祀的地点。
Input
第一行包含两个用空格隔开的整数N、M,分别表示岔口和河道的数目,岔口从1到N编号。
接下来M行,每行包含两个用空格隔开的整数u、v,
描述一条连接岔口u和岔口v的河道,水流方向为自u向v。
N≤100M≤1000
Output
第一行包含一个整数K,表示最多能选取的祭祀点的个数。

Sample Input
4 4

1 2

3 4

3 2

4 2
Sample Output
2


很明显的找一条最长反链。

然后最长反链=最小链覆盖。注意是最小链覆盖而不是最小路径覆盖。

所以我们先跑一次传递闭包即可。

AC代码:

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int inf=0x3f3f3f3f;
const int N=210,M=1e6+10;
int n,m,s,t,h[N],g[N][N];
int head[N],nex[M],to[M],w[M],tot=1;
inline void ade(int a,int b,int c){
	to[++tot]=b; nex[tot]=head[a]; w[tot]=c; head[a]=tot;
}
inline void add(int a,int b,int c){ade(a,b,c);	ade(b,a,0);}
inline int bfs(){
	queue<int> q;	q.push(s);	memset(h,0,sizeof h);	h[s]=1;
	while(q.size()){
		int u=q.front();	q.pop();
		for(int i=head[u];i;i=nex[i]){
			if(w[i]&&!h[to[i]]){
				h[to[i]]=h[u]+1;	q.push(to[i]);
			}
		}
	}
	return h[t];
}
int dfs(int x,int f){
	if(x==t)	return f;	int fl=0;
	for(int i=head[x];i&&f;i=nex[i]){
		if(w[i]&&h[to[i]]==h[x]+1){
			int mi=dfs(to[i],min(f,w[i]));
			w[i]-=mi,w[i^1]+=mi,fl+=mi,f-=mi;
		}
	}
	if(!fl)	h[x]=-1;
	return fl;
}
inline int dinic(){
	int res=0;
	while(bfs())	res+=dfs(s,inf);
	return res;
}
void floyd(){
	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				g[i][j]|=(g[i][k]&g[k][j]);
}
signed main(){
	cin>>n>>m;	t=n*2+1;
	for(int i=1,a,b;i<=m;i++)	cin>>a>>b,g[a][b]=1;
	for(int i=1;i<=n;i++)	add(s,i,1),add(i+n,t,1);
	floyd();
	for(int i=1;i<=n;i++)	for(int j=1;j<=n;j++)	if(g[i][j]!=0)	add(i,j+n,1);
	cout<<n-dinic();
	return 0;
}
BZOJ-1143 [CTSC2008]祭祀BZOJ-1143 [CTSC2008]祭祀 青烟绕指柔! 发布了469 篇原创文章 · 获赞 241 · 访问量 2万+ 私信 关注
上一篇:中国剩余定理


下一篇:P2857 [USACO06FEB]稳定奶牛分配Steady Cow Assignment