Analysis of typical examples of acm network flow and cost flow

introduction

The general difficulty of the problems of network flow and cost flow type lies in drawing. This paper mainly summarizes the various difficulties encountered by the author in the process of doing exercises and explains them in the form of examples.

On the relevant principles of network flow and cost flow, many blogs written in great detail can be found on the Internet. This paper will not repeat the relevant knowledge points. This paper will give more examples to analyze, and be familiar with how to turn the topic into a graph and how to build a graph skillfully. Here are some well written blogs for reference.
Network flow fee flow introduction blog reference:
https://blog.csdn.net/yjr3426619/article/details/82808303
https://blog.csdn.net/x_y_q_/article/details/51999466
https://blog.csdn.net/Tramp_1/article/details/52618334
https://blog.csdn.net/A_Comme_Amour/article/details/79356220

Example analysis

Example 1
Source: International Collegiate Programming Contest (ACM-ICPC) World Finals 2015 Question C: Catering
Question surface:


Given a graph with n+1(1 ≤ n ≤ 100)\mathbf{n+1(1\le n\le 100)}n+1(1 ≤ n ≤ 100) points (the number of points starts from 0), for any two points i, j (i < j) \ mathbf {i, j (i < j)} i, j (i < j), there is a directed edge from i to j (with edge weight 0 ≤ edge weight ≤ 1000000\mathbf{0\le edge weight \ Le 1000000} 0 ≤ edge weight ≤ 1000000). There are k people starting from point 0. Everyone can walk along any edge to a point (it can be point 0, that is, not moving). It is required that there is exactly one person passing through any point i(1 ≤ i ≤ n)\mathbf{i(1\le i\le n)}i(1 ≤ i ≤ n). Ask everyone what the maximum sum of edge weights they pass through.

