「网络流24题」 16. 数字梯形问题

<题目链接>

写在前面

我没坑网络流 24 题！我来填坑了！

这个模型是「最大权不相交路径」，实现方法是最大费用最大流。

我的理解是用「最大流」这个工具去限制选点，用「费用」去描述每个点，最后取「最大费用」。

建图麻烦，跑板子简单。

先膜个人，我大幅参考了这个人的题解。

第一问

点和边都不相交。

套路拆点，每个点拆成 X 和 Y，然后 X 向 Y 连边，容量为 (1)，费用为这个数。这条边流了，就代表选了这个点。

每个点的 Y 向这个点能到的点的 X 连边。

源点向最上层的 X 连边，最下层的 Y 向汇点连边，容量都为 (1)，费用都为 (0)。

第二问

点可以相交，边不行。

这就不用拆点了，直接连。

源点连的边不变。

每个点向能到的点连边，容量为 (1)，费用为这个数。

最下层直接连汇点，容量为 INF（点可以相交，所以最下层的点可能走过很多次），费用为这个数。

第三问

点和边都可以相交。

在第二问的基础上，把点之间的边，容量由 (1) 改为 INF，其余和第二问一样。

每次建一个图跑 MCMF，算出的最大费用就是答案。

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
using std::fill;
using std::max;
using std::min;
using std::queue;
const int MAXN=1200,INF=0x3f3f3f3f;
int m,n,S,T,cnt,a[30][30],num[30][30];
struct Edge
{
	int to,w,f;
	Edge *nxt,*back;
	Edge(int to,int w,int f,Edge* nxt):to(to),w(w),f(f),nxt(nxt),back(nullptr){}
	~Edge(void)
	{
		if(nxt!=nullptr)
			delete nxt;
	}
}*head[MAXN];
void AddEdges(int u,int v,int w,int f)
{
	head[u]=new Edge(v,w,f,head[u]);
	head[v]=new Edge(u,0,-f,head[v]);
	head[u]->back=head[v];
	head[v]->back=head[u];
}
void Init(void)
{
	for(int i=S;i<=T;++i)
		head[i]=nullptr;
}
void Build(int opt)
{
	Init();
	for(int i=1;i<=m;++i)
		AddEdges(S,num[1][i],1,0);
	for(int i=1;i<n;++i)
		for(int j=1;j<m+i;++j)
			if(opt==1)
			{
				AddEdges(num[i][j],num[i][j]+cnt,1,a[i][j]);
				AddEdges(num[i][j]+cnt,num[i+1][j],1,0);
				AddEdges(num[i][j]+cnt,num[i+1][j+1],1,0);
			}
			else
			{
				bool t=opt==2;
				AddEdges(num[i][j],num[i+1][j],t ? 1 : INF,a[i][j]);
				AddEdges(num[i][j],num[i+1][j+1],t ? 1 : INF,a[i][j]);
			}
	for(int i=1;i<m+n;++i)
		if(opt==1)
		{
			AddEdges(num[n][i],num[n][i]+cnt,1,a[n][i]);
			AddEdges(num[n][i]+cnt,T,1,0);
		}
		else
			AddEdges(num[n][i],T,INF,a[n][i]);
}
void Destroy(void)
{
	for(int i=S;i<=T;++i)
		delete head[i];
}
namespace MCMF
{
	bool exist[MAXN];
	int dis[MAXN],pre[MAXN],flow[MAXN];
	Edge *pre_e[MAXN];
	bool SPFA(int S,int T)就是答案
	{
		queue<int> q;
		memset(exist,false,sizeof exist);
		memset(dis,0xc0,sizeof dis);
		memset(pre,0,sizeof pre);
		memset(flow,0x3f,sizeof flow);
		fill(pre_e,pre_e+T+1,nullptr);
		q.push(S);
		exist[S]=1;
		dis[S]=0;
		while(!q.empty())
		{
			int u=q.front();
			q.pop();
			exist[u]=0;
			for(Edge *i=head[u];i!=nullptr;i=i->nxt)
			{
				int v=i->to;
				if(i->w && dis[v]<dis[u]+i->f)
				{
					if(!exist[v])
					{
						q.push(v);
						exist[v]=1;
					}
					dis[v]=dis[u]+i->f;
					pre[v]=u;
					pre_e[v]=i;
					flow[v]=min(flow[u],i->w);
				}
			}
		}
		return dis[T]!=0xc0c0c0c0;
	}
	void Run(int S,int T)
	{
		int ans=0;
		while(SPFA(S,T))
			for(int i=T;i!=S;i=pre[i])
			{
				Edge *t=pre_e[i];
				t->w-=flow[T];
				t->back->w+=flow[T];
				ans+=t->f*flow[T];
			}
		printf("%d
",ans);
	}
}
int main(int argc,char** argv)
{
	scanf("%d %d",&m,&n);
	for(int i=1;i<=n;++i)
		for(int j=1;j<m+i;++j)
		{
			scanf("%d",&a[i][j]);
			num[i][j]=++cnt;
		}
	S=0,T=(cnt<<1)+1;
	for(int i=1;i<=3;++i)
	{
		Build(i);
		MCMF::Run(S,T);
		Destroy();
	}
	return 0;
}

谢谢阅读。