网络流

31

EK

#include<iostream>
#include<vector>
#include<cstring>
#include<queue>
#include<climits>
using namespace std;
#define N 10002
#define ff(a,b,c) for(int a=b;a<=c;a++)

typedef long long ll;
int n,m,s,t;
struct{
	int u,v;ll w;
} edges[N];
int last[N];
ll flow[N];
int tot;
vector<int> to[N];
int exists[201][201];
inline void add_edge(int u,int v,ll w){
	to[u].push_back(tot);
	edges[tot++]={
		u,v,w
	};
	
	
}
bool bfs(){
	queue<int> q;
	memset(kast,0xFF,sizof(int)*(n+1));
	flow[s]=LLONG_MAX;
	q.push(s);
	while(!q.empty()){
		int cur=q.front();
		q.pop();
		if(cur==t) break;
		for(auto e: to[cur]){
			int v=edges[e].v;ll w=edges[e].w;
			if(w>0&&last[v]==-1){
				last[v]=e;
				flow[v]=min(flow[cur], w);
				q.push(v);
			}
		}
	}
	return last[t]!=-1;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>m>>s>>t;
	ff(i,1,m){
		int u,v;ll w;
		cin>>u>>v>>w;
		add_edge(u,v,w);	
		add_edge(v,u,0);
	}
	ll maxf=0;
	while(bfs()){
		maxf+=flow[t];
		for(int i=t;i!=s;i=edges[last[i]].u){
			int cur=last[i];
			edges[cur].w -= flow[t];
			edges[cur^1].w += flow[t];
		}
	}
	cout<<maxf;
}

Dinic

// Problem: P3376 【模板】网络最大流
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3376
// Memory Limit: 128 MB
// Time Limit: 1000 ms

#include<iostream>
#include<vector>
#include<cstring>
#include<queue>
#include<climits>
using namespace std;
#define N 10002
#define ff(a,b,c) for(int a=b;a<=c;a++)

typedef long long ll;
int n,m,s,t;
struct{
	int u,v;ll w;
} edges[N];
int dep[N];
int tot;
vector<int> to[N];
inline void add_edge(int u,int v,ll w){
	to[u].push_back(tot);
	edges[tot++]={
		u,v,w
	};
}
int fir[N];
ll dfs(int u,ll flow){
	if(u==t||!flow) return flow;
	ll curf=0;
	
	for(auto i=to[u].begin()+fir[u];i!=to[u].end();i++){
		int e=*i;
		fir[u]++;
		int v=edges[e].v;ll w=edges[e].w;
		if(dep[v]!=dep[u]+1) continue;
		ll f=dfs(v, min(w, flow-curf));
		if(!f) continue;
		curf+=f;
		edges[e].w-=f;
		edges[e^1].w+=f;
		if(curf==flow) break;
	}
	return curf;
	
}

bool bfs(){
	queue<int> q;
	memset(dep,0,sizeof(int)*(n+1));
	
	dep[s]=1;
	q.push(s);
	while(!q.empty()){
		int cur=q.front();
		q.pop();
		for(auto e: to[cur]){
			int v=edges[e].v;ll w=edges[e].w;
			if(!dep[v]&&w>0){
				dep[v]=dep[cur]+1;
				q.push(v);
			}
		}
		if(to[cur].size()) iter_swap(to[cur].begin(), to[cur].end()-1);
	}
	return dep[t]!=0;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>m>>s>>t;
	ff(i,1,m){
		int u,v;ll w;
		cin>>u>>v>>w;
		add_edge(u,v,w);	
		add_edge(v,u,0);
	}
	ll maxf=0;
	while(bfs()){
		memset(fir,0,sizeof(int)*(n+1));
		maxf+=dfs(s,LLONG_MAX);
	}
	cout<<maxf;
}

费用流(基于Dinic)

// Problem: P3381 【模板】最小费用最大流
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3381
// Memory Limit: 128 MB
// Time Limit: 1000 ms

#include<iostream>
#include<vector>
#include<cstring>
#include<queue>

#define N 5005
#define M 100005
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
typedef struct{
	int u,v;
	int w,c;
} edge;
int tot;
int dis[N],vis[N];
edge edges[M];
vector<int> to[N];
inline void add_edge(int u,int v,int w,int c){
	edges[tot]={
		u,v,w,c
	};
	to[u].push_back(tot++);
}
typedef struct hi{
	int c;int v;
	bool operator <(const hi &x) const {
		return c>x.c;
	}
} hi;
int n,m,s,t;
int h[N];
void spfa(){
	queue<int> q;
	q.push(s);
	memset(h,0x3F,sizeof(int)*(n+1));
	memset(vis,0,sizeof(int)*(n+1));
	h[s]=0;
	vis[s]=1;
	while(!q.empty()){
		int cur=q.front();
		q.pop();
		vis[cur]=0;
		for(auto e:to[cur]){
			int v=edges[e].v,w=edges[e].w, c=edges[e].c,u=edges[e].u;
			if(w&&h[v]>h[u]+c){
				h[v]=h[u]+c;
				if(!vis[v]){
					vis[v]=1;
					q.push(v);
				}
			}
		}
	}
}
int last[N];
bool bfs(){
	
	priority_queue<hi> q;
	q.push({0,s});
	memset(dis,0x3F,sizeof(int)*(n+1));
	memset(vis,0,sizeof(int)*(n+1));
	memset(last,0xFF,sizeof(int)*(n+1));
	dis[s]=0;
	while(!q.empty()){
		auto k=q.top();
		q.pop();
		int cur=k.v;
		if(vis[cur]) continue;
		vis[cur]=1;
		
		for(auto e:to[k.v]){
			int v=edges[e].v,u=edges[e].u,c=edges[e].c;
			if(edges[e].w&&dis[v]>dis[u]+c+h[u]-h[v]){
				dis[v]=dis[u]+c+h[u]-h[v];
				last[v]=e;
				if(!vis[v]){
					q.push({dis[v],v});
				}
			}
			
		}
		
	}
	return last[t]!=-1;
	// return dis[t]!=INF;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);
	cin>>n>>m>>s>>t;
	for(int i=1;i<=m;i++){
		int u,v;int w,c;
		cin>>u>>v>>w>>c;
		add_edge(u,v,w,c);
		add_edge(v,u,0,-1*c);
	}
	spfa();
	int maxflow=0,mincost=0;
	// int te=5;
	
	while(bfs()){
		int maxf=INF,cc=0;
		for(int i=1;i<=n;i++) h[i]+=dis[i];
		for(int i=last[t];i!=-1;i=last[edges[i].u]){
			
			maxf=min(maxf, edges[i].w);
		}
		for(int i=last[t];i!=-1;i=last[edges[i].u]){
			edges[i].w-=maxf;
			edges[i^1].w+=maxf;
		}
		for(int i=last[t];i!=-1;i=last[edges[i].u]){
			cc+=edges[i].c;
		}
		maxflow+=maxf;
		mincost+=maxf*cc;
	}
	cout<<maxflow<<" "<<mincost;
}