网络流练习

清疚 2021-11-05 22:28 330阅读 0赞

最大流dinic模板

const int N = 1e6+10;
    int n, m, S, T;
    struct edge {
        int v,w,next;
    } e[N];
    int head[N], dep[N], vis[N], cur[N], cnt=1;
    queue<int> Q;
    void add(int u, int v, int w) {
        e[++cnt] = {v,w,head[u]};
        head[u] = cnt;
        e[++cnt] = {u,0,head[v]};
        head[v] = cnt;
    }
    int bfs() {
        REP(i,1,T) dep[i]=INF,vis[i]=0,cur[i]=head[i];
        dep[S]=0,Q.push(S);
        while (Q.size()) {
            int u = Q.front(); Q.pop();
            for (int i=head[u]; i; i=e[i].next) {
                if (dep[e[i].v]>dep[u]+1&&e[i].w) {
                    dep[e[i].v]=dep[u]+1;
                    Q.push(e[i].v);
                }
            }
        }
        return dep[T]!=INF;
    }
    int dfs(int x, int w) {
        if (x==T) return w;
        int used = 0;
        for (int i=cur[x]; i; i=e[i].next) {
            cur[x] = i;
            if (dep[e[i].v]==dep[x]+1&&e[i].w) {
                int flow = dfs(e[i].v,min(w-used,e[i].w));
                if (flow) {
                    used += flow;
                    e[i].w -= flow;
                    e[i^1].w += flow;
                    if (used==w) break;
                }
            }
        }
        return used;
    }
    int dinic() {
        int ans = 0;
        while (bfs()) ans+=dfs(S,INF);
    	return ans;
    }

最小费用最大流EK+spfa模板

int n, m, k;
    struct _ {int from,to,w,f;};
    vector<_> E;
    vector<int> g[N];
    int a[N], pre[N], inq[N], d[N];
    int mf,mc;
    queue<int> q;
    void add(int x, int y, int c, int w) {
    	g[x].pb(E.size());
    	E.pb({x,y,c,w});
    	g[y].pb(E.size());
    	E.pb({y,x,0,-w});
    }
    void mfmc(int S, int T) {
    	while (1) {
    		REP(i,1,n) a[i]=d[i]=INF,inq[i]=0;
    		q.push(S),d[S]=0;
    		while (!q.empty()) {
    			int x=q.front(); q.pop();
    			inq[x] = 0;
    			for (auto t:g[x]) {
    				auto e=E[t];
    				if (e.w>0&&d[e.to]>d[x]+e.f) {
    					d[e.to]=d[x]+e.f;
    					pre[e.to]=t;
    					a[e.to]=min(a[x],e.w);
    					if (!inq[e.to]) {
    						inq[e.to]=1;
    						q.push(e.to);
    					}
    				}
    			}
    		}
    		if (a[T]==INF) break;
    		for (int u=T;u!=S;u=E[pre[u]].from) {
    			E[pre[u]].w-=a[T];
    			E[pre[u]^1].w+=a[T];
    		}
    		mf+=a[T],mc+=a[T]*d[T];
    	}
    }

最小费用最大流dinic+spfa

