2018年长沙理工大学第十三届程序设计竞赛 K. zzq的离散数学教室2（dilworth定理+有向图可相交路径覆盖 dinic版）

题目

在这个题目中，集合中有n个元素，编号从1到n。它们之间共有m对偏序关系，每一对偏序关系的表示形式为以空格分开的两个编号：x y。含义是x和y之间有关系≤。(这里的≤不是传统意义上的小于等于，可以理解为从y到x的一条有向边)，记做：x≤y。同时这些关系也具有传递性，例如，如果x≤y并且y≤z，那么可以得到x≤z。数据保证不会出现同时有x≤y,y≤z,z≤x的情况。

现在我们的问题是，要你从n个元素里尽可能多的选出一些元素，使得这些元素之间不满足偏序关系。（即这些点中，任意两点都不存在偏序关系）.问你最多能选几个元素。 

T组样例，n<=1e5，sumn<=3e5，m<=2n

思路来源

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=45181859

题解

dilworth定理，最长反链=最小链覆盖，

在有向图中，反链即为没有上下游关系的两个点

偏序最大独立集=有向图最小链覆盖，可相交

dinic建图即可，传统建图方法先求传递闭包然后最大匹配，

但是n=1e5这样边开不下

于是，考虑这样一种dinic建图方法，

1. 将i拆成i和i+n两个点，

2. 将原来的有向边x->y，看做是x->y+n

3. 超级源点s->i

4. (i+n)->超级汇点e

5. 对于不直接相邻，也就是上下游关系即可连边的条件，额外建边(i+n)->i

左侧s->i可以看成是选了一个起点，x->y+n如果不相交的话就是选了一个终点，

y+n->y相当于允许退回去，不把y当终点，后面还可以选其他点当终点

最终y+n->e认为是选了一个终点

这个退回去重选的边的权值，只要大于最大流即可，这里置INF，

x->y+n的边的权值，因为也要过重选的流量，所以也置INF

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<map> 
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
const int maxn=2e5+10;
const int maxm=2e6+10;
int level[maxn];
int head[maxn],cnt;
int t,n,m;
int ss,ee;
struct edge{int v,nex;ll w;}e[maxm];
void init(int n)
{
	cnt=0;
    for(int i=1;i<=n;++i){
        head[i]=-1;
    }
}
void add(int u,int v,ll w)
{
	e[cnt].v=v;
	e[cnt].w=w;
	e[cnt].nex=head[u];
	head[u]=cnt++;
}
void add2(int u,int v,ll w,bool op)//是否为有向图 
{
	add(u,v,w);
	add(v,u,op?0:w);
}
bool bfs(int s,int t)
{
	queue<int>q;
	memset(level,0,sizeof level);
	level[s]=1;
	q.push(s);
	while(!q.empty())
	{
		int x=q.front();
		q.pop();
		if(x==t)return 1;
		for(int u=head[x];~u;u=e[u].nex)
		{
			int v=e[u].v;ll w=e[u].w;
			if(!level[v]&&w)
			{
				level[v]=level[x]+1;
				q.push(v);
			}
		}
	}
	return 0;
}
ll dfs(int u,ll maxf,int t)
{
	if(u==t)return maxf;
	ll ret=0;
	for(int i=head[u];~i;i=e[i].nex)
	{
		int v=e[i].v;ll w=e[i].w;
		if(level[u]+1==level[v]&&w)
		{
			ll MIN=min(maxf-ret,w);
			w=dfs(v,MIN,t);
			e[i].w-=w;
			e[i^1].w+=w;
			ret+=w;
			if(ret==maxf)break;
		}
	}
	if(!ret)level[u]=-1;//优化,防止重搜,说明u这一路不可能有流量了 
	return ret;
}
ll Dinic(int s,int t)
{
	ll ans=0;
	while(bfs(s,t))
	ans+=dfs(s,INF,t);
	return ans;
}
int main()
{ 
    scanf("%d",&t);
    //n个点 m条边 
    while(t--)
    {
    	scanf("%d%d",&n,&m);
    	init(2*n+2);
        ss=2*n+1,ee=2*n+2;
    	for(int j=0;j<m;++j) 
    	{
    		int u,v;
    		scanf("%d%d",&u,&v);
    		add2(u,v+n,INF,1);
    	}
        for(int j=1;j<=n;++j)
        {
            add2(ss,j,1,1);
            add2(j+n,j,INF,1);
            add2(j+n,ee,1,1);
        }
    	ll ans=Dinic(ss,ee);
    	printf("%lld\n",n-ans);
    }
	return 0;
}