前言
网络流大法好
只刷了14道题目，剩下的真的做不动啦。
1.飞行员匹配问题
传送门
本题为二分图匹配问题，可以用网络流解决，也可以用匈牙利算法解决。
这题是一道SPJ，方案不唯一，样例好长时间不过，我以为我错了。。。
#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
#define il inline
using namespace std;
const int inf=;
const int maxm=+;
int head[maxm],to[maxm*],cap[maxm*],net[maxm*];
int cnt=;
il void add(int x,int y,int c){cnt++,to[cnt]=y,cap[cnt]=c,net[cnt]=head[x],head[x]=cnt;}
int flow[maxm],pre[maxm],id[maxm],match;
queue <int> dl;
il int BFS(int s,int t)
{
while(!dl.empty()) dl.pop();
memset(pre,-,sizeof(pre));
pre[s]=,flow[s]=inf;
dl.push(s);
while(!dl.empty())
{
int x=dl.front();
dl.pop();
if(x==t) break;
for(int i=head[x];i;i=net[i])
if(to[i]!=s&&cap[i]>&&pre[to[i]]==-)
{
pre[to[i]]=x,id[to[i]]=i;
flow[to[i]]=min(flow[x],cap[i]);
dl.push(to[i]);
}
}
if(pre[t]==-) return -;
else return flow[t];
}
il void change_cap(int s,int t,int x)
{
int now=t,last,sum=;
while(now!=s)
{
cap[id[now]]-=x;
cap[id[now]^]+=x;
now=pre[now];
//if((sum&1)==0) match[now]=last;
//else last=now;
//sum++;
}
}
il int maxflow(int s,int t)
{
int max_flow=;
int d=;
while((d=(BFS(s,t)))!=-)
{
change_cap(s,t,d);
max_flow+=d;
}
return max_flow;
}
int main()
{
int n,m,s,t;
scanf("%d%d",&m,&n);
s=,t=n+;
int s1=,s2=;
while()
{
scanf("%d%d",&s1,&s2);
if(s1==-&&s2==-) break;
add(s1,s2,inf),add(s2,s1,);
}
for(int i=;i<=m;i++) add(s,i,),add(i,s,);
for(int i=m+;i<=n;i++) add(i,t,),add(t,i,);
printf("%d\n",maxflow(s,t));
for(int i=;i<=cnt;i+=)
{
s1=to[i],s2=to[i^];
if(s1==s||s1==t||s2==s||s2==t) continue;
if(cap[i^]) printf("%d %d\n",s2,s1);
}
return ;
}
2.软件补丁问题
传送门
神TM网络流。
SPFA+状压轻松水过
#include <cstdio>
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
bool vis[<<];
int inf;
int ok1[],ok2[],help[],cas[],time[],dis[<<];
queue <int> dl;
int n,m;
char s[];
int spfa()
{
memset(dis,/,sizeof(dis));
dis[(<<n)-]=;
vis[(<<n)-]=;
inf=dis[];
dl.push((<<n)-);
while(!dl.empty())
{
int x=dl.front();
dl.pop();
vis[x]=;
for(int i=;i<=m;i++)
{
bool f1=((ok1[i]&x)==ok1[i]),f2=((ok2[i]&x)==);
if(!f1||!f2) continue;
int to=x&(help[i]);
to|=cas[i];
if(dis[x]+time[i]<dis[to])
{
dis[to]=dis[x]+time[i];
if(vis[to]) continue;
vis[to]=,dl.push(to);
}
}
}
return dis[]==inf?:dis[];
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++)
{
scanf("%d %s",&time[i],s);
for(int j=;j<strlen(s);j++)
{
if(s[j]=='+') ok1[i]|=(<<j);
if(s[j]=='-') ok2[i]|=(<<j);
}
scanf("%s",s);
int l=,r=;
for(int j=;j<strlen(s);j++)
{
if(s[j]=='-') l+=(<<j);
if(s[j]=='+') r+=(<<j);
}
help[i]=~l,cas[i]=r;
}
//cout<<ok1[1]<<" "<<ok2[1]<<endl;
printf("%d\n",spfa());
return ;
}
3.负载平衡问题
传送门
要不是这标签，打死我也不想最小费用最大流。
网络流之精髓，在于建模。
建模分析：
首先，我们先计算出平均的货物数量。
虚拟出一个源点和一个汇点。
将一个仓库拆成两个节点，供应节点X以及需求节点Y
从一个仓库的供应节点向相邻仓库的需求节点建立容量无限大，费用为1的边，模拟仓库之间的搬运。
从一个仓库的供应节点向相邻仓库的供应节点建立容量无限大，费用为1的边，模拟仓库之间的停留搬运
若一个仓库有盈余，则从源点向此仓库的供应节点建立容量为盈余，费用为0的边。
若一个仓库有亏损，则从此仓库的需求节点向汇点连一条容量为亏损，费用为0的边
在此网络上跑网络流，亏损和盈余之间会互补，此时求出的费用即为最小费用。
震惊的是：此题EK居然和Dinic一样快
#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
#define il inline
using namespace std;
const int inf=;
const int maxm=;
int head[maxm],to[maxm*],cap[maxm*],net[maxm*],cost[maxm*];
int val[maxm];
int cnt=;
il void add(int x,int y,int c,int z){cnt++,to[cnt]=y,cost[cnt]=z,cap[cnt]=c,net[cnt]=head[x],head[x]=cnt;}
int flow[maxm],pre[maxm],id[maxm],dis[maxm],max_flow,min_cost;
bool vis[maxm];
queue <int> dl;
il bool BFS(int s,int t)
{
while(!dl.empty()) dl.pop();
memset(pre,-,sizeof(pre));
memset(dis,/,sizeof(dis));
dis[s]=,flow[s]=inf,pre[s]=,vis[s]=;
dl.push(s);
while(!dl.empty())
{
int x=dl.front();
dl.pop();
vis[x]=;
for(int i=head[x];i;i=net[i])
{
int tmp=to[i];
if(cap[i]>&&dis[tmp]>dis[x]+cost[i])
{
dis[tmp]=dis[x]+cost[i];
pre[tmp]=x;
id[tmp]=i;
flow[tmp]=min(flow[x],cap[i]);
if(!vis[tmp]) vis[tmp]=,dl.push(tmp);
}
}
}
return pre[t]==-?:;
}
il void change_cap(int s,int t,int x)
{
int now=t;
while(now!=s)
{
cap[id[now]]-=x,cap[id[now]^]+=x;
now=pre[now];
}
}
void il get_ans(int s,int t)
{
max_flow=,min_cost=;
while(BFS(s,t))
{
//printf("%d\n",flow[t]);
max_flow+=flow[t],min_cost+=dis[t]*flow[t];
change_cap(s,t,flow[t]);
}
}
il void adx(int x,int y,int cax,int c)
{
add(x,y,cax,c),add(y,x,,-c);
}
int main()
{
int n,sum=,s=,t=;
scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%d",&val[i]),sum+=val[i];
sum/=n;
for(int i=;i<=n;i++)
{
val[i]-=sum;
if(val[i]>) add(s,i,val[i],),add(i,s,,);
else add(i+n,t,-val[i],),add(t,i+n,,);
}
for(int i=;i<=n;i++)
{
if(i!=n)
adx(i,i+,inf,),adx(i,i+n+,inf,);
if(i!=)
adx(i,i-,inf,),adx(i,i+n-,inf,);
}
adx(,n,inf,),adx(,*n,inf,),adx(n,,inf,),adx(n,n+,inf,);
get_ans(s,t);
return printf("%d",min_cost)*;
}
4.魔术球问题
emmm
好题，真的是好题。
类型：最小路径覆盖
QWQ
我们把柱子看做路径，然后把球成点。
枚举球的数量，看看这些球的最小覆盖路径是多少。
是否大于柱子。
建图：每增加一个新节点，枚举前面的节点看看是否为平方数，是就建边。
实现：枚举！
按说应该二分的，但是若我们进行二分，就得重新建图。
那么多数组初始化，肯定很慢的。
若我们枚举，每次多加一个球，那我们就可以在原来的残留网络上跑最大流啦，快的一批。
#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
#include <cmath>
#define il inline
using namespace std;
const int inf=;
const int maxm=+;
const int anx=;
int head[maxm],to[maxm*],cap[maxm*],net[maxm*];
int top[maxm];
int cnt=;
il void add(int x,int y,int c){cnt++,to[cnt]=y,cap[cnt]=c,net[cnt]=head[x],head[x]=cnt;}
int flow[maxm],pre[*anx+],id[maxm],preflow=,anaa;
int ans[maxm];
queue <int> dl;
bool vis[maxm];
il int BFS(int s,int t)
{
while(!dl.empty()) dl.pop();
memset(pre,-,sizeof(pre));
pre[s]=,flow[s]=inf;
dl.push(s);
while(!dl.empty())
{
int x=dl.front();
dl.pop();
if(x==t) break;
for(int i=head[x];i;i=net[i])
if(to[i]!=s&&cap[i]>&&pre[to[i]]==-)
{
pre[to[i]]=x,id[to[i]]=i;
flow[to[i]]=min(flow[x],cap[i]);
dl.push(to[i]);
}
}
if(pre[t]==-) return -;
else return flow[t];
}
il void change_cap(int s,int t,int x)
{
int now=t,last,sum=;
while(now!=s)
{
cap[id[now]]-=x;
cap[id[now]^]+=x;
now=pre[now];
}
}
il void maxflow(int s,int t)
{
//int max_flow=preflow;
int d=;
while((d=(BFS(s,t)))!=-)
{
change_cap(s,t,d);
anaa-=d;
}
//return anaa;
}
inline void adx(int x,int y,int cax)
{
add(x,y,cax),add(y,x,);
}
int main()
{
freopen("balla.in","r",stdin);
freopen("balla.out","w",stdout);
int nowball=;
int n,s,t;
scanf("%d",&n);
s=,t=;
while()
{
anaa++;
nowball++;
for(int i=;i<nowball;i++)
if(sqrt(i+nowball)==(int)sqrt(i+nowball)) adx(i,nowball+anx,);
adx(s,nowball,),adx(nowball+anx,t,);
maxflow(s,t);
if(anaa>n) break;
}
printf("%d",--nowball);
for(int i=;i<=nowball;i++)
for(int j=head[i];j;j=net[j])
if(cap[j]==) ans[i]=to[j]-anx;
puts("");
for(int i=;i<=nowball;i++)
{
if(vis[i]) continue;
int now=i;
while(now!=-anx)
printf("%d ",now),vis[now]=,now=ans[now];
puts("");
}
return ;
}
5.餐巾
类型：最小费用最大流
建模分析：首先 将每天拆成两个点
X代表每天需要的毛巾
Y代表每天产生的旧毛巾
需要的毛巾
1.每天需要的毛巾可以直接来自于购买毛巾
因此从源点向X连一条容量为need，费用为购买费用的边
2.每天需要的毛巾可以来源于之前洗的旧毛巾
因此从d1天前和d2天前产生旧毛巾的点向本天需要的点连容量无限大，费用为清洗费用的点
3.从每天需要的点向汇点连一条容量为need，费用为0的边
旧毛巾
1.每天至少产生need条旧毛巾
因此从源点向本天旧毛巾点连一条容量为need，费用为0的点
2.上一天的旧毛巾可以不去清洗
因此从上一天的旧毛巾点向本天的旧毛巾点连一条容量为inf，费用为0的点
分析：因为其他边都为无穷边，所以我们最终跑出的最大流即为need之和，最小费用流为答案
CODE
题目传送门
#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
#define il inline
#define ll long long
using namespace std;
const int inf=;
const int maxm=;
int head[maxm],to[maxm*],net[maxm*];
ll cost[maxm*],cap[maxm*];
int cnt=;
il void add(int x,int y,ll c,ll z){cnt++,to[cnt]=y,cost[cnt]=z,cap[cnt]=c,net[cnt]=head[x],head[x]=cnt;}
ll flow[maxm],dis[maxm],max_flow,min_cost;
int pre[maxm],id[maxm];
ll need[maxm];
bool vis[maxm];
queue <int> dl;
il bool BFS(ll s,ll t)
{
while(!dl.empty()) dl.pop();
for(int i=;i<=;i++) pre[i]=-,dis[i]=inf;
dis[s]=,flow[s]=inf,pre[s]=,vis[s]=;
dl.push(s);
while(!dl.empty())
{
int x=dl.front();
dl.pop();
vis[x]=;
for(int i=head[x];i;i=net[i])
{
int tmp=to[i];
if(cap[i]>&&dis[tmp]>dis[x]+cost[i])
{
dis[tmp]=dis[x]+cost[i];
pre[tmp]=x;
id[tmp]=i;
flow[tmp]=min(flow[x],cap[i]);
if(!vis[tmp]) vis[tmp]=,dl.push(tmp);
}
}
}
return pre[t]==-?:;
}
il void change_cap(int s,int t,ll x)
{
int now=t;
while(now!=s)
{
cap[id[now]]-=x,cap[id[now]^]+=x;
now=pre[now];
}
}
void il get_ans(int s,int t)
{
max_flow=,min_cost=;
while(BFS(s,t))
{
max_flow+=flow[t],min_cost+=dis[t]*flow[t];
change_cap(s,t,flow[t]);
}
}
il void adx(int x,int y,ll cax,ll c)
{
add(x,y,cax,c),add(y,x,,-c);
}
il ll read()
{
ll x=,w=;char ch=;
while(ch<'0'||ch>'9') {if(ch=='-') w=-;ch=getchar();}
while(ch>='0'&&ch<='9') {x=(x<<)+(x<<)+ch-'0';ch=getchar();}
return x*w;
}
int main()
{
freopen("napkin.in","r",stdin);
freopen("napkin.out","w",stdout);
int n;
scanf("%d",&n);
for(int i=;i<=n;i++)
need[i]=read();
ll p=read(),d1=read(),p1=read(),d2=read(),p2=read();
int s=,t=;
for(int i=;i<=n;i++)
{
adx(s,i,need[i],p),adx(s,i+n,need[i],);//i为需求毛巾数量,第一个模拟的是直接购买毛巾的数量,第二个为今日旧毛巾的数量
adx(i,t,need[i],);
if(i+d1<=n) adx(i+n,i+d1,inf,p1);
if(i+d2<=n) adx(i+n,i+d2,inf,p2);//今日需求毛巾可以由之前的快洗和慢洗毛巾得来
if(i+<=n) adx(i+n,i++n,inf,);
}
get_ans(s,t);
return printf("%lld\n",min_cost)*;
}
6.最小路径覆盖问题
问题：给你若干个点和边，问最少用几条路可以覆盖掉全图。
问题转化：网络流
题目传送门
分析：
我们首先将原图用n条路径覆盖，每条边只经过每个节点。
现在尽量合并更多的路径(即将两个路径通过一条边首尾相连)。
可以知道，每合并两条路径，图中的路径覆盖数就会减少1。
所以我们只需要利用网络流合并相关的路径即可。
答案求解：
首先将每个节点拆成(Xi,Yi)两个节点，建立源点和汇点，分别连接(S,Xi)和(Yi,T)。
然后对于每一条原图中的边，建立边(Xi,Yi)即可。
这样每一条增广路都只会经过2个节点(Xa,Yb)，对应合并的两个节点。
由于每个节点至多与一个节点合并，故边(S,Xi)和(Yi,T)容量为1。
此时的最大流对应的就是最多可以合并的路径数。
至于输出路径嘛，这题是SPJ，瞎搞就行。
#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
#include <cmath>
#define il inline
using namespace std;
const int inf=;
const int maxm=+;
const int anx=;
int head[maxm],to[maxm*],cap[maxm*],net[maxm*];
int top[maxm];
int cnt=;
il void add(int x,int y,int c){cnt++,to[cnt]=y,cap[cnt]=c,net[cnt]=head[x],head[x]=cnt;}
int flow[maxm],pre[],id[maxm],preflow=,anaa;
int ans[maxm];
queue <int> dl;
bool vis[maxm];
il int BFS(int s,int t)
{
while(!dl.empty()) dl.pop();
memset(pre,-,sizeof(pre));
pre[s]=,flow[s]=inf;
dl.push(s);
while(!dl.empty())
{
int x=dl.front();
dl.pop();
if(x==t) break;
for(int i=head[x];i;i=net[i])
if(to[i]!=s&&cap[i]>&&pre[to[i]]==-)
{
pre[to[i]]=x,id[to[i]]=i;
flow[to[i]]=min(flow[x],cap[i]);
dl.push(to[i]);
}
}
if(pre[t]==-) return -;
else return flow[t];
}
il void change_cap(int s,int t,int x)
{
int now=t,last,sum=;
while(now!=s)
{
cap[id[now]]-=x;
cap[id[now]^]+=x;
now=pre[now];
}
}
il int maxflow(int s,int t)
{
int max_flow=;
int d=;
while((d=(BFS(s,t)))!=-)
{
change_cap(s,t,d);
max_flow+=d;
}
return max_flow;
}
inline void adx(int x,int y,int cax)
{
add(x,y,cax),add(y,x,);
}
int main()
{
int n,m,s=,t;
scanf("%d%d",&n,&m);
t=;
for(int i=;i<=n;i++) adx(s,i,),adx(i+anx,t,);
for(int i=;i<=m;i++)
{
int a,b;
scanf("%d%d",&a,&b);
adx(a,b+anx,);
}
int Ans=maxflow(s,t);
for(int i=;i<=n;i++)
for(int j=head[i];j;j=net[j])
if(cap[j]==) ans[i]=to[j]-anx;
for(int i=;i<=n;i++)
{
if(vis[i]) continue;
int now=i;
while(now!=-anx)
printf("%d ",now),vis[now]=,now=ans[now];
puts("");
}
return printf("%d\n",n-Ans)*;
}
7.试题库问题
这道题基本上算是网络流最简单的题了。
首先建图（屁话
首先，对于每个题库可以向汇点连一条容量为需求的边。
对于每个题目，先从源点向每个题目连一条容量为1的边。
然后从每个题目向所属题库连容量为1的边。
然后，没了。。。
方案输出，找一下cap为0的就行了。
SPJ的评测
#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
#include <cmath>
#include <vector>
#define il inline
using namespace std;
const int inf=;
const int maxm=+;
const int anx=;
int head[maxm],to[maxm*],cap[maxm*],net[maxm*];
int top[maxm];
int cnt=;
il void add(int x,int y,int c){cnt++,to[cnt]=y,cap[cnt]=c,net[cnt]=head[x],head[x]=cnt;}
int flow[maxm],pre[],id[maxm],preflow=,anaa;
queue <int> dl;
bool vis[maxm];
vector <int> ans[];
il int BFS(int s,int t)
{
while(!dl.empty()) dl.pop();
memset(pre,-,sizeof(pre));
pre[s]=,flow[s]=inf;
dl.push(s);
while(!dl.empty())
{
int x=dl.front();
dl.pop();
if(x==t) break;
for(int i=head[x];i;i=net[i])
if(to[i]!=s&&cap[i]>&&pre[to[i]]==-)
{
pre[to[i]]=x,id[to[i]]=i;
flow[to[i]]=min(flow[x],cap[i]);
dl.push(to[i]);
}
}
if(pre[t]==-) return -;
else return flow[t];
}
il void change_cap(int s,int t,int x)
{
int now=t,last,sum=;
while(now!=s)
{
cap[id[now]]-=x;
cap[id[now]^]+=x;
now=pre[now];
}
}
il int maxflow(int s,int t)
{
int max_flow=;
int d=;
while((d=(BFS(s,t)))!=-)
{
change_cap(s,t,d);
max_flow+=d;
}
return max_flow;
}
inline void adx(int x,int y,int cax)
{
add(x,y,cax),add(y,x,);
}
int main()
{
int n,k;
scanf("%d%d",&k,&n);
int s=,t=;
for(int i=,x;i<=k;i++)
scanf("%d",&x),adx(i,t,x);
for(int i=;i<=n;i++)
{
int p;
adx(s,i+n,);
scanf("%d",&p);
for(int j=,x;j<=p;j++)
scanf("%d",&x),adx(i+n,x,);
}
maxflow(s,t);
//printf("This is ans\n");
for(int i=;i<=n;i++)
{
for(int j=head[i+n];j;j=net[j])
if(cap[j]==)
{
ans[to[j]].push_back(i);
break;
}
}
for(int i=;i<=k;i++)
{
printf("%d:",i);
for(int j=;j<ans[i].size();j++)
printf(" %d",ans[i][j]);
puts("");
}
return ;
}
8.星际转移问题
类型：网络最大流
分析：
飞船对于不同的时间，航道不同，所以用时间建模。
不停的增加时间，用飞船运载乘客，当某一时刻图中的最大流超过了乘客数，即为最小的花费时间。
建模：
首先从源点向地球连一条inf的边
从月球向汇点连一条inf的边
由于乘客可以在空间站等待，所以从上个时刻空间站的点（包括地月）向本时刻连一条inf的边
从飞船的上一时刻位置向本时刻位置连一条p[i]的边
然后不停跑最大流就可以了。
问题 ：不存在的情况，即无从地球通往月球的航道，并查集即可解决。
懒得搞了，天数>600时输出无解。。。
CODE
#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
#include <cmath>
#include <vector>
#define il inline
using namespace std;
const int inf=;
const int maxm=+;
const int anx=;
int head[maxm],to[maxm*],cap[maxm*],net[maxm*];
int p[maxm];
int cnt=;
il void add(int x,int y,int c){cnt++,to[cnt]=y,cap[cnt]=c,net[cnt]=head[x],head[x]=cnt;}
int flow[maxm],pre[],id[maxm],preflow=,anaa;
queue <int> dl;
bool vis[maxm];
int dx[][],len[],n,m,k;;
il int BFS(int s,int t)
{
while(!dl.empty()) dl.pop();
memset(pre,-,sizeof(pre));
pre[s]=,flow[s]=inf;
dl.push(s);
while(!dl.empty())
{
int x=dl.front();
dl.pop();
if(x==t) break;
for(int i=head[x];i;i=net[i])
if(to[i]!=s&&cap[i]>&&pre[to[i]]==-)
{
pre[to[i]]=x,id[to[i]]=i;
flow[to[i]]=min(flow[x],cap[i]);
dl.push(to[i]);
}
}
if(pre[t]==-) return -;
else return flow[t];
}
il void change_cap(int s,int t,int x)
{
int now=t,last,sum=;
while(now!=s)
{
cap[id[now]]-=x;
cap[id[now]^]+=x;
now=pre[now];
}
}
il int maxflow(int s,int t)
{
int max_flow=preflow;
int d=;
while((d=(BFS(s,t)))!=-)
{
change_cap(s,t,d);
max_flow+=d;
}
return max_flow;
}
inline void adx(int x,int y,int cax)
{
add(x,y,cax),add(y,x,);
}
void make_map(int day)
{
for(int i=;i<=n;i++)
adx(i+(day-)*n,i+day*n,inf);
for(int i=;i<=m;i++)
{
int x=dx[i][(day-)%len[i]];
int y=dx[i][day%len[i]];
adx((day-)*n+x,day*n+y,p[i]);
}
}
int main()
{
scanf("%d%d%d",&n,&m,&k);
n+=;
for(int i=,size;i<=m;i++)
{
scanf("%d",&p[i]);
scanf("%d",&size);
len[i]=size;
for(int j=;j<size;j++)
{
scanf("%d",&dx[i][j]);
dx[i][j]+=;
}
}
int s=,t=;
int day=;
while()
{
adx(s,day*n+,inf),adx(day*n+,t,inf);
if(day>=)
make_map(day);
preflow=maxflow(s,t);
if(preflow>=k)
{
printf("%d\n",day);
return ;
}
day++;
if(day==)
{
printf("0\n");
return ;
}
}
}
9.运输问题
这题也太裸了。。。。
类型：费用流
建图：
从源点向仓库连容量为提供量，费用为0的边
从商店向汇点连容量为需求量，费用为0的边
从每个仓库向商店连容量inf，费用为运输费的边
第一问跑最小费用最大流
第二问跑最大费用最大流
啥，你问我咋跑最大费用，SPFA跑最长路就行啊（滑稽
题目链接
#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
#define il inline
using namespace std;
const int inf=;
const int maxm=;
int head[maxm],to[maxm*],cap[maxm*],net[maxm*],cost[maxm*];
int need[maxm],sup[maxm],wt[][];
int cnt=;
il void add(int x,int y,int c,int z){cnt++,to[cnt]=y,cost[cnt]=z,cap[cnt]=c,net[cnt]=head[x],head[x]=cnt;}
int flow[maxm],pre[maxm],id[maxm],dis[maxm],max_flow,min_cost;
bool vis[maxm];
queue <int> dl;
il bool BFS(int s,int t)
{
while(!dl.empty()) dl.pop();
memset(pre,-,sizeof(pre));
memset(dis,/,sizeof(dis));
dis[s]=,flow[s]=inf,pre[s]=,vis[s]=;
dl.push(s);
while(!dl.empty())
{
int x=dl.front();
dl.pop();
vis[x]=;
for(int i=head[x];i;i=net[i])
{
int tmp=to[i];
if(cap[i]>&&dis[tmp]>dis[x]+cost[i])
{
dis[tmp]=dis[x]+cost[i];
pre[tmp]=x;
id[tmp]=i;
flow[tmp]=min(flow[x],cap[i]);
if(!vis[tmp]) vis[tmp]=,dl.push(tmp);
}
}
}
return pre[t]==-?:;
}
il void change_cap(int s,int t,int x)
{
int now=t;
while(now!=s)
{
cap[id[now]]-=x,cap[id[now]^]+=x;
now=pre[now];
}
}
il bool BFS1(int s,int t)
{
while(!dl.empty()) dl.pop();
memset(pre,-,sizeof(pre));
memset(dis,,sizeof(dis));
dis[s]=,flow[s]=inf,pre[s]=,vis[s]=;
dl.push(s);
while(!dl.empty())
{
int x=dl.front();
dl.pop();
vis[x]=;
for(int i=head[x];i;i=net[i])
{
int tmp=to[i];
if(cap[i]>&&dis[tmp]<dis[x]+cost[i])
{
dis[tmp]=dis[x]+cost[i];
pre[tmp]=x;
id[tmp]=i;
flow[tmp]=min(flow[x],cap[i]);
if(!vis[tmp]) vis[tmp]=,dl.push(tmp);
}
}
}
return pre[t]==-?:;
}
void il get_ans(int s,int t)
{
max_flow=,min_cost=;
while(BFS(s,t))
{
max_flow+=flow[t],min_cost+=dis[t]*flow[t];
change_cap(s,t,flow[t]);
}
}
void il get_ans1(int s,int t)
{
max_flow=,min_cost=;
while(BFS1(s,t))
{
max_flow+=flow[t],min_cost+=dis[t]*flow[t];
change_cap(s,t,flow[t]);
}
}
il void adx(int x,int y,int cax,int c)
{
add(x,y,cax,c),add(y,x,,-c);
}
int main()
{
freopen("tran.in","r",stdin);
freopen("tran.out","w",stdout);
int n,m;
scanf("%d%d",&n,&m);
int s=,t=m+n+;
for(int i=;i<=n;i++)
scanf("%d",&sup[i]),adx(s,i,sup[i],);
for(int i=;i<=m;i++)
scanf("%d",&need[i]),adx(i+n,t,need[i],);
for(int i=;i<=n;i++)
for(int j=,x;j<=m;j++)
scanf("%d",&wt[i][j]),adx(i,j+n,inf,wt[i][j]);
get_ans(s,t);
printf("%d\n",min_cost);
memset(head,,sizeof(head)),memset(to,,sizeof(to));
memset(cap,,sizeof(cap)),memset(cost,,sizeof(cost));
cnt=;
for(int i=;i<=n;i++)
adx(s,i,sup[i],);
for(int i=;i<=m;i++)
adx(i+n,t,need[i],);
for(int i=;i<=n;i++)
for(int j=,x;j<=m;j++)
adx(i,j+n,inf,wt[i][j]);
get_ans1(s,t);
return printf("%d\n",min_cost)*;
}
10.航空问题
费用流问题。
建图：
源点向起点连inf费用为0的边
终点向汇点连inf费用为0的边
除了起点终点，每个点只能走一次。
所以拆点，容量为1，费用为1
起点终点容量为2，费用为1
输入的边容量为1费用为0
跑最大费用流
若最大流为2，则有解
因为起点终点经过两次 所以 答案-2
CODE
#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
#include <map>
#define il inline
using namespace std;
const int inf=;
const int maxm=;
int head[maxm],to[maxm*],cap[maxm*],net[maxm*],cost[maxm*];
map <string,int> idx;
string name[maxm];
int cnt=;
il void add(int x,int y,int c,int z){cnt++,to[cnt]=y,cost[cnt]=z,cap[cnt]=c,net[cnt]=head[x],head[x]=cnt;}
int flow[maxm],pre[maxm],id[maxm],dis[maxm],max_flow,min_cost,ans[maxm],w[maxm];
bool vis[maxm];
queue <int> dl;
il void change_cap(int s,int t,int x)
{
int now=t;
while(now!=s)
{
cap[id[now]]-=x,cap[id[now]^]+=x;
now=pre[now];
}
}
il bool BFS(int s,int t)
{
while(!dl.empty()) dl.pop();
memset(pre,-,sizeof(pre));
memset(dis,,sizeof(dis));
dis[s]=,flow[s]=inf,pre[s]=,vis[s]=;
dl.push(s);
while(!dl.empty())
{
int x=dl.front();
dl.pop();
vis[x]=;
for(int i=head[x];i;i=net[i])
{
int tmp=to[i];
if(cap[i]>&&dis[tmp]<dis[x]+cost[i])
{
dis[tmp]=dis[x]+cost[i];
pre[tmp]=x;
id[tmp]=i;
flow[tmp]=min(flow[x],cap[i]);
if(!vis[tmp]) vis[tmp]=,dl.push(tmp);
}
}
}
return pre[t]==-?:;
}
void il get_ans(int s,int t)
{
max_flow=,min_cost=;
while(BFS(s,t))
{
max_flow+=flow[t],min_cost+=dis[t]*flow[t];
change_cap(s,t,flow[t]);
}
}
il void adx(int x,int y,int cax,int c)
{
add(x,y,cax,c),add(y,x,,-c);
}
int main()
{
int n,v;
scanf("%d%d",&n,&v);
int s=,t=;
for(int i=;i<=n;i++)
{
cin>>name[i];
idx[name[i]]=i;
if(i!=&&i!=n) adx(i,i+n,,);
else adx(i,i+n,,);
w[i]=cnt;
}
adx(s,,inf,);
adx(*n,t,inf,);
for(int i=;i<=v;i++)
{
string s1,s2;
cin>>s1>>s2;
adx(idx[s1]+n,idx[s2],,);
}
get_ans(s,t);
if(max_flow!=) printf("No Solution!\n");
else
{
memset(vis,,sizeof(vis));
printf("%d\n",min_cost-);
}
}
10.分配问题
类型：最小费用流
这题是裸题
qwq
#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
#define il inline
using namespace std;
const int inf=;
const int maxm=;
int head[maxm],to[maxm*],cap[maxm*],net[maxm*],cost[maxm*];
int need[maxm],sup[maxm],wt[][];
int cnt=;
il void add(int x,int y,int c,int z){cnt++,to[cnt]=y,cost[cnt]=z,cap[cnt]=c,net[cnt]=head[x],head[x]=cnt;}
int flow[maxm],pre[maxm],id[maxm],dis[maxm],max_flow,min_cost;
bool vis[maxm];
queue <int> dl;
il bool BFS(int s,int t)
{
while(!dl.empty()) dl.pop();
memset(pre,-,sizeof(pre));
memset(dis,/,sizeof(dis));
dis[s]=,flow[s]=inf,pre[s]=,vis[s]=;
dl.push(s);
while(!dl.empty())
{
int x=dl.front();
dl.pop();
vis[x]=;
for(int i=head[x];i;i=net[i])
{
int tmp=to[i];
if(cap[i]>&&dis[tmp]>dis[x]+cost[i])
{
dis[tmp]=dis[x]+cost[i];
pre[tmp]=x;
id[tmp]=i;
flow[tmp]=min(flow[x],cap[i]);
if(!vis[tmp]) vis[tmp]=,dl.push(tmp);
}
}
}
return pre[t]==-?:;
}
il void change_cap(int s,int t,int x)
{
int now=t;
while(now!=s)
{
cap[id[now]]-=x,cap[id[now]^]+=x;
now=pre[now];
}
}
il bool BFS1(int s,int t)
{
while(!dl.empty()) dl.pop();
memset(pre,-,sizeof(pre));
memset(dis,,sizeof(dis));
dis[s]=,flow[s]=inf,pre[s]=,vis[s]=;
dl.push(s);
while(!dl.empty())
{
int x=dl.front();
dl.pop();
vis[x]=;
for(int i=head[x];i;i=net[i])
{
int tmp=to[i];
if(cap[i]>&&dis[tmp]<dis[x]+cost[i])
{
dis[tmp]=dis[x]+cost[i];
pre[tmp]=x;
id[tmp]=i;
flow[tmp]=min(flow[x],cap[i]);
if(!vis[tmp]) vis[tmp]=,dl.push(tmp);
}
}
}
return pre[t]==-?:;
}
void il get_ans(int s,int t)
{
max_flow=,min_cost=;
while(BFS(s,t))
{
max_flow+=flow[t],min_cost+=dis[t]*flow[t];
change_cap(s,t,flow[t]);
}
}
void il get_ans1(int s,int t)
{
max_flow=,min_cost=;
while(BFS1(s,t))
{
max_flow+=flow[t],min_cost+=dis[t]*flow[t];
change_cap(s,t,flow[t]);
}
}
il void adx(int x,int y,int cax,int c)
{
add(x,y,cax,c),add(y,x,,-c);
}
int main()
{
int n;
scanf("%d",&n);
int s=,t=;
for(int i=;i<=n;i++)
{
adx(s,i,,);
adx(i+n,t,,);
for(int j=;j<=n;j++)
scanf("%d",&wt[i][j]),adx(i,j+n,,wt[i][j]);
}
get_ans(s,t);
printf("%d\n",min_cost);
memset(head,,sizeof(head)),memset(to,,sizeof(to));
memset(cap,,sizeof(cap)),memset(cost,,sizeof(cost));
cnt=;
for(int i=;i<=n;i++)
{
adx(s,i,,);
adx(i+n,t,,);
for(int j=;j<=n;j++)
adx(i,j+n,,wt[i][j]);
}
get_ans1(s,t);
printf("%d\n",min_cost);
return ;
}
11.圆桌问题
类型：网络最大流
建模：
对于每组人员，从源点S向每组连一条容量为人员数量的边
对于每个桌子，向汇点T连一条容量为容纳人员数量的边
每组人员向每个桌子连一条容量为1的边即可。
Judge：跑出来的最大流是否等于总人数
方案：枚举即可
#include <cstdio>
#include <iostream>
#include <queue>
#include <cstring>
#define il inline
using namespace std;
const int inf=;
const int maxm=;
int head[maxm],to[maxm*],cap[maxm*],net[maxm*],deep[maxm],cnt=;
il void add(int x,int y,int c){cnt++,to[cnt]=y,cap[cnt]=c,net[cnt]=head[x],head[x]=cnt;}
queue <int> dl;
il bool BFS(int s,int t)
{
while(!dl.empty()) dl.pop();
memset(deep,-,sizeof(deep));
dl.push(s),deep[s]=;
while(!dl.empty())
{
int x=dl.front();dl.pop();
for(int i=head[x];i;i=net[i])
if(cap[i]>&&deep[to[i]]==-)
dl.push(to[i]),deep[to[i]]=deep[x]+;
}
return deep[t]==-?:;
}
int dfs(int now,int flow,int t)
{
if(now==t) return flow;
int w,used=;
for(int i=head[now];i;i=net[i])
{
int v=to[i];
if(deep[v]==deep[now]+&&cap[i])
{
w=dfs(v,min(flow-used,cap[i]),t);
cap[i]-=w;
cap[i^]+=w;
used+=w;
if(used==flow) return flow;
}
}
if(!used) deep[now]=-;
return used;
}
il int dinic(int s,int t)
{
int maxflow=;
while(BFS(s,t)) maxflow+=dfs(s,inf,t);
return maxflow;
}
inline void adx(int x,int y,int cax)
{
add(x,y,cax),add(y,x,);
}
il int read()
{
int x=,w=;
char ch=;
while(ch<'0'||ch>'9')
{
if(ch=='-') w=-;
ch=getchar();
}
while(ch>='0'&&ch<='9')
x=(x<<)+(x<<)+ch-'0',ch=getchar();
return x*w;
}
int main()
{
//freopen("roundtable.in","r",stdin);
//freopen("roundtable.out","w",stdout);
int n,m;
n=read(),m=read();
int s=,t=,sum=;
for(int i=,x;i<=n;i++)
{
x=read(),sum+=x;
adx(s,i,x);
}
for(int i=,x;i<=m;i++)
{
x=read();
adx(i+n,t,x);
}
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
adx(i,j+n,);
int ans=(dinic(s,t)==sum);
printf("%d\n",ans);
if(ans)
{
for(int i=;i<=n;i++)
{
for(int j=head[i];j;j=net[j])
if(cap[j]==) printf("%d ",to[j]-n);
puts("");
}
}
return ;
}
12.最长不下降子序列问题
qwq
类型：最大不交叉路径->最大流
第一问 可以用 n^2的办法解决，同时求出以某个数字最作为结尾时最长的不下降最序列长度，len[i]。
第二问 题目要求每个数字只用一次，问题为最大不交叉路径
考虑通过第一问求出的数组来分层建图
首先每个数字只用一次，很明显要拆点
当一个位置的len[i]为第一问答案时，这个位置可以作为结尾，于是从源点连一条容量为inf的边
反之，当一个位置len[i]=1时，那么这个位置可以作为开头，于是从此点的出点向汇点连一条inf的边
对于 i<j并且val[i]<=val[j]len[i]==len[j]−1时 i < j 并 且 v a l [ i ] <= v a l [ j ] l e n [ i ] == l e n [ j ] − 1 时 ，这两个点可以接在一起，于是从j的出点向i的入点建一条容量为1的边
跑最大流即为答案
第三问，将1和n的出点和入点的边容量改为inf即可
#include <cstdio>
#include <iostream>
#include <queue>
#include <cstring>
#define il inline
using namespace std;
const int inf=;
const int maxm=;
int head[],to[maxm*],cap[maxm*],net[maxm*],deep[],cnt=;
il void add(int x,int y,int c){cnt++,to[cnt]=y,cap[cnt]=c,net[cnt]=head[x],head[x]=cnt;}
queue <int> dl;
int maxlen[maxm],val[maxm];
il bool BFS(int s,int t)
{
while(!dl.empty()) dl.pop();
memset(deep,-,sizeof(deep));
dl.push(s),deep[s]=;
while(!dl.empty())
{
int x=dl.front();dl.pop();
for(int i=head[x];i;i=net[i])
if(cap[i]>&&deep[to[i]]==-)
dl.push(to[i]),deep[to[i]]=deep[x]+;
}
return deep[t]==-?:;
}
int dfs(int now,int flow,int t)
{
if(now==t) return flow;
int w,used=;
for(int i=head[now];i;i=net[i])
{
int v=to[i];
if(deep[v]==deep[now]+&&cap[i])
{
w=dfs(v,min(flow-used,cap[i]),t);
cap[i]-=w;
cap[i^]+=w;
used+=w;
if(used==flow) return flow;
}
}
if(!used) deep[now]=-;
return used;
}
il int dinic(int s,int t)
{
int maxflow=;
while(BFS(s,t)) maxflow+=dfs(s,inf,t);
return maxflow;
}
inline void adx(int x,int y,int cax)
{
add(x,y,cax),add(y,x,);
}
il int read()
{
int x=,w=;
char ch=;
while(ch<'0'||ch>'9')
{
if(ch=='-') w=-;
ch=getchar();
}
while(ch>='0'&&ch<='9')
x=(x<<)+(x<<)+ch-'0',ch=getchar();
return x*w;
}
int main()
{
freopen("alis.in","r",stdin);
freopen("alis.out","w",stdout);
int n=read();
for(int i=;i<=n;i++)
val[i]=read();
for(int i=;i<=n;i++)
maxlen[i]=;
int ans=;
for(int i=;i<=n;i++)
for(int j=;j<i;j++)
if(val[j]<=val[i]) maxlen[i]=max(maxlen[i],maxlen[j]+),ans=max(ans,maxlen[i]);
printf("%d\n",ans);
if(ans==) printf("%d\n%d\n",n,n);
if(ans==) printf("0\n0\n");
if(ans!=&&ans!=)
{
int s=,t=;
for(int i=;i<=n;i++)
{
adx(i,i+n,);
if(maxlen[i]==ans) adx(s,i,inf);
if(maxlen[i]==) adx(i+n,t,inf);
for(int j=;j<i;j++)
if(val[j]<=val[i]&&maxlen[j]+==maxlen[i]) adx(i+n,j,);
}
printf("%d\n",dinic(s,t));
memset(head,,sizeof(head)),cnt=;
for(int i=;i<=n;i++)
{
if(i!=&&i!=n) adx(i,i+n,);
else adx(i,i+n,inf);
if(maxlen[i]==ans) adx(s,i,inf);
if(maxlen[i]==) adx(i+n,t,inf);
for(int j=;j<i;j++)
if(val[j]<=val[i]&&maxlen[j]+==maxlen[i]) adx(i+n,j,);
}
printf("%d\n",dinic(s,t));
}
return ;
}
13.孤岛营救问题
类型：状压+BFS
不是网络流（滑稽
很明显是个状压嘛。
我们状态压缩钥匙。
vis[x][y][S] v i s [ x ] [ y ] [ S ] 表示在x y这个位置持有钥匙状态为S是否来过
BFS队列里存4个变量
分别为当前横纵坐标，步数以及钥匙状态
map[x1][y1][x2][y2]表示两个点直接是否有墙或者是门。
pas[x][y][i]表示x y这个点放的钥匙的种类
num[x][y]表示当前点钥匙数目
坑点：
1.钥匙不是用了就没了（(#`O′)喂，没了才有问题吧
2.一个点可以放多个钥匙（人家又没说只放一个。
3.初始点可以放钥匙
4.别忘了输出-1….
虽然我只被2坑了
CODE
题目传送门
#include <cstdio>
#include <iostream>
#include <queue>
#define il inline
using namespace std;
bool vis[][][(<<)];
int map[][][][];
int pas[][][],num[][];
struct node{
int x,y,step,cos;
};
queue <node> dl;
int n,m,p,k;
int dx[]={,,-,,},dy[]={,,,,-};
il int BFS()
{
int nows=;
for(int i=;i<=num[][];i++)
nows|=(<<(pas[][][i]-));
vis[][][nows]=;
dl.push((node){,,,nows});
while(!dl.empty())
{
node now=dl.front();
dl.pop();
if(now.x==n&&now.y==m)
return now.step;
for(int i=;i<=;i++)
{
int xx=now.x+dx[i],yy=now.y+dy[i],t;
if(xx<||yy<||xx>n||yy>m) continue;
if(map[now.x][now.y][xx][yy]==-) continue;
if((t=map[now.x][now.y][xx][yy])!=)
if((now.cos&(<<(t-)))==) continue;
int cosx=now.cos;
for(int j=;j<=num[xx][yy];j++)
cosx|=(<<(pas[xx][yy][j]-));
if(vis[xx][yy][cosx]) continue;
vis[xx][yy][cosx]=;
dl.push((node){xx,yy,now.step+,cosx});
}
}
return -;
}
int main()
{
//freopen("rescue.in","r",stdin);
//freopen("rescue.out","w",stdout);
scanf("%d%d%d%d",&n,&m,&p,&k);
for(int i=;i<=k;i++)
{
int x1,x2,y1,y2,g;
scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&g);
if(g==) map[x1][y1][x2][y2]=map[x2][y2][x1][y1]=-;
else map[x1][y1][x2][y2]=map[x2][y2][x1][y1]=g;
}
int s;
scanf("%d",&s);
for(int i=;i<=s;i++)
{
int x,y,p;
scanf("%d%d%d",&x,&y,&p);
pas[x][y][++num[x][y]]=p;
}
printf("%d\n",BFS());
return ;
}
14.汽车行驶问题
按照要求BFS就行了，
坑点：强制消费。
qwq
#include <cstdio>
#include <iostream>
#include <queue>
#include <cstring>
#define il inline
using namespace std;
int vis[][][],n,a,b,c,k;
struct node{
int x,y,cost,oil;
};
queue <node> dl;
bool map[][];
int dx[]={,,-,,},dy[]={,,,,-};
il int BFS()
{
memset(vis,/,sizeof(vis));
dl.push((node){,,,k});
vis[][][k]=;
while(!dl.empty())
{
node now=dl.front();
//printf("%d %d %d %d\n",now.x,now.y,now.cost,now.oil);
node nex;
dl.pop();
if(now.oil==) continue;
//printf("1\n");
for(int i=;i<=;i++)
{
int xx=now.x+dx[i],yy=now.y+dy[i];
if(xx<||yy<||xx>n||yy>n) continue;
nex.x=xx,nex.y=yy,nex.cost=now.cost,nex.oil=now.oil-;
if(nex.x<now.x||nex.y<now.y) nex.cost+=b;
if(map[nex.x][nex.y])
nex.oil=k,nex.cost+=a;
if(vis[nex.x][nex.y][nex.oil]>nex.cost) vis[nex.x][nex.y][nex.oil]=nex.cost,dl.push(nex);
if(map[nex.x][nex.y]==)
{
nex.oil=k,nex.cost+=(a+c);
if(vis[nex.x][nex.y][nex.oil]>nex.cost) vis[nex.x][nex.y][nex.oil]=nex.cost,dl.push(nex);
}
}
}
int ans=vis[][][];
for(int i=;i<=k;i++)
ans=min(ans,vis[n][n][i]);
return ans;
}
int main()
{
scanf("%d%d%d%d%d",&n,&k,&a,&b,&c);
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
scanf("%d",&map[i][j]);
return printf("%d\n",BFS())*;
}
15.太空飞行计划问题
http://blog.csdn.net/qq_35914587/article/details/79155879
忘了有这个分类了，写完了才想起来，不粘贴了。
16.方格取数问题
http://blog.csdn.net/qq_35914587/article/details/79163024
17.骑士共存问题
http://blog.csdn.net/qq_35914587/article/details/79163404
![#1394 : 网络流四·最小路径覆盖[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)