网络流24题 1/24 洛谷P2756 飞行员配对方案问题（二分图匹配）
题目思路
二分图匹配的板子题，用dinic求解时，先将源点连所有左部点，汇点连所有右部点，容量全设为1，然后连上所有题目给出的边，这样就建好图了。
跑dinic后最大流就是二分图最大匹配值。
题目还要求输出左部和右部点相连情况，开始在想用一个fa数组记录连接情况，每次dfs更新，但是wa了3、4个点，估计是撤销操作的影响。其实只要判断左部点连向右部的正向边是否为0就好，为零输出两个端点。
网络流24题 2/24 洛谷P3254 圆桌问题（二分图多重匹配）
题目思路
建图基本跟上题一样，只是源点到左部点，右部点到汇点的容量变一下就行了。
题目要求判断是否成立，成立就输出所有*的就餐位置
我们让餐桌作为左部点，单位表示右部点，我们最后只需要判断右部点到汇点边的容量是否都为0，都为0说明说明成立。
然后我们判断就餐位置就跟上题类似，判断右部点连向左部点的边是否为1，为1说明正边被走过，输出左部点。
很坑的是这题是先输入m再输入n，要注意这里。
ac代码
int cnt=1;
struct node
{
int to,next;
int w;
}e[maxn];
int first[maxn];
int n,m,s,t;
int dep[maxn];
int cur[maxn];
int fa[maxn];
int vis[maxn];
void add(int u,int v,int w)
{
e[++cnt].to=v;
e[cnt].w=w;
e[cnt].next=first[u];
first[u]=cnt;
}
inline bool bfs()
{
ms(dep,-1);
dep[s]=0;
memcpy(cur,first,sizeof(first));
queue<int>q;
q.push(s);
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=first[u];i!=-1;i=e[i].next)
{
int to=e[i].to;
int vol=e[i].w;
if(vol>0&&dep[to]==-1)
{
dep[to]=dep[u]+1;
q.push(to);
}
}
}
return dep[t]!=-1;
}
inline int dfs(int u=s,int flow=inf)
{
if(u==t)
return flow;
int last=flow;
for(int i=cur[u];i!=-1&&last;i=e[i].next)
{
cur[u]=i;
int to=e[i].to;
int vol=e[i].w;
if(vol>0&&dep[to]==dep[u]+1)
{
int c=dfs(to,min(vol,last));
fa[u]=to;
last-=c;
e[i].w-=c;
e[i^1].w+=c;
}else
{
fa[u]=-1;
}
}
return flow-last;
}
inline void dinic()
{
while(bfs())
{
dfs();
}
int flag=0;
for(int i=1;i<=n;i++)
{
for(int j=first[i];j!=-1;j=e[j].next)
{
if(e[j].to!=t)continue;
if(e[j].w!=0)
{
flag=1;
}
}
}
if(flag==1)printf("0\n");
else
{
printf("1\n");
for(int i=1;i<=n;i++)
{
for(int j=first[i];j!=-1;j=e[j].next)
{
if(e[j].to==t)continue;
if(e[j].w==1)
{
printf("%d ",e[j].to-n);
}
}
printf("\n");
}
}
}
int main()
{
scanf("%d%d",&n,&m);
s=0,t=m+n+1;
ms(first,-1);
ms(fa,-1);
for(int i=1;i<=n;i++)
{
int w;
scanf("%d",&w);
add(i,t,w);
add(t,i,0);
}
for(int i=1;i<=m;i++)
{
int w;
scanf("%d",&w);
add(i+n,s,0);
add(s,i+n,w);
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
add(i,j+n,0);
add(j+n,i,1);
}
}
dinic();
}
网络流24题 3/24 洛谷P2763 试题库问题（二分图多重匹配）
题目思路
基本思路跟上题一样，但是建图的时候源点连向题目的边容量应该为1
这里没考虑清楚，wa了一发
网络流24题 4/24 洛谷P2764 最小路径覆盖问题（最小路径不相交覆盖）
题目思路
将每个点拆成两份x1，x2，源点连向x1，x2连向汇点，容量均为1。
在根据题目给的边，将端点连起来，容量也为1。
我们对这个图跑最短路，跑出来的最大流就是原图中点的最大匹配值
又因为最小路径覆盖=原图节点数-新图最大匹配数
所以我们就能够的到答案了。
输出路径见代码
ac代码
int cnt=1;
struct node
{
int to,next;
int w;
}e[maxn];
int first[maxn];
int n,m,s,t;
int dep[maxn];
int cur[maxn];
int vis[maxn];
void add(int u,int v,int w)
{
e[++cnt].to=v;
e[cnt].w=w;
e[cnt].next=first[u];
first[u]=cnt;
}
inline bool bfs()
{
ms(dep,-1);
dep[s]=0;
memcpy(cur,first,sizeof(first));
queue<int>q;
q.push(s);
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=first[u];i!=-1;i=e[i].next)
{
int to=e[i].to;
int vol=e[i].w;
if(vol>0&&dep[to]==-1)
{
dep[to]=dep[u]+1;
q.push(to);
}
}
}
return dep[t]!=-1;
}
inline int dfs(int u=s,int flow=inf)
{
if(u==t)
return flow;
int last=flow;
for(int i=cur[u];i!=-1&&last;i=e[i].next)
{
cur[u]=i;
int to=e[i].to;
int vol=e[i].w;
if(vol>0&&dep[to]==dep[u]+1)
{
int c=dfs(to,min(vol,last));
last-=c;
e[i].w-=c;
e[i^1].w+=c;
}
}
return flow-last;
}
inline void dinic()
{
int ans=0;
while(bfs())
{
ans+=dfs();
}
for(int i=1;i<=n;i++)vis[i]=0;
for(int i=1;i<=n;i++)
{
if(vis[i]==1)continue;
int x=i;
int flag=1;
while(1)
{
if(flag==0)break;
flag=0;
printf("%d ",x);
vis[x]=1;
for(int j=first[x];j!=-1;j=e[j].next)
{
int to=e[j].to;
if(e[j].w==0&&vis[to]==0&&to!=s)
{
x=to-n;
flag=1;
break;
}
}
}
printf("\n");
}
printf("%d\n",n-ans);
}
int main()
{
scanf("%d%d",&n,&m);
s=0,t=2*n+1;
ms(first,-1);
for(int i=1;i<=n;i++)
{
add(s,i,1);
add(i,s,0);
add(i+n,t,1);
add(t,i+n,0);
}
for(int i=1;i<=m;i++)
{
int u,v;
scanf("%d%d",&u,&v);
add(u,v+n,1);
add(v+n,u,0);
}
dinic();
}
网络流24题 5/24 洛谷P2765 魔术球问题
题目思路
题目乍一看会有贪心等想法，其实确实也有这种解法，但作为网络流24题中的一个，还是用网络流求解。
因为题目给出要求每个柱子上的点之间和为完全平方数，所以我们可以根据这个条件建边。
题目要求按编号从小到大将球放上柱子，那么我们就枚举球的编号。每次加入后，将球连向源点汇点，再将已经放入的能和它组成完全平方数的点连向它。然后我们每次枚举建完图后都跑一边dinic，当我们得不到值（即该点加入后没有新的匹配生成）时我们将这个点放到新的柱子的第一位。如果柱子数大于题目给的n，那么说明当前值无法放入了，直接退出枚举。我们就得到了需要的值。
这题建议不要用memset来初始化，不然会t。
还有不用当前弧优化能过，用memcpy来进行弧优化的初始化会t，就很神奇。
ac代码
#pragma comment(linker, "/STACK:102400000,102400000")
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <math.h>
#include <string.h>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <utility>
#define pi 3.1415926535898
#define ll long long
#define lson rt<<1
#define rson rt<<1|1h
#define eps 1e-6
#define ms(a,b) memset(a,b,sizeof(a))
#define legal(a,b) a&b
#define print1 printf("111\n")
#define pb(x) push_back(x)
using namespace std;
const int maxn = 2e6+10;
const int inf = 1e9;
const ll llinf =1e18+10;
const ll mod = 1e9+7;
int cnt=1;
struct node
{
int to,next;
int w;
}e[maxn];
int first[maxn];
int n,m,s,t;
int dep[maxn];
int cur[maxn];
int top[maxn];
int sp[maxn];
int now,tot;
void add(int u,int v,int w)
{
e[++cnt].to=v;
e[cnt].w=w;
e[cnt].next=first[u];
first[u]=cnt;
}
inline bool bfs()
{
for(int i=1;i<=100010;i++)dep[i]=-1;
dep[s]=0;
queue<int>q;
q.push(s);
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=first[u];i;i=e[i].next)
{
int to=e[i].to;
int vol=e[i].w;
if(vol>0&&dep[to]==-1)
{
dep[to]=dep[u]+1;
q.push(to);
}
}
}
return dep[t]!=-1;
}
inline int dfs(int u=s,int flow=inf)
{
if(u==t)
return flow;
int last=flow;
for(int i=first[u];i&&last;i=e[i].next)
{
//cur[u]=i;
int to=e[i].to;
int vol=e[i].w;
if(vol>0&&dep[to]==dep[u]+1)
{
int c=dfs(to,min(vol,last));
last-=c;
e[i].w-=c;
e[i^1].w+=c;
}
}
return flow-last;
}
inline int dinic()
{
int ans=0;
while(bfs())
{
ans+=dfs();
}
return ans;
}
int main()
{
int n;
scanf("%d",&n);
s=0;
t=100*1000+1;
tot=0,now=0;
while(tot<=n)
{
++now;
add(s,now*2,1);
add(now*2,s,0);
add(now*2+1,t,1);
add(t,now*2+1,0);
for(int i=sqrt(now);i*i<2*now;i++)
{
if(i*i<=now)continue;
int tem=i*i-now;
add(tem*2,now*2+1,1);
add(now*2+1,tem*2,0);
}
int tem=dinic();
if(tem==0)
top[++tot]=now;
}
printf("%d\n",now-1);
for(int i=1;i<=n;i++)
{
int x=top[i];
while(1)
{
printf("%d ",x);
int flag=0;
for(int j=first[2*x];j;j=e[j].next)
{
int to=e[j].to;
if(to==s)continue;
if(e[j].w==0)
{
x=(to-1)/2;
flag=1;
break;
}
}
if(flag==0)
break;
}
printf("\n");
}
}
总结
这题开始想的时候枚举建图的方式都搞错了，还是要记住二分图建图的模型和它代表的意义，不要跟别普通的图搞混。
尽量少用memset，几组数据都是删前tle，删完之后只有30ms
网络流24题 6/24 洛谷P2766 最长不下降子序列问题
题目思路
题目给出了三问。
因为数据较小，所有第一问可以用n方dp求出答案s。
对于第二问，第三问我们用网络流求解。
首先对于第二问，每个点都只出现在一个序列里面，所以考虑拆点。
我们将点i拆成i_a和i_b两个点，i_a连向i_b并且容量为1。
我们可以根据dp的结果来决定其他的连线
我们首先让dp[i]==1的点i跟s连一条边，容量为1，s流向i。
然后让dp[i]==s的点i跟t连一条边，容量为1，i流向t。
然后对满足i<j,a[i]<a[j],dp[j]=dp[i]+1的i、j两点连边。
这样我们就建好图了，跑完最短路就能得到第二问的答案。
第三问跟第二问类似，只需要把s连向1和n，1内部连线，n内部连线，1和n连向t的边容量全部变成inf就好了。但是这样会出现一个特殊情况，就是s = = 1时，图的结果会是inf，而不是答案1。所以我们需要特判这个情况。
ac代码
#pragma comment(linker, "/STACK:102400000,102400000")
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <math.h>
#include <string.h>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <utility>
#define pi 3.1415926535898
#define ll long long
#define lson rt<<1
#define rson rt<<1|1h
#define eps 1e-6
#define ms(a,b) memset(a,b,sizeof(a))
#define legal(a,b) a&b
#define print1 printf("111\n")
#define pb(x) push_back(x)
using namespace std;
const int maxn = 2e6+10;
const int inf = 0x7f7f7f7f;
const ll llinf =1e18+10;
const ll mod = 1e9+7;
int cnt=1;
struct node
{
int to,next;
int w;
}e[maxn];
int first[maxn];
int n,m,s,t;
int dep[maxn];
int cur[maxn];
int top[maxn];
int dp[maxn];
int a[maxn];
int now,tot;
void add(int u,int v,int w)
{
e[++cnt].to=v;
e[cnt].w=w;
e[cnt].next=first[u];
first[u]=cnt;
}
inline bool bfs()
{
ms(dep,-1);
dep[s]=0;
queue<int>q;
q.push(s);
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=first[u];i;i=e[i].next)
{
int to=e[i].to;
int vol=e[i].w;
if(vol>0&&dep[to]==-1)
{
dep[to]=dep[u]+1;
q.push(to);
}
}
}
return dep[t]!=-1;
}
inline int dfs(int u=s,int flow=inf)
{
if(u==t)
return flow;
int last=flow;
for(int i=first[u];i&&last;i=e[i].next)
{
//cur[u]=i;
int to=e[i].to;
int vol=e[i].w;
if(vol>0&&dep[to]==dep[u]+1)
{
int c=dfs(to,min(vol,last));
last-=c;
e[i].w-=c;
e[i^1].w+=c;
}
}
return flow-last;
}
inline int dinic()
{
int ans=0;
while(bfs())
{
//print1;
ans+=dfs();
}
return ans;
}
int main()
{
scanf("%d",&n);
s=0,t=n*2+1;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
int ss=0;
for(int i=1;i<=n;i++)dp[i]=1;
for(int i=1;i<=n;i++)
{
for(int j=1;j<i;j++)
{
if(a[i]>=a[j])
dp[i]=max(dp[i],dp[j]+1);
}
ss=max(ss,dp[i]);
}
printf("%d\n",ss);
for(int i=1;i<=n;i++)
{
add(i,i+n,1);
add(i+n,i,0);
if(dp[i]==1)
{
add(s,i,1);
add(i,s,0);
}
if(dp[i]==ss)
{
add(i+n,t,1);
add(t,i+n,0);
}
for(int j=i+1;j<=n;j++)
{
if(a[i]<=a[j]&&dp[j]==dp[i]+1)
{
add(i+n,j,1);
add(j,i+n,0);
}
}
}
int ans=dinic();
printf("%d\n",ans);
cnt=1;
if(ss==1)
{
set<int>st;
for(int i=1;i<=n;i++)
st.insert(a[i]);
printf("%d\n",st.size());
}else
{
ms(first,0);
for(int i=1;i<=n;i++)
{
if(dp[i]==1)
{
if(i==1||i==n)
{
add(s,i,inf);
add(i,s,0);
}else
{
add(s,i,1);
add(i,s,0);
}
}
if(dp[i]==ss)
{
if(i==n||i==1)
{
add(i+n,t,inf);
add(t,i+n,0);
}else
{
add(i+n,t,1);
add(t,i+n,0);
}
}
if(i==1||i==n)
{
add(i,i+n,inf);
add(i+n,i,0);
}else
{
add(i,i+n,1);
add(i+n,i,0);
}
}
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
if(a[i]<=a[j]&&dp[j]==dp[i]+1)
{
add(i+n,j,1);
add(j,i+n,0);
}
}
}
int ans=dinic();
printf("%d\n",ans);
}
}