E-K算法代码模板
#include <bits/stdc++.h>
#define ll long long
#define IOS std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int M=500005;
struct node
{
int to,next;
int w;
}e[M];
int head[M],vis[M],dis[M],pre[M];
int cnt=2,n,m,s,t,ans,inf=99999999;
void add(int u,int v,int w){
e[cnt].to=v;
e[cnt].w=w;
e[cnt].next=head[u];
head[u]=cnt++;
e[cnt].to=u;
e[cnt].w=0;
e[cnt].next=head[v];
head[v]=cnt++;
}
int bfs()//bfs找增广路
{
for(int i=1;i<=n;i++){vis[i]=0;}
queue<int> q;
q.push(s);
vis[s]=1;
dis[s]=inf;//dis数组表示流经该点的流量
while(!q.empty())
{
int x=q.front();
q.pop();
for(int i=head[x];i;i=e[i].next)
{
if(e[i].w==0)continue;
int v=e[i].to;
if(vis[v]==1)continue;
dis[v]=min(dis[x],e[i].w);
pre[v]=i;
q.push(v);
vis[v]=1;
if(v==t)return 1;
}
}
return 0;
}
void update()//更新残留网络
{
int x=t;//x=汇点,倒着更新
while(x!=s)
{
int v=pre[x];
e[v].w-=dis[t];
e[v^1].w+=dis[t];
x=e[v^1].to;
}
ans+=dis[t];
}
int main()
{
int u,v,w;
scanf("%d %d %d %d",&n,&m,&s,&t);
for(int i=1;i<=m;i++)
{
scanf("%d %d %d",&u,&v,&w);
add(u,v,w);
}
while(bfs()!=0)
{update();}
printf("%d\n",ans);
return 0;
}Dinic算法代码模板
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll inf=0x3f3f3f3f;
ll n,m,u,v,s,t;
ll w,ans,dis[530005];
ll cnt=2,now[530005],head[530005];
struct node
{
ll to,next,w;
}e[530005];
void add(ll u,ll v,ll w)
{
e[cnt].to=v;
e[cnt].w=w;
e[cnt].next=head[u];
head[u]=cnt++;
e[cnt].to=u;
e[cnt].w=0;
e[cnt].next=head[v];
head[v]=cnt++;
}
ll bfs()//在残量网络中构造分层图
{
for (int i=1;i<=n;i++)dis[i]=0;//将所有点初始置为inf
queue<ll> q;//定义队列
q.push(s);//将源点入队
dis[s]=1;//源点为第1层
now[s]=head[s];//当前弧优化
while(!q.empty())
{
ll x=q.front();
q.pop();
for(int i=head[x];i;i=e[i].next)
{
ll v=e[i].to;
if(e[i].w>0&&dis[v]==0)
{
q.push(v);
now[v]=head[v];
dis[v]=dis[x]+1;
if(v==t)return 1;//找到一条增广路
}
}
}
return 0;
}
ll dfs(ll x,ll sum)
{
if(x==t)return sum;
ll k,res=0;//k是当前最小的剩余容量
for(int i=now[x];i&∑i=e[i].next)
{
now[x]=i;//当前弧优化
ll v=e[i].to;
if(e[i].w>0&&(dis[v]==dis[x]+1))
{
k=dfs(v,min(sum,e[i].w));
if(k==0){dis[v]=0;} //剪枝，去掉增广完毕的点
e[i].w-=k;
e[i^1].w+=k;
res+=k;//res表示经过该点的所有流量和（相当于流出的总量）
sum-=k; //sum表示经过该点的剩余流量
}
}
return res;
}
int main()
{
scanf("%lld %lld %lld %lld",&n,&m,&s,&t);
for(int i=1;i<=m;i++)
{
scanf("%lld %lld %lld",&u,&v,&w);
add(u,v,w);
}
while(bfs())
{ans+=dfs(s,inf);}//流量守恒,(流入=流出)
printf("%lld\n",ans);
return 0;
} 以下题目来自洛谷网络流24题（包括但不限于）
------------------------------------------------------------------------------------------------
飞行员配对方案问题
二分图最大匹配问题，建一个超级源点与超级汇点，源点与外籍飞行员建容量为1的边，汇点与英国飞行员也建容量为1的边，同理外籍飞行员与英国飞行之前也是建容量为1 的边，建好之后用dinic跑一个最大流即可，最后输出方案的时候根据两点之间的流量判断该边是否被使用
代码
#include <bits/stdc++.h>
#define ll long long
#define IOS std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
template<class T> inline void read(T &x){
x=0; register char c=getchar(); register bool f=0;
while(!isdigit(c))f^=c=='-',c=getchar();
while(isdigit(c))x=x*10+c-'0',c=getchar(); if(f)x=-x;
}
using namespace std;
struct node
{
int w,to,next;
}e[5005];
int head[5005],dis[5005],now[5005],vis[5005];
int cnt=2,n,m,s=201,t=202,u,v,inf=99999999;
void add(int u,int v,int w)
{
e[cnt].to=v;
e[cnt].w=w;
e[cnt].next=head[u];
head[u]=cnt++;
e[cnt].to=u;
e[cnt].w=0;
e[cnt].next=head[v];
head[v]=cnt++;
}
int bfs()
{
for(int i=1;i<=n;i++)dis[i]=0;
dis[s]=0;dis[t]=0;
queue<int> q;
q.push(s);
dis[s]=1;
//now[s]=head[s];
while(!q.empty())
{
int x=q.front();
q.pop();
for(int i=head[x];i;i=e[i].next)
{
int v=e[i].to;
if(e[i].w>0&&dis[v]==0)
{
q.push(v);
dis[v]=dis[x]+1;
//now[v]=head[v];
if(v==t){return 1;}
}
}
}
return 0;
}
int dfs(int x,int sum)
{
if(x==t){return sum;}
int k,res=0;
for(int i=head[x];i;i=e[i].next)
{
int v=e[i].to;
if(e[i].w>0&&(dis[v]==dis[x]+1))
{
k=dfs(v,min(sum,e[i].w));
if(k==0)dis[v]=0;
e[i].w-=k;
//pre[v]=x;
e[i^1].w+=k;
res+=k;
sum-=k;
}
}
return res;
}
int main()
{
IOS
cin>>m>>n;
while(cin>>u>>v)
{
if(u==-1&&v==-1)
{break;}
if(vis[u]==0)
{add(s,u,1);
vis[u]=1;}
if(vis[v]==0)
{add(v,t,1);
vis[v]=1;}
add(u,v,1);
}
int ans=0;
while(bfs()){
ans+=dfs(s,inf);
}
cout<<ans<<endl;
for(int i=1;i<=m;i++)
{
for(int j=head[i];j;j=e[j].next)
{
if(e[j].w==0)
{
int to=e[j].to;
if(to==s){continue;}
cout<<i<<" "<<to<<endl;
break;
}
}
}
return 0;
}地震逃生
很裸的最大流模板题
代码
#include <bits/stdc++.h>
#define ll long long
#define IOS std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
template<class T> inline void read(T &x){
x=0; register char c=getchar(); register bool f=0;
while(!isdigit(c))f^=c=='-',c=getchar();
while(isdigit(c))x=x*10+c-'0',c=getchar(); if(f)x=-x;
}
using namespace std;
ll n,m,cnt=2,s,t,inf=0x3f3f3f3f;
ll head[5005],dis[5005];
struct node
{
ll to,next,w;
}e[5005];
void add(ll u,ll v,ll w)
{
e[cnt].to=v;
e[cnt].w=w;
e[cnt].next=head[u];
head[u]=cnt++;
e[cnt].to=u;
e[cnt].w=0;
e[cnt].next=head[v];
head[v]=cnt++;
}
ll bfs()
{
for(int i=1;i<=n;i++){dis[i]=0;}
queue<ll> q;
q.push(s);
dis[s]=1;
while(!q.empty())
{
ll x=q.front();
q.pop();
for(int i=head[x];i;i=e[i].next)
{
ll v=e[i].to;
if(dis[v]==0&&e[i].w>0){
dis[v]=dis[x]+1;
q.push(v);
if(v==t)return 1;
}
}
}
return 0;
}
ll dfs(ll u,ll sum)
{
if(u==t)return sum;
ll k,res=0;
for(int i=head[u];i;i=e[i].next)
{
ll v=e[i].to;
if((dis[v]==dis[u]+1)&&e[i].w>0)
{
k=dfs(v,min(sum,e[i].w));
if(k==0)dis[v]=0;
e[i].w-=k;
e[i^1].w+=k;
res+=k;
sum-=k;
}
}
return res;
}
int main()
{
IOS
ll a,b,c,x;
cin>>n>>m>>x;
s=1;t=n;
for(int i=1;i<=m;i++)
{
cin>>a>>b>>c;
add(a,b,c);
}
ll ans=0;
while(bfs())
{ans+=dfs(s,inf);}
//cout<<ans<<endl;
if(ans==0)
{
cout<<"Orz Ni Jinan Saint Cow!"<<endl;
return 0;
}
if(x%ans==0)
{cout<<ans<<" "<<x/ans<<endl;}
else
{cout<<ans<<" "<<x/ans+1<<endl;}
return 0;
} 酒店之王
果然，网络流问题就像Y总说的那样，难在建图 ＞﹏＜
类似于一个三分图匹配，题目给出了客人和房间之前的关系、客人和饭菜之间的关系，未给出饭菜和房间之间的关系，因此以 源点->房间->客人->饭菜->汇点 类似于这种方式建图。然后还有很关键的一个问题，就是会出现下面这种情况
每条边的容量是1，这样跑出来的最大流是2，但题意是一个客人只能选择一个房间和一种饭菜饭菜，因此我们对客人进行拆点
这样就可以了
代码
#include <bits/stdc++.h>
#define ll long long
#define IOS std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
template<class T> inline void read(T &x){
x=0; register char c=getchar(); register bool f=0;
while(!isdigit(c))f^=c=='-',c=getchar();
while(isdigit(c))x=x*10+c-'0',c=getchar(); if(f)x=-x;
}
using namespace std;
int n,p,q;
vector<int>a[102],b[102];
struct node
{
int to,next,w;
}e[500005];
int head[500005],dis[500005],vis[303][303],cai[102],dian[102];
int cnt=2,s,t,inf=99999999;
void add(int u,int v,int w)
{
e[cnt].to=v;
e[cnt].w=w;
e[cnt].next=head[u];
head[u]=cnt++;
e[cnt].to=u;
e[cnt].w=0;
e[cnt].next=head[v];
head[v]=cnt++;
}
int bfs()
{
for(int i=1;i<=500;i++)dis[i]=0;
queue<int>q;
q.push(s);
dis[s]=1;
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].to;
if(dis[v]==0&&e[i].w>0)
{
dis[v]=dis[u]+1;
q.push(v);
if(v==t){return 1;}
}
}
}
return 0;
}
int dfs(int u,int sum)
{
if(u==t)return sum;
int k,res=0;
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].to;
if((dis[v]==dis[u]+1)&&e[i].w>0)
{
k=dfs(v,min(sum,e[i].w));
if(k==0)dis[v]=0;
e[i].w-=k;
e[i^1].w+=k;
res+=k;
sum-=k;
}
}
return res;
}
int main()
{
int x;
cin>>n>>p>>q;
s=401;t=402;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=p;j++){
cin>>x;
if(x==1){
a[i].push_back(j);
}
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=q;j++){
cin>>x;
if(x==1){
b[i].push_back(j);
}
}
}
/////////////////////////////////////////////////
for(int i=1;i<=n;i++)
{
if(a[i].size()==0||b[i].size()==0)continue;
for(int j=0;j<a[i].size();j++)
{
if(dian[a[i][j]]==0)
{
dian[a[i][j]]=1;
add(s,100+a[i][j],1);
}
add(a[i][j]+100,i,1);
}
add(i,i+200,1);
for(int j=0;j<b[i].size();j++)
{
if(cai[b[i][j]]==0)
{
cai[b[i][j]]=1;
add(300+b[i][j],t,1);
}
add(i+200,b[i][j]+300,1);
}
}
int ans=0;
while(bfs()){
ans+=dfs(s,inf);
}
cout<<ans<<endl;
return 0;
}
试题库问题
超级源点与试题建边，容量为1；试题与类型也建边，容量为1；类型与超级汇点建边，容量为题目所需的类型数量。然后跑最大流。最后的判断也要格外注意一下。
代码
#include <bits/stdc++.h>
#define ll long long
#define IOS std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
template<class T> inline void read(T &x){
x=0; register char c=getchar(); register bool f=0;
while(!isdigit(c))f^=c=='-',c=getchar();
while(isdigit(c))x=x*10+c-'0',c=getchar(); if(f)x=-x;
}
using namespace std;
int n,k,s,t,cnt=2,inf=0x3f3f3f;
int task[1005];
struct node
{
int to,next,w;
}e[500005];
int head[500005],dis[5005],vis[1002];
void add(int u,int v,int w)
{
e[cnt].to=v;
e[cnt].w=w;
e[cnt].next=head[u];
head[u]=cnt++;
e[cnt].to=u;
e[cnt].w=0;
e[cnt].next=head[v];
head[v]=cnt++;
}
int bfs()
{
for(int i=1;i<=4005;i++)dis[i]=0;
dis[s]=1;
queue<int>q;
q.push(s);
while(!q.empty())
{
int x=q.front();
q.pop();
for(int i=head[x];i;i=e[i].next)
{
int v=e[i].to;
if(dis[v]==0&&e[i].w>0)
{
dis[v]=dis[x]+1;
q.push(v);
if(v==t)return 1;
}
}
}
return 0;
}
int dfs(int x,int sum)
{
if(x==t)return sum;
int k,res=0;
for(int i=head[x];i;i=e[i].next)
{
int v=e[i].to;
if((dis[v]==dis[x]+1)&&e[i].w>0)
{
int minn=min(sum,e[i].w);
k=dfs(v,minn);
if(k==0){dis[v]=0;}
e[i].w-=k;
e[i^1].w+=k;
res+=k;
sum-=k;
}
}
return res;
}
int main()
{
s=3001,t=3003;
cin>>k>>n;
for(int i=1;i<=k;i++){
cin>>task[i];
}
int p,x;
for(int i=1;i<=n;i++)
{
cin>>p;
if(p==0){continue;}
add(s,i,1);
for(int j=1;j<=p;j++)
{
cin>>x;
add(i,x+1000,1);
vis[x]=1;
}
}
for(int i=1;i<=k;i++){
if(vis[i]==1){
add(1000+i,t,task[i]);
}
}
int ans=0;
while(bfs()){
ans+=dfs(s,inf);
}
int tt=0;
for(int i=1;i<=k;i++){
tt+=task[i];
}
if(ans<tt){cout<<"No solution!"<<endl;return 0;}
vector<int> c[1002];
for(int i=1;i<=k;i++)
{
for(int j=head[1000+i];j;j=e[j].next)
{
int v=e[j].to;
if(v==t)continue;
if(e[j].w>0){
c[i].push_back(v);
}
}
}
int flag=1;
for(int i=1;i<=k;i++){
if(c[i].size()<task[i]){
flag=0;break;
}
}
if(flag==0){cout<<"No solution!"<<endl;return 0;}
for(int i=1;i<=k;i++){
cout<<i<<": ";
for(int j=0;j<c[i].size();j++){
cout<<c[i][j]<<" ";
}
cout<<endl;
}
return 0;
}最小路径覆盖问题
二分图中，最小路径覆盖=点的总数 - 点之间的最大匹配数（网络最大流）
因此建一个二分图，超源与x建边，容量为1，x与y之前建边，容量为1，y与超汇之间建边，容量为1。然后跑一个最大流
代码
#include <bits/stdc++.h>
#define ll long long
#define IOS std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
template<class T> inline void read(T &x){
x=0; register char c=getchar(); register bool f=0;
while(!isdigit(c))f^=c=='-',c=getchar();
while(isdigit(c))x=x*10+c-'0',c=getchar(); if(f)x=-x;
}
using namespace std;
struct node
{
int to,next,w;
}e[500005];
int head[500005],dis[500005],vis[50005];
int in[2005],out[2005];
int cnt=2,n,m,s,t,inf=99999999;
void add(int u,int v,int w)
{
e[cnt].to=v;
e[cnt].w=w;
e[cnt].next=head[u];
head[u]=cnt++;
e[cnt].to=u;
e[cnt].w=0;
e[cnt].next=head[v];
head[v]=cnt++;
}
int bfs()
{
for(int i=1;i<=600;i++)dis[i]=0;
queue<int>q;
dis[s]=1;
q.push(s);
while(!q.empty()){
int x=q.front();
q.pop();
for(int i=head[x];i;i=e[i].next){
int v=e[i].to;
if(dis[v]==0&&e[i].w>0){
dis[v]=dis[x]+1;
q.push(v);
if(v==t){return 1;}
}
}
}
return 0;
}
int dfs(int x,int sum)
{
if(x==t)return sum;
int k,res=0;
for(int i=head[x];i;i=e[i].next)
{
int v=e[i].to;
if((dis[v]==dis[x]+1)&&e[i].w>0){
k=dfs(v,min(sum,e[i].w));
if(k==0)dis[v]=0;
e[i].w-=k;
e[i^1].w+=k;
res+=k;
sum-=k;
}
}
return res;
}
int main()
{
int x,y;
s=501;t=502;
cin>>n>>m;
for(int i=1;i<=m;i++)
{
cin>>x>>y;
if(vis[x]==0){
add(s,x,1);
vis[x]=1;
}
if(vis[y+200]==0){
add(200+y,t,1);
vis[y+200]=1;
}
add(x,y+200,1);
}
int ans=0;
while(bfs()){
ans+=dfs(s,inf);
}
for(int i=1+200;i<=150+200;i++){
for(int j=head[i];j;j=e[j].next){
if(e[j].w>0){
int u=e[j].to;
if(u==t)continue;
out[u]=i-200;
in[i-200]=u;
break;
}
}
}
//cout<<in[2]<<endl;
for(int i=1;i<=n;i++){
if(in[i]==0&&out[i]!=0){
int u=i;
while(u!=0){
cout<<u<<" ";
u=out[u];
}
cout<<endl;
}
}
cout<<n-ans<<endl;
return 0;
}
//4,9,16,25,36,49,64,81,100,121
123