网络流（拆点）
概述
最大流拆点是指将图中的点进行拆分，拆成一个入点和一个出点，之间的流量设置为出入的流量限制。
三分图匹配
在二分图匹配之中在中间加入了一层图点，直接进行匹配的话会导致中间的点的流量发生问题，所以我们要限制流量。因此我们可以考虑把中间的点拆分为2个点，之间的流量为1即可，建立一个虚拟源点S到第一层点建立流量为1的边，T为最后一层，中间直接连边即可。
#include<iostream>
#include<cstring>
#include<algorithm>
#define inf 0x3f3f3f3f
using namespace std;
const int N=410,M=5e4+10;
int n,F,D,S,T;
int head[N],d[N],cur[N],q[N],idx;
struct Edge{
int next,to,f;
}edge[M];
void add(int a,int b,int c)
{
edge[idx]=(Edge){head[a],b,c},head[a]=idx++;
edge[idx]=(Edge){head[b],a,0},head[b]=idx++;
}
bool bfs()
{
int hh=0,tt=0;
memset(d,-1,sizeof d);
q[0]=S,d[S]=0,cur[S]=head[S];
while(hh<=tt)
{
int t=q[hh++];
for(int i=head[t];~i;i=edge[i].next)
{
int ver=edge[i].to;
if(d[ver]==-1&&edge[i].f)
{
d[ver]=d[t]+1;
cur[ver]=head[ver];
if(ver==T) return true;
q[++tt]=ver;
}
}
}
return false;
}
int find(int u,int limit)
{
if(u==T) return limit;
int flow=0;
for(int i=cur[u];~i&&flow<limit;i=edge[i].next)
{
cur[u]=i;
int ver=edge[i].to;
if(d[ver]==d[u]+1&&edge[i].f)
{
int t=find(ver,min(edge[i].f,limit-flow));
if(!t) d[ver]=-1;
edge[i].f-=t; edge[i^1].f+=t; flow+=t;
}
}
return flow;
}
int dinic()
{
int res=0,flow;
while(bfs())
while(flow=find(S,inf))
res+=flow;
return res;
}
int main()
{
scanf("%d%d%d", &n, &F, &D);
S = 0, T = n * 2 + F + D + 1;
memset(head, -1, sizeof head);
for (int i = 1; i <= F; i ++ ) add(S, n * 2 + i, 1);
for (int i = 1; i <= D; i ++ ) add(n * 2 + F + i, T, 1);
for (int i = 1; i <= n; i ++ )
{
add(i, n + i, 1);
int a, b, t;
scanf("%d%d", &a, &b);
while (a -- )
{
scanf("%d", &t);
add(n * 2 + t, i, 1);
}
while (b -- )
{
scanf("%d", &t);
add(i + n, n * 2 + F + t, 1);
}
}
printf("%d\n", dinic());
return 0;
}最长上升子序列
此处的上升子序列与之前有所不同，这里是求最长子序列的个数问题，因为是求方案我们要去存一下dp状态，所以不太适合使用LIS,直接暴力即可。然后建图的思路是从S到dp[i]==1建一条inf的边，从dp[i]==max到T建一条inf的边，从i到n+i建一条1的边限制流量，最后从n+j到i建一条流量为1的边做一个转移 。
#include<iostream>
#include<cstring>
#include<algorithm>
#define inf 0x3f3f3f3f
using namespace std;
const int N=1<<10,M=3e5+10;
int n,S,T,idx;
int head[N],cur[N],d[N],q[N];
int g[N],w[N];
struct Edge{
int next,to,f;
}edge[M];
void add(int a,int b,int c)
{
edge[idx]=(Edge){head[a],b,c},head[a]=idx++;
edge[idx]=(Edge){head[b],a,0},head[b]=idx++;
}
bool bfs()
{
int hh=0,tt=0;
memset(d,-1,sizeof d);
q[0]=S,d[S]=0,cur[S]=head[S];
while(hh<=tt)
{
int t=q[hh++];
for(int i=head[t];~i;i=edge[i].next)
{
int ver=edge[i].to;
if(d[ver]==-1&&edge[i].f)
{
d[ver]=d[t]+1;
cur[ver]=head[ver];
if(ver==T) return true;
q[++tt]=ver;
}
}
}
return false;
}
int find(int u,int limit)
{
if(u==T) return limit;
int flow=0;
for(int i=cur[u];~i&&flow<limit;i=edge[i].next)
{
cur[u]=i;
int ver=edge[i].to;
if(d[ver]==d[u]+1&&edge[i].f)
{
int t=find(ver,min(edge[i].f,limit-flow));
if(!t) d[ver]=-1;
edge[i].f-=t,edge[i^1].f+=t,flow+=t;
}
}
return flow;
}
int dinic()
{
int res=0,flow;
while(bfs())
while(flow=find(S,inf))
res+=flow;
return res;
}
int main()
{
memset(head,-1,sizeof head);
scanf("%d",&n);
S=0,T=2*n+1;
for(int i=1;i<=n;i++) scanf("%d",&w[i]);
int s=0;
for(int i=1;i<=n;i++){
add(i,n+i,1);
g[i]=1;
for(int j=1;j<i;j++)
if(w[j]<=w[i]) g[i]=max(g[i],g[j]+1);
for(int j=1;j<i;j++)
if(w[j]<=w[i]&&g[j]+1==g[i])
add(n+j,i,1);
s=max(s,g[i]);
if(g[i]==1) add(S,i,1);
}
for(int i=1;i<=n;i++)
if(g[i]==s) add(n+i,T,1);
printf("%d\n",s);
if(s==1) printf("%d\n%d\n",n,n);
else{
int res=dinic();
printf("%d\n",res);
for(int i=0;i<idx;i+=2)
{
int a=edge[i^1].to,b=edge[i].to;
if(a==S&&b==1) edge[i].f=inf;
else if(a==1&&b==n+1) edge[i].f=inf;
else if(a==n&&b==2*n) edge[i].f=inf;
else if(a==2*n&&b==T) edge[i].f=inf;
}
res+=dinic();
printf("%d\n",res);
}
return 0;
}
