HLPP

#include
using namespace std;
#define N 2010
#define M 200010
#define INF 0x3f3f3f3f
inline int read()
{
	int s=0,f=1;
	char ch=getchar();
	while(ch<'0'||'9'head,to,nxt,val;
int ht[N],ex[N],gap[N];//高度,超额流,gap优化 
void join(int u,int v,int w)
{
	nxt.push_back(head[u]);
	head[u]=to.size();
	to.push_back(v);
	val.push_back(w);
}

bool bfs()
{	
	queueq;
	for(int i=1;i<=n;++i)
	{
		ht[i]=INF;
	} 
	while(!q.empty())
	{
		q.pop();
	}
	q.push(T),ht[T]=0;//汇点跑源点 反向跑所以是i^1 
	while(!q.empty())
	{
		int u=q.front();q.pop();
		for(int i=head[u];i!=-1;i=nxt[i])
		{
			if(val[i^1]&&ht[to[i]]>ht[u]+1)
			{
				ht[to[i]]=ht[u]+1;
				q.push(to[i]);
			}
		}
	}
	return ht[S]!=INF;
}
struct cmp
{
	bool operator()(int a,int b){return ht[a],cmp>q;
bool vis[N];
bool push(int u)
{
	for(int i=head[u];i!=-1;i=nxt[i])
	{
		if(val[i]&&ht[u]==ht[to[i]]+1)
		{
			int tmp=min(val[i],ex[u]);
			ex[u]-=tmp;
			ex[to[i]]+=tmp;
			val[i]-=tmp;
			val[i^1]+=tmp;
			if(to[i]!=S&&to[i]!=T&&!vis[to[i]])
			{
				vis[to[i]]=1;
				q.push(to[i]);
			}
			if(!ex[u]) return 0;
		}
	}
	return 1;
}
void relabel(int u)
{
	ht[u]=INF;
	for(int i=head[u];i!=-1;i=nxt[i])
	{
		if(val[i]) ht[u]=min(ht[u],ht[to[i]]);
	}
	++ht[u];
}
int hlpp()
{
	if(!bfs()) return 0;
	ht[S]=n;
	memset(gap,0,sizeof(gap));
	for(int i=1;i<=n;++i)
	{
		if(ht[i]!=INF) ++gap[ht[i]];
	}
	for(int i=head[S];i!=-1;i=nxt[i])
	{
		if(val[i])
		{
			int tmp=val[i];
			ex[S]-=tmp;
			ex[to[i]]+=tmp;
			val[i]-=tmp;
			val[i^1]+=tmp;
			if(to[i]!=S&&to[i]!=T&&!vis[to[i]])
			{
				vis[to[i]]=1;
				q.push(to[i]);
			}
		}
	}
	while(!q.empty())
	{
		int u=q.top();
		q.pop();vis[u]=0;
		while(push(u))
		{
			if(!--gap[ht[u]])
			{
				for(int i=1;i<=n;++i)
				{
					if(i!=S&&i!=T&&ht[i]>ht[u]&&ht[i]