MF+MCMF namespace封装()

MF

namespace MF
{
	typedef long long Cap_Type;
	const int N=1e6+10,M=2e6+10;const Cap_Type INF=4e18;
	int head[N],des[M],nxt[M],cgt=1,s,t,S,dep[N],que[N],H,T,h2[N];bool vis[N];Cap_Type cap[M];
	inline void Clear(){memset(head,0,(S+2)*sizeof(head[0]));cgt=1;S=0;}
	inline void ins(const int &x,const int &y,const Cap_Type &c=1)
	{
		if(!x||!y)return;
		nxt[++cgt]=head[x];des[head[x]=cgt]=y;cap[cgt]=c;
		nxt[++cgt]=head[y];des[head[y]=cgt]=x;cap[cgt]=0;
	}
	inline bool bfs()
	{
		memset(dep,0,(S+2)*sizeof(dep));dep[que[H=T=0]=s]=1;
		while(H<=T){int u=que[H++];for(int i(head[u]);i;i=nxt[i])if(cap[i]&&!dep[des[i]])dep[que[++T]=des[i]]=dep[u]+1;} return dep[t];
	}
	inline Cap_Type dfs(const int &u=s,Cap_Type in=INF)
	{
		if(u==t)return in;Cap_Type out=0;
		for(int &i=h2[u];i;i=nxt[i])
		{
			int v=des[i];if(cap[i]&&dep[v]==dep[u]+1)
			{
				Cap_Type tmp=dfs(v,cap[i]<in?cap[i]:in);
				out+=tmp;cap[i]-=tmp;cap[i^1]+=tmp;if(!(in-=tmp))break;
			}
		}
		return out?out:dep[u]=0;
	}
	inline Cap_Type dinic(){Cap_Type res=0;while(bfs())memcpy(h2,head,(S+2)<<2),res+=dfs();return res;}
}
using MF::ins;using MF::S;using MF::s;using MF::t;using MF::dinic;

MCMF

namespace MCMF
{
	typedef long long Val_Type;typedef long long Cap_Type;
	const Val_Type INF_v=4e18;const Cap_Type INF_c=4e18; 
	const int N=1e6+10,M=2e6+10;int head[N],des[M],nxt[M],cgt=1;Cap_Type cap[M];Val_Type val[M];
	template<typename T> inline T Abs(T x){return x<0?-x:x;} 
	inline void ins(const int &x,const int &y,const int &c,const Val_Type &w)
	{
		nxt[++cgt]=head[x];des[head[x]=cgt]=y;cap[cgt]=c;val[cgt]=w;
		nxt[++cgt]=head[y];des[head[y]=cgt]=x;cap[cgt]=0;val[cgt]=-w;
	}
	int que[20000010],H,T;Val_Type dis[N],mnc;int s,t,S;bool inq[N];
	inline bool spfa()
	{
		for(int i=0;i<=S+2;++i)dis[i]=INF_v;dis[que[H=T=0]=s]=0;
		while(H<=T)
		{
			int u=que[H++];inq[u]=false;for(int i(head[u]);i;i=nxt[i])
				{int v=des[i];if(cap[i]&&dis[v]>dis[u]+val[i]){dis[v]=dis[u]+val[i];if(!inq[v])inq[que[++T]=v]=true;}}
		}
		return dis[t]<INF_v;
	}
	inline Cap_Type dfs(const int &u=s,Cap_Type in=INF_c)
	{
		if(u==t)return in;Cap_Type out=0;inq[u]=true;
		for(int i(head[u]);i;i=nxt[i])
		{
			int v=des[i];if(cap[i]&&!inq[v]&&dis[v]==(dis[u]+val[i]))
			{
				Cap_Type tmp=dfs(v,cap[i]<in?cap[i]:in);mnc+=val[i]*tmp;
				cap[i]-=tmp;cap[i^1]+=tmp;out+=tmp;if(!(in-=tmp))break;
			}
		}
		if(!out)dis[u]=4e18;inq[u]=false;return out;
	}
	inline Cap_Type dinic(){Cap_Type res=0;while(spfa())res+=dfs();return res;}
	inline void Clear(){memset(head,0,(S+2)*sizeof(head[0]));cgt=1;S=0;mnc=0;}
}
using MCMF::ins;using MCMF::s;using MCMF::t;using MCMF::S;using MCMF::dinic;using MCMF::mnc;
————————