const int N = 5e4+10,S=N-2,T=N-1;
    int n,m,cost,flow;
    struct edge {
        int to,next,w,v;
        edge(int to=0,int next=0,int w=0,int v=0):to(to),next(next),w(w),v(v){}
    } e[N<<1];
    int head[N],dep[N],vis[N],cnt=1;
    queue<int> Q;
    
    int spfa() {
    	REP(i,1,n) dep[i]=INF,vis[i]=0;
    	dep[T]=INF;
        dep[S]=0,Q.push(S);
        while (Q.size()) {
            int u = Q.front(); Q.pop();
    		vis[u] = 0;
    		for (int i=head[u]; i; i=e[i].next) {
    			if (e[i].w&&dep[e[i].to]>dep[u]+e[i].v) {
    				dep[e[i].to]=dep[u]+e[i].v;
    				if (!vis[e[i].to]) { 
    					vis[e[i].to]=1;
    					Q.push(e[i].to);
    				}
    			}
    		}
        }
        return dep[T]!=INF;
    }
    int dfs(int x, int w) {
        if (x==T) {
            cost = cost+w*dep[T];
            flow += w;
            return w;
        }
    	vis[x] = 1;
    	int used = 0;
        for (int i=head[x]; i; i=e[i].next) {
            if (!vis[e[i].to]&&dep[e[i].to]==dep[x]+e[i].v&&e[i].w) {
                int f = dfs(e[i].to,min(w-used,e[i].w));
    			if (f) {
    				used += f;
    				e[i].w -= f;
    				e[i^1].w += f;
    				if(used==w) break;
    			}
            }
    	}
        return used;
    }
    void dinic(){
        while(spfa()) dfs(S,INF);
    }
    void add(int x,int y,int k,int v) {
        e[++cnt] = edge(y,head[x],k,v);
    	head[x] = cnt;
    	e[++cnt] = edge(x,head[y],0,-v);
    	head[y] = cnt;
    }

练习1. luogu P1402 酒店之王

大意:$n$个客人, $p$个房间, $q$个菜, 给定每个客人的喜好, 一个客人满意当且仅当他住到喜欢的房间吃到喜欢的菜. 求一个分配, 使得满意的客人尽量多, 输出满意的客人个数.

刚开始想着直接连边跑最大匹配, 但是这样的话一个客人可能算多次, 所以将客人拆点限制流量不超过1即可.

int main() {
    	scanf("%d%d%d", &n, &p, &q);
    	REP(i,1,n) REP(j,1,p) scanf("%d",a[i]+j);
    	REP(i,1,n) REP(j,1,p) scanf("%d",b[i]+j);
    	S = p+q+2*n+1, T = S+1;
    	REP(i,1,p) add(S,i,1);
    	REP(i,1,q) add(i+p,T,1);
    	REP(i,p+q+1,p+q+n) add(i,i+n,1);
    	REP(i,1,n) { 
    		REP(j,1,p) if (a[i][j]) add(j,p+q+i,1);
    		REP(j,1,q) if (b[i][j]) add(p+q+n+i,j+p,1);
    	}
    	int ans = 0;
    	while (bfs()) ans+=dfs(S,INF);
    	printf("%d\n", ans);
    }

练习2. luogu P2604 \[ZJOI2010\]网络扩容

大意: 给定一张有向图，每条边都有一个容量C和一个扩容费用W。这里扩容费用是指将容量扩大1所需的费用。求： 1、 在不扩容的情况下，1到N的最大流； 2、 将1到N的最大流增加K所需的最小扩容费用。

第二问在残量网络上每条边容量增加INF, 费用为w, 再增加源点S, 向1连容量k的边来限流

int main() {
    	scanf("%d%d%d", &n, &m, &k);
    	REP(i,1,m) {
    		scanf("%d%d%d%d",uu+i,vv+i,cc+i,ww+i);
    		add(uu[i],vv[i],cc[i],0);
    	}
    	mfmc(1,n);
    	printf("%d ",mf);
    	add(n+1,1,k,0);
    	REP(i,1,m) add(uu[i],vv[i],k,ww[i]);
    	mfmc(n+1,n);
    	printf("%d\n",mc);
    }

练习3. luogu P2153 \[SDOI2009\]晨跑

大意: 给定有向图, 求1->n最多能找出多少条不相交的路径, 使得路径经过除1和n以外的点最多1次. 在路径数最多的前提下, 求总路劲最短是多少.

关键是要保证路径不能相交, 把每个点拆开, 限流为1即可.

int main() {
    	scanf("%d%d", &n, &m);
    	REP(i,1,n) add(i,i+n,1,0);
    	REP(i,1,m) { 
    		int u,v,w;
    		scanf("%d%d%d",&u,&v,&w);
    		add(u+n,v,1,w);
    	}
    	mfmc(n+1,n);
    	printf("%d %d\n",mf,mc);
    }

### ###

转载于:https://www.cnblogs.com/uid001/p/10896748.html