前言
網絡流大法好
隻刷了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=)