NKOJ 4343 最小流：有源汇上下界 （上下界网络流）

发表于 |
字数统计: 610字 | 阅读时长 ≈ 3min

P4343最小流:有源汇上下界

问题描述

n 个点，m 条边，每条边 e有一个流量下界 lower(e) 和流量上界 upper(e)，给定源点 s 与汇点 t，求源点到汇点的最小流。

输入格式

第一行两个正整数 n、m、s、t。
之后的 m行，每行四个整数 s、t、lower、upper 。

输出格式

如果无解，输出一行 please go home to sleep。
否则输出最小流。

样例输入

7 12 6 7
6 1 0 2147483647
1 7 0 2147483647
6 2 0 2147483647
2 7 0 2147483647
6 3 0 2147483647
3 7 0 2147483647
6 4 0 2147483647
4 7 0 2147483647
6 5 0 2147483647
5 7 0 2147483647
5 1 1 2147483647
3 4 1 2147483647

样例输出

2

提示

1≤n≤50003,1≤m≤125003

上下界网络流模板题，然而此题有一组菊花图的数据，需要在SAP时避免重复讨论边，具体实现参见代码。处理菊花图非常的优秀

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#define N 150000
#define M 500000
using namespace std;
int TT,n,m,S,T,ans,lim,D[N],Lim,dis[N],cnt[N];
int TOT=1,LA[N],NE[M],EN[M],G[M],ty[M],H[M];
void ADD(int x,int y,int z,int c)
{
	TOT++;
	EN[TOT]=y;
	H[x]=TOT;
	G[TOT]=z;
	ty[TOT]=c;
	NE[TOT]=LA[x];
	LA[x]=TOT;
}
int SAP(int x,int f)
{
	int i,y,d=0,tmp;
	if(x==T)return f;
	for(i=LA[x];i;LA[x]=i=NE[i])//!!!!
	{
		y=EN[i];
		if(!G[i]||ty[i]>Lim||dis[x]!=dis[y]+1)continue;
		tmp=SAP(y,min(f-d,G[i]));
		d+=tmp;G[i]-=tmp;G[i^1]+=tmp;
		if(d==f||dis[S]>T)return d;
	}
	LA[x]=H[x];//!!!!
	if(!--cnt[dis[x]])dis[S]=T+1;
	cnt[++dis[x]]++;
	return d;
}
int main()
{
	int i,j,x,y,u,d,s,t;
	scanf("%d%d%d%d",&n,&m,&s,&t);
	for(i=1;i<=m;i++)
	{
		scanf("%d%d%d%d",&x,&y,&d,&u);
		ADD(x,y,u-d,1);ADD(y,x,0,1);
		D[x]-=d;D[y]+=d;
	}
	S=n+1;T=S+1;
	for(i=1;i<=n;i++)
	if(D[i]>0)ADD(S,i,D[i],1),ADD(i,S,0,1),lim+=D[i];
	else if(D[i]<0)ADD(i,T,-D[i],1),ADD(T,i,0,1);
	ADD(t,s,1e9,2);ADD(s,t,0,2);
	Lim=1;while(dis[S]<=T)ans+=SAP(S,1e9);
	memset(dis,0,sizeof(dis));
	memset(cnt,0,sizeof(cnt));
	Lim=2;
	while(dis[S]<=T)ans+=SAP(S,1e9);
	if(ans==lim)printf("%d",G[TOT]);
	else printf("please go home to sleep");
}