MF

namespace MF
{
	typedef long long Cap_Type;
	const int N=1e6+10,M=2e6+10;const Cap_Type INF=4e18;
	int head[N],des[M],nxt[M],cgt=1,s,t,S,dep[N],que[N],H,T,h2[N];bool vis[N];Cap_Type cap[M];
	inline void Clear(){memset(head,0,(S+2)*sizeof(head[0]));cgt=1;S=0;}
	inline void ins(const int &x,const int &y,const Cap_Type &c=1)
	{
		if(!x||!y)return;
		nxt[++cgt]=head[x];des[head[x]=cgt]=y;cap[cgt]=c;
		nxt[++cgt]=head[y];des[head[y]=cgt]=x;cap[cgt]=0;
	}
	inline bool bfs()
	{
		memset(dep,0,(S+2)*sizeof(dep));dep[que[H=T=0]=s]=1;
		while(H<=T){int u=que[H++];for(int i(head[u]);i;i=nxt[i])if(cap[i]&&!dep[des[i]])dep[que[++T]=des[i]]=dep[u]+1;} return dep[t];
	}
	inline Cap_Type dfs(const int &u=s,Cap_Type in=INF)
	{
		if(u==t)return in;Cap_Type out=0;
		for(int &i=h2[u];i;i=nxt[i])
		{
			int v=des[i];if(cap[i]&&dep[v]==dep[u]+1)
			{
				Cap_Type tmp=dfs(v,cap[i]<in?cap[i]:in);
				out+=tmp;cap[i]-=tmp;cap[i^1]+=tmp;if(!(in-=tmp))break;
			}
		}
		return out?out:dep[u]=0;
	}
	inline Cap_Type dinic(){Cap_Type res=0;while(bfs())memcpy(h2,head,(S+2)<<2),res+=dfs();return res;}
}
using MF::ins;using MF::S;using MF::s;using MF::t;using MF::dinic;

MCMF

namespace MCMF
{
	typedef long long Val_Type;typedef long long Cap_Type;
	const Val_Type INF_v=4e18;const Cap_Type INF_c=4e18; 
	const int N=1e6+10,M=2e6+10;int head[N],des[M],nxt[M],cgt=1;Cap_Type cap[M];Val_Type val[M];
	template<typename T> inline T Abs(T x){return x<0?-x:x;} 
	inline void ins(const int &x,const int &y,const int &c,const Val_Type &w)
	{
		nxt[++cgt]=head[x];des[head[x]=cgt]=y;cap[cgt]=c;val[cgt]=w;
		nxt[++cgt]=head[y];des[head[y]=cgt]=x;cap[cgt]=0;val[cgt]=-w;
	}
	int que[20000010],H,T;Val_Type dis[N],mnc;int s,t,S;bool inq[N];
	inline bool spfa()
	{
		for(int i=0;i<=S+2;++i)dis[i]=INF_v;dis[que[H=T=0]=s]=0;
		while(H<=T)
		{
			int u=que[H++];inq[u]=false;for(int i(head[u]);i;i=nxt[i])
				{int v=des[i];if(cap[i]&&dis[v]>dis[u]+val[i]){dis[v]=dis[u]+val[i];if(!inq[v])inq[que[++T]=v]=true;}}
		}
		return dis[t]<INF_v;
	}
	inline Cap_Type dfs(const int &u=s,Cap_Type in=INF_c)
	{
		if(u==t)return in;Cap_Type out=0;inq[u]=true;
		for(int i(head[u]);i;i=nxt[i])
		{
			int v=des[i];if(cap[i]&&!inq[v]&&dis[v]==(dis[u]+val[i]))
			{
				Cap_Type tmp=dfs(v,cap[i]<in?cap[i]:in);mnc+=val[i]*tmp;
				cap[i]-=tmp;cap[i^1]+=tmp;out+=tmp;if(!(in-=tmp))break;
			}
		}
		if(!out)dis[u]=4e18;inq[u]=false;return out;
	}
	inline Cap_Type dinic(){Cap_Type res=0;while(spfa())res+=dfs();return res;}
	inline void Clear(){memset(head,0,(S+2)*sizeof(head[0]));cgt=1;S=0;mnc=0;}
}
using MCMF::ins;using MCMF::s;using MCMF::t;using MCMF::S;using MCMF::dinic;using MCMF::mnc;