费用流2
网格图
费用流的网格图一般都是找路线，可以解决很多dp解决不了的问题，同时也可以解决数字三角形的变态魔改问题，其中最重要的是拆点限流增边。
acwing2191:
梯形的第一行有 m 个数字。（相当于数字三角形第n层开始）
从梯形的顶部的 m 个数字开始，在每个数字处可以沿左下或右下方向移动，形成一条从梯形的顶至底的路径。
规则 1：从梯形的顶至底的 m 条路径互不相交。
规则 2：从梯形的顶至底的 m 条路径仅在数字结点处相交。
规则 3：从梯形的顶至底的 m 条路径允许在数字结点相交或边相交。
解：我们首先要把点上的权值换为边上的权值同时限流为1；对于规则一我们秩序在点的出点和另一个点的入点做一个容量为1费用为0的限制即可；对于规则二为我们只要把入点到出点的流量增宽即可；规则三我们把点到点的流量改为inf。接下来每一次求最大流最大费用即可。
#include<iostream>
#include<cstring>
#include<algorithm>
#define inf 0x3f3f3f3f
using namespace std;
const int N = 3e3,M = 1e4;
int head[N],idx,st[N];
int incf[N],q[N],pre[N],d[N];
int n,m,S,T;
int id[40][40],cost[40][40];
struct Edge{
int next,to,f,w;
}edge[M];
void add(int a,int b,int c,int d)
{
edge[idx]=(Edge){head[a],b,c,d},head[a]=idx++;
edge[idx]=(Edge){head[b],a,0,-d},head[b]=idx++;
}
bool spfa()
{
int hh=0,tt=1;
memset(st,false,sizeof st);
memset(d,0xcf,sizeof d);
memset(incf,0,sizeof incf);
q[0]=S,d[S]=0,incf[S]=inf;
while(hh!=tt)
{
int t=q[hh++];
if(hh==N) hh=0;
st[t]=false;
for(int i=head[t];~i;i=edge[i].next)
{
int ver=edge[i].to;
if(edge[i].f&&d[ver]<d[t]+edge[i].w)
{
d[ver]=d[t]+edge[i].w;
pre[ver]=i;
incf[ver]=min(edge[i].f,incf[t]);
if(!st[ver])
{
q[tt++]=ver;
if(tt==N) tt=0;
st[ver]=true;
}
}
}
}
return incf[T]>0;
}
int EK()
{
int cost=0;
while(spfa())
{
int t=incf[T];
cost+=t*d[T];
for(int i=T;i!=S;i=edge[pre[i]^1].to)
{
edge[pre[i]].f-=t;
edge[pre[i]^1].f+=t;
}
}
return cost;
}
int main()
{
int cnt=0;
scanf("%d%d",&m,&n);
S=++cnt; T=++cnt;
for(int i=1;i<=n;i++)
for(int j=1;j<=m+i-1;j++)
{
scanf("%d",&cost[i][j]);
id[i][j]=++cnt;
}
//规则1
memset(head,-1,sizeof head); idx=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m+i-1;j++)
{
add(id[i][j]*2,id[i][j]*2+1,1,cost[i][j]);
if(i==1) add(S,id[i][j]*2,1,0);
if(i==n) add(id[i][j]*2+1,T,1,0);
if(i<n){
add(id[i][j]*2+1,id[i+1][j]*2,1,0);
add(id[i][j]*2+1,id[i+1][j+1]*2,1,0);
}
}
printf("%d\n",EK());
//规则2
memset(head,-1,sizeof head); idx=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m+i-1;j++)
{
add(id[i][j]*2,id[i][j]*2+1,inf,cost[i][j]);
if(i==1) add(S,id[i][j]*2,1,0);
if(i==n) add(id[i][j]*2+1,T,inf,0);
if(i<n){
add(id[i][j]*2+1,id[i+1][j]*2,1,0);
add(id[i][j]*2+1,id[i+1][j+1]*2,1,0);
}
}
printf("%d\n",EK());
//规则3
memset(head,-1,sizeof head); idx=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m+i-1;j++)
{
add(id[i][j]*2,id[i][j]*2+1,inf,cost[i][j]);
if(i==1) add(S,id[i][j]*2,1,0);
if(i==n) add(id[i][j]*2+1,T,inf,0);
if(i<n){
add(id[i][j]*2+1,id[i+1][j]*2,inf,0);
add(id[i][j]*2+1,id[i+1][j+1]*2,inf,0);
}
}
printf("%d\n",EK());
return 0;
}拆点
acwing969 这道题是对于拆点的涉及，我们首先把毛巾拆为使用和需求，对于快洗和慢洗我们从使用的毛巾向需求的毛巾连一条流量为inf费用为所需费用的边即可，同时考虑继承问题，我们需要从使用的毛巾向第二天使用的毛巾连一条流量为inf，费用为0的边；新购买的毛巾我们直接从源点向所需毛巾连一条流量为inf费用为所需费用的边，接下来我们求最大流，限制在于到T的边上。
#include<iostream>
#include<cstring>
#include<algorithm>
#define inf 0x3f3f3f3f
using namespace std;
const int N = 2e3+10,M = 1e4+10;
int n,m,S,T;
int p,x,xp,y,yp;
int head[N],idx;
int d[N],q[N],incf[N],pre[N];
bool st[N];
struct Edge{
int next,to,f,w;
}edge[M];
void add(int a,int b,int c,int d)
{
edge[idx]=(Edge){head[a],b,c,d},head[a]=idx++;
edge[idx]=(Edge){head[b],a,0,-d},head[b]=idx++;
}
bool spfa()
{
int hh=0,tt=1;
memset(st,false,sizeof st);
memset(d,0x3f,sizeof d);
memset(incf,0,sizeof incf);
q[0]=S,incf[S]=inf,d[S]=0;
while(hh!=tt)
{
int t=q[hh++];
if(hh==N) hh=0;
st[t]=false;
for(int i=head[t];~i;i=edge[i].next)
{
int ver=edge[i].to;
if(edge[i].f&&d[ver]>d[t]+edge[i].w)
{
d[ver]=d[t]+edge[i].w;
incf[ver]=min(incf[t],edge[i].f);
pre[ver]=i;
if(!st[ver])
{
q[tt++]=ver;
if(tt==N) tt=0;
st[ver]=true;
}
}
}
}
return incf[T]>0;
}
int EK()
{
int cost=0;
while(spfa())
{
int t=incf[T];
cost+=t*d[T];
for(int i=T;i!=S;i=edge[pre[i]^1].to)
{
edge[pre[i]].f-=t;
edge[pre[i]^1].f+=t;
}
}
return cost;
}
int main()
{
memset(head,-1,sizeof head);
scanf("%d%d%d%d%d%d",&n,&p,&x,&xp,&y,&yp);
S=0,T=2*n+1;
for(int i=1;i<=n;i++)
{
int r; scanf("%d",&r);
add(S,i,r,0);
add(n+i,T,r,0);
add(S,n+i,inf,p);
if(i<n) add(i,i+1,inf,0);
if(i+x<=n) add(i,i+n,inf,xp);
if(i+y<=n) add(i,i+n,inf,yp);
}
printf("%d\n",EK());
return 0;
}
