[洛谷 4013]数字梯形问题

题面链接

https://www.luogu.com.cn/problem/P4013

题解

Problem 1

将每个点 \(p\) 拆分成 \(p_x,p_y\) 两个点。连 \(p_x \to p_y\),流量为 \(1\)(只能经过一次),费用为该点的价值的边。

如果 \(p\) 和 \(q\) 相邻,连 \(p_y \to q_x\),流量为 \(1\)(其实如果路径不在点处相交,也不会在边处相交),费用为 \(0\) 的边。

源点向第一行所有入点连流量为 \(1\),费用为 \(0\) 的边。最后一行所有出点向汇点连流量为 \(1\),费用为 \(1\) 的边。

跑最大费用最大流即可。

Problem 2

允许两条路径在点处相交了,那么唯一的不合法情况就是两条路径在边相交了(实质是两条路径同时经过了一条边)。

我们只需对上面的建图方式做些改动就行:\(p_x \to p_y\) 的边的流量和最后一行出点向汇点的流量都直接改成 \(\infty\) 就行。

Problem 3

这一问真正地没任何限制了。

在第二问的基础上,将 \(p_y \to q_x\) 边的流量也改为 \(\infty\) 即可。

#include <cstring>
#include <iostream>
#include <string>
#include <queue>
#define INF 0x3f3f3f3f
using namespace std;
struct edge
{
 int v,w,c,next;
}e[200005];
struct node
{
 int v,e;
}p[2005];
int head[2005],dis[2005],vis[2005],id[55][55],a[55][55];
int n,m,s,t,cnt=1,minc;
void addedge(int u,int v,int w,int c)
{
 e[++cnt].v=v;
 e[cnt].w=w;
 e[cnt].c=c;
 e[cnt].next=head[u];
 head[u]=cnt;
}
bool spfa()
{
 queue<int> q;
 memset(dis,INF,sizeof(dis));
 dis[s]=0,vis[s]=1;
 q.push(s);
 while(!q.empty())
 {
  int u=q.front();
  q.pop();
  vis[u]=0;
  for(int i=head[u];i;i=e[i].next)
   if(e[i].w&&dis[u]-e[i].c<dis[e[i].v])
   {
    dis[e[i].v]=dis[u]-e[i].c;
    p[e[i].v].v=u;
    p[e[i].v].e=i;
    if(!vis[e[i].v])
    {
     vis[e[i].v]=1;
     q.push(e[i].v);
    }
   }
 }
 return dis[t]!=INF;
}
int main()
{
 int tot=0;
 cin>>m>>n;
 for(int i=1;i<=n;i++)
  for(int j=1;j<=m+i-1;j++)
   cin>>a[i][j],id[i][j]=++tot;
 
 //problem 1
 s=2*tot+1,t=2*tot+2;
 memset(head,0,sizeof(head));
 cnt=1,minc=0;
 for(int i=1;i<=m;i++)
  addedge(s,i,1,0),addedge(i,s,0,0);
 for(int i=1;i<=n;i++)
  for(int j=1;j<=m+i-1;j++)
  {
   int u=id[i][j],v1=id[i+1][j],v2=id[i+1][j+1];
   addedge(u,u+tot,1,a[i][j]),addedge(u+tot,u,0,-a[i][j]);
   if(i!=n)addedge(u+tot,v1,1,0),addedge(v1,u+tot,0,0);
   if(i!=n)addedge(u+tot,v2,1,0),addedge(v2,u+tot,0,0);
  }
 for(int i=1;i<=m+n-1;i++)
 {
  int u=id[n][i];
  addedge(u+tot,t,1,0),addedge(t,u+tot,0,0);
 }
 while(spfa())
 {
  int minw=INF;
  for(int i=t;i!=s;i=p[i].v)
   minw=min(minw,e[p[i].e].w);
  for(int i=t;i!=s;i=p[i].v)
  {
   e[p[i].e].w-=minw;
   e[p[i].e^1].w+=minw;
  }
  minc+=minw*dis[t];
 }
 cout<<-minc<<endl;
 
 //problem 2
 s=2*tot+1,t=2*tot+2;
 memset(head,0,sizeof(head));
 cnt=1,minc=0;
 for(int i=1;i<=m;i++)
  addedge(s,i,1,0),addedge(i,s,0,0);
 for(int i=1;i<=n;i++)
  for(int j=1;j<=m+i-1;j++)
  {
   int u=id[i][j],v1=id[i+1][j],v2=id[i+1][j+1];
   addedge(u,u+tot,INF,a[i][j]),addedge(u+tot,u,0,-a[i][j]);
   if(i!=n)addedge(u+tot,v1,1,0),addedge(v1,u+tot,0,0);
   if(i!=n)addedge(u+tot,v2,1,0),addedge(v2,u+tot,0,0);
  }
 for(int i=1;i<=m+n-1;i++)
 {
  int u=id[n][i];
  addedge(u+tot,t,INF,0),addedge(t,u+tot,0,0);
 }
 while(spfa())
 {
  int minw=INF;
  for(int i=t;i!=s;i=p[i].v)
   minw=min(minw,e[p[i].e].w);
  for(int i=t;i!=s;i=p[i].v)
  {
   e[p[i].e].w-=minw;
   e[p[i].e^1].w+=minw;
  }
  minc+=minw*dis[t];
 }
 cout<<-minc<<endl;
 
 //problem 3
 s=2*tot+1,t=2*tot+2;
 memset(head,0,sizeof(head));
 cnt=1,minc=0;
 for(int i=1;i<=m;i++)
  addedge(s,i,1,0),addedge(i,s,0,0);
 for(int i=1;i<=n;i++)
  for(int j=1;j<=m+i-1;j++)
  {
   int u=id[i][j],v1=id[i+1][j],v2=id[i+1][j+1];
   addedge(u,u+tot,INF,a[i][j]),addedge(u+tot,u,0,-a[i][j]);
   if(i!=n)addedge(u+tot,v1,INF,0),addedge(v1,u+tot,0,0);
   if(i!=n)addedge(u+tot,v2,INF,0),addedge(v2,u+tot,0,0);
  }
 for(int i=1;i<=m+n-1;i++)
 {
  int u=id[n][i];
  addedge(u+tot,t,INF,0),addedge(t,u+tot,0,0);
 }
 while(spfa())
 {
  int minw=INF;
  for(int i=t;i!=s;i=p[i].v)
   minw=min(minw,e[p[i].e].w);
  for(int i=t;i!=s;i=p[i].v)
  {
   e[p[i].e].w-=minw;
   e[p[i].e^1].w+=minw;
  }
  minc+=minw*dis[t];
 }
 cout<<-minc<<endl;
 
 return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据