Problem solution: the difficulty of this problem lies in drawing. In fact, if you master the method of model transformation, you can make this problem without understanding the principle of network flow. Analyze the characteristics of the graph of this problem, and assume that the trajectory formed by everyone walking is a new graph. In this graph, the exit degree of point 0 is less than or equal to K (not 0), and the other points are divided into two types. For non end points, the entry degree and exit degree of points are equal to 1, the entry degree of end points is 1, and the exit degree is 0. Therefore, as long as we can construct a graph that meets this access relationship and maximize the weight sum of the graph.
Consider establishing the following network flow model:
For each point i(i ≤ n)\mathbf{i(i\le n)}i(i ≤ n), a mirror node i ′ = i+n\mathbf{i'=i+n}i ′ = i+n is established. In this way, the edge connection relationship is changed from I − > J \ mathbf {I - > J} I − > J to I − > J' \ mathbf {I - > J '} I − > J', but the edge connection mode of network flow has to be changed. The capacity is set to 1 and the cost is set to the original edge weight. Then let the source point s and sink point t connect an edge with capacity k and cost 0 from point s to node 0, and an edge with capacity 1 and cost 0 to nodes 1~n. For all N + 1~n + n nodes, connect an edge with capacity of 1 and cost of 0 to point t. The schematic diagram of edge connection is shown in Figure 1 below:

So why is it legal to connect the sides in this way. First of all, the exit degree of point 0 must be less than or equal to k, because the maximum flow from point s is only k. in addition, the only flow at point n+1 can only come from point 0. This edge (referring to the edge of 0 − > n+1) \ mathbf{(referring to the edge of 0 - > n+1)} (referring to the edge of 0 − > n+1) must be calculated into the maximum flow, so the exit degree of point 0 is at least 1, which is all legal. Considering the penetration of each point in the original diagram except point 0, since the flow from point s is not less than the maximum flow into point t, the nodes n+1~n+n will contribute flow to point T. due to the restriction that the flow of each node is 1, and the flow of nodes n+1~n+n must come from 0 ~ n-1, which is equivalent to the penetration of nodes 1~n in the original diagram is 1. The outgoing degree of each node (1~n) in the original figure can be 0 or 1, which corresponds to the edge connection relationship between nodes 1~n and nodes n+1~n+n in the network flow (if there is no edge connection, it is 0, otherwise it is 1, because the maximum traffic of nodes 1~n is 1, the maximum outgoing degree is 1)
In general, the graph formed by the network flow has a legal edge connection. Since the maximum flow is n, it is obvious that the cost flow must be the largest in all cases. After the map is built, you only need to run the maximum flow from s to t.

code:

#include <bits/stdc++.h>
#define FOR(i,a,b) for(register int i=(a);i<(b);++i)
#define ROF(i,a,b) for(register int i=(a);i>=(b);--i)
#define pi pair<int,int>
#define mk(a,b) make_pair(a,b)
#define mygc(c) (c)=getchar()
#define mypc(c) putchar(c)
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef double db;
const int maxn = 400;
const int maxm = 200005;
const int inf = 2147483647;
typedef long long ll;
const double eps = 1e-9;
const long long INF = 9223372036854775807ll;
ll qpow(ll a,ll b,ll c){ll ans=1;while(b){if(b&1)ans=ans*a%c;a=a*a%c;b>>=1;}return ans;}
inline void rd(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
inline void rd(ll *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
inline void rd(db *x){scanf("%lf",x);}
inline int rd(char c[]){int i,s=0;for(;;){mygc(i);if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF) break;}c[s++]=i;for(;;){mygc(i);if(i==' '||i=='\n'||i=='\r'||i=='\t'||i==EOF) break;c[s++]=i;}c[s]='\0';return s;}
inline void rd(int a[],int n){FOR(i,0,n)rd(&a[i]);}
inline void rd(ll a[],int n){FOR(i,0,n)rd(&a[i]);}
template <class T, class S> inline void rd(T *x, S *y){rd(x);rd(y);}
template <class T, class S, class U> inline void rd(T *x, S *y, U *z){rd(x);rd(y);rd(z);}
template <class T, class S, class U, class V> inline void rd(T *x, S *y, U *z, V *w){rd(x);rd(y);rd(z);rd(w);}
inline void wr(int x){if(x < 10) putchar('0' + x); else wr(x / 10), wr(x % 10);}
inline void wr(int x, char c){int s=0,m=0;char f[10];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
inline void wr(ll x, char c){int s=0,m=0;char f[20];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
inline void wr(db x, char c){printf("%.15f",x);mypc(c);}
inline void wr(const char c[]){int i;for(i=0;c[i]!='\0';i++)mypc(c[i]);}
inline void wr(const char x[], char c){int i;for(i=0;x[i]!='\0';i++)mypc(x[i]);mypc(c);}
template<class T> inline void wrn(T x){wr(x,'\n');}
template<class T, class S> inline void wrn(T x, S y){wr(x,' ');wr(y,'\n');}
template<class T, class S, class U> inline void wrn(T x, S y, U z){wr(x,' ');wr(y,' ');wr(z,'\n');}
template<class T, class S, class U,class H> inline void wrn(T x, S y, U z,H h){wr(x,' ');wr(y,' ');wr(z,' ');wr(h,'\n');}
template<class T> inline void wra(T x[], int n){int i;if(!n){mypc('\n');return;}FOR(i,0,n-1)wr(x[i],' ');wr(x[n-1],'\n');}
struct MCMF{
	int h[maxn],ee,n,m,maxflow=0,mincost=0,flow[maxn],cost[maxn],father[maxn],inq[maxn];
	struct Edge{
		int v,w,c,next;
	}edge[maxm];
	queue<int> q;
	void init(int nn){
		n=nn;
		memset(h,-1,sizeof(int)*(nn+1));
	}
	void addedge(int u,int v,int w,int c){
		edge[ee]=Edge{v,w,c,h[u]};
		h[u]=ee++;
		edge[ee]=Edge{u,0,-c,h[v]};
		h[v]=ee++;
	}
	bool bfs(int s,int t){
		memset(flow,0,sizeof(int)*(n+1));
		memset(cost,0x3f,sizeof(int)*(n+1));
		memset(inq,0,sizeof(int)*(n+1));
		while(!q.empty())q.pop();
		cost[s]=0;
		q.push(s);
		inq[s]=1;
		flow[s]=inf;
		while(!q.empty()){
			int u=q.front();
			q.pop();
			for(int i=h[u];i!=-1;i=edge[i].next){
				if(edge[i].w && cost[edge[i].v]>cost[u]+edge[i].c){
					cost[edge[i].v]=cost[u]+edge[i].c;
					flow[edge[i].v]=min(flow[u],edge[i].w);
					father[edge[i].v]=i;
					if(!inq[edge[i].v]){
						inq[edge[i].v]=1;
						q.push(edge[i].v);
					}
				}
			}
			inq[u]=0;
		}
		return flow[t]>0; 
	}
	int sfpa(int s,int t){
		while(bfs(s,t)){
			maxflow+=flow[t];
			mincost+=cost[t]*flow[t];
			int i=father[t];
			edge[i].w-=flow[t];
			edge[i^1].w+=flow[t];
			while(edge[i^1].v!=s){
				i=father[edge[i^1].v];
				edge[i].w-=flow[t];
				edge[i^1].w+=flow[t];
			}
		}
		return mincost;
	}
}mcmf;

int main(){
	int n,k,s,t;
	rd(&n,&k);
	mcmf.init(2*n+2);
	s=2*n+1,t=2*n+2;
	FOR(i,0,n){
		if(!i)mcmf.addedge(s,i,k,0);else mcmf.addedge(s,i,1,0);
		mcmf.addedge(i+n+1,t,1,0);
		FOR(j,i+1,n+1){
			int x;
			rd(&x);
			mcmf.addedge(i,j+n,1,x);
		}
	}
	wrn(mcmf.sfpa(s,t));
}

Example 2
To be added...

Tags: Algorithm Graph Theory ICPC

Posted by newzub on Sun, 22 May 2022 16:31:05 +0300