[Luogu 3701] 「伪模板」主席树

<题目链接>

---

#include <algorithm>

#include <cstdio>

#include <cstring>

#include <queue>

using std::min;

using std::queue;

const int MAXN=210,INF=0x3f3f3f3f;

int n,m,S,T,win[5][5]={	{0	,1	,1	,-1	,-1	},

						{-1	,0	,1	,1	,-1	},

						{-1	,-1	,0	,1	,1	},

						{1	,-1	,-1	,0	,1	},

						{1	,1	,-1	,-1	,0	}};

struct Edge

{

	int to,w;

	Edge *nxt,*back;

	Edge(int to=0,int w=0,Edge* nxt=nullptr):to(to),w(w),nxt(nxt),back(nullptr){}

	~Edge(void)

	{

		if(nxt!=nullptr)

			delete nxt;

	}

}*head[MAXN];

void AddEdges(int u,int v,int w)

{

	head[u]=new Edge(v,w,head[u]);

	head[v]=new Edge(u,0,head[v]);

	head[u]->back=head[v];

	head[v]->back=head[u];

}

int Number(char *s)

{

	if(s[0]=='J')

		return 0;

	else if(s[0]=='H')

		return 1;

	else if(s[0]=='W')

		return 2;

	else if(s[0]=='E')

		return 3;

	else if(s[0]=='Y')

		return 4;

}

void InitTree(int *a)

{

	char s[5];

	for(int i=1;i<=n;++i)

	{

		scanf(" %s",s);

		a[i]=Number(s);

		if(a[i]==4)

			++a[0];

	}

}

void Init(void)

{

	static int a[MAXN],b[MAXN];

	T=(n<<1)+1;

	InitTree(a);

	InitTree(b);

	for(int i=1;i<=n;++i)

		head[i]=nullptr;

	for(int i=1,x;i<=n;++i)

	{

		scanf("%d",&x);

		AddEdges(S,i,!a[i] ? x+a[0] : x);

	}

	for(int i=1,x;i<=n;++i)

	{

		scanf("%d",&x);

		AddEdges(i+n,T,!b[i] ? x+b[0] : x);

	}

	for(int i=1;i<=n;++i)

		for(int j=1;j<=n;++j)

			if(win[a[i]][b[j]]==1)

				AddEdges(i,j+n,1);

}

void Destroy(void)

{

	for(int i=S;i^T;++i)

		delete head[i];

}

namespace Procyon

{

	int dis[MAXN];

	Edge *cur[MAXN];

	bool BFS(int S,int T)

	{

		queue<int> q;

		memset(dis,0,sizeof dis);

		q.push(S);

		dis[S]=1;

		while(!q.empty())

		{

			int u=q.front(),v;

			q.pop();

			for(Edge *i=head[u];i!=nullptr;i=i->nxt)

				if(i->w && !dis[v=i->to])

				{

					q.push(v);

					dis[v]=dis[u]+1;

				}

		}

		return dis[T];

	}

	int DFS(int u,int k)

	{

		if(u==T || !k)

			return k;

		int v,f,sum=0;

		for(Edge *&i=cur[u];i!=nullptr;i=i->nxt)

			if(i->w && dis[v=i->to]==dis[u]+1 && (f=DFS(v,min(k,i->w))))

			{

				k-=f;

				sum+=f;

				i->w-=f;

				i->back->w+=f;

			}

		if(!sum)

			dis[u]=1;

		return sum;

	}

	void Dinic(int S,int T)

	{

		int ans=0;

		while(BFS(S,T))

		{

			memcpy(cur,head,sizeof head);

			ans+=DFS(S,INF);

		}

		printf("%d\n",min(m,ans));

	}

}

int main(int argc,char** argv)

{

	scanf("%d %d",&n,&m);

	Init();

	Procyon::Dinic(S,T);

	Destroy();

	return 0;

}