OI - 排水water（团队互测） | Lucky_Glass's Blog

以心为名，名为爱惜

0%

OI - 排水water（团队互测）

发表于 更新于 分类于 Valine：

关于网络流还有很多

# 题面

点击展开/折叠 题意

给定一张不完整的 $n$ 个点、$m$ 条边的费用流图（$1\le n\le 500,1\le m\le50000$，费用流图随机构造），其中每条边只给定起始点 $u_i$、结束点 $v_i$ 以及单位流量的费用 $c_i$，但不给定容量。源点为 $1$ 汇点为 $n$。

然后进行 $T$ 次询问 $T\le10^5$，每次询问给定一个分数 $\tfrac xy$，意为：使费用流图的每一条边的容量都为 $\tfrac xy$，从源点流出一单位的流量，求最小费用流（若不能流完一单位的流量，输出 $-1$）。

# 解析

因为网络流图只要发生变化（如增删边、改容量/代价），就很难快速的重新计算最小费用流，我们希望费用流图中的容量是固定的。于是第一步关键转化是将题目转化为：

每条边容量为 $1$，每次询问从源点流出 $\tfrac yx$ 的流量，求最小费用流。

相当于把流量扩大了 $\tfrac yx$ 倍，当然最后算出来的答案还要乘上 $\tfrac xy$ 变回来。

于是下一个问题就是如何快速处理出不同流量的最小费用流？

考虑单路增广（弱化 Dinic 算法），若还有 $t\ge1$ 的流量未从源点流出且还可以增广，则下一次增广流出的流量一定是 $1$（沿着一条最短路增广）；若未流出的流量 $t<1$，则最后一次增广，延最短路流出 $t$ 的流量——可以理解为仍然流出 $1$ 的流量，然后增广的费用乘上 $t$。

于是可以先对原费用流图进行单路增广直到不能增广，记录每次增广的代价。贪心地想，假如需要流出的流量是 $\tfrac ab$，则一定是取代价前 $\lfloor\tfrac ab\rfloor$ 小的增广方案，每次增广流量 $1$；若还剩余流量 $\tfrac{a\bmod b}{b}$，则取下一个代价最小的增广方案，其代价乘上 $\tfrac{a\bmod b}{b}$ 加入总代价。

当然发现流量流不完时输出 $-1$。

所以对每次增广的费用排序后作前缀和就可以 $O(1)$ 回答询问。

# 源代码

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
/*Lucky_Glass*/
#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

inline int Read(){
	register int r=0,c=getchar();
	while(c<'0' || '9'<c) c=getchar();
	while('0'<=c && c<='9') r=(r<<1)+(r<<3)+(c^'0'),c=getchar();
	return r;
}

const int N=510,M=5e4+10;
#define ci const int &

struct GRAPH{
	int head[N],to[M<<1],nxt[M<<1],cap[M<<1],cst[M<<1],ncnt;
	GRAPH(){ncnt=1;}
	void AddEdge(ci u,ci v,ci ca,ci cs){
		int p=++ncnt,q=++ncnt;
		to[p]=v,nxt[p]=head[u],cap[p]=ca,cst[p]=cs,head[u]=p;
		to[q]=u,nxt[q]=head[v],cap[q]=0,cst[q]=-cs,head[v]=q;
	}
	inline int operator [](ci u){return head[u];}
}Gr;

int n,m;
vector<long long> aug,pre;
bool inq[N];
int to[N],eid[N];
long long dis[N];

queue<int> que;
bool SPFA(){
	memset(dis,0x3f,sizeof dis);
	long long inf=dis[0];
	que.push(1),dis[1]=0;
	while(!que.empty()){
		int u=que.front();que.pop();
		inq[u]=false;
		for(int it=Gr[u];it;it=Gr.nxt[it]){
			int v=Gr.to[it];
			if(Gr.cap[it]<=0 || dis[v]<=dis[u]+Gr.cst[it]) continue;
			dis[v]=dis[u]+Gr.cst[it];
			to[v]=u,eid[v]=it;
			if(!inq[v]) inq[v]=true,que.push(v);
		}
	}
	return dis[n]<inf;
}
void Dinic(){
	while(SPFA()){
		int s=n;
		long long tot=0;
		while(s!=1){
			tot+=Gr.cst[eid[s]];
			Gr.cap[eid[s]]--,Gr.cap[eid[s]^1]++;
			s=to[s];
		}
		aug.push_back(tot);
	}
}
long long GCD(long long a,long long b){return b? GCD(b,a%b):a;}
int main(){
	freopen("water.in","r",stdin);
	freopen("water.out","w",stdout);
	n=Read(),m=Read();
	for(int i=1;i<=m;i++){
		int u=Read(),v=Read(),w=Read();
		Gr.AddEdge(u,v,1,w);
	}
	Dinic();
	if(!aug.empty()){
		sort(aug.begin(),aug.end());
		pre.push_back(aug.front());
		for(int i=1,I=aug.size();i<I;i++)
			pre.push_back(pre.back()+aug[i]);
	}
	int cas=Read();
	while(cas--){
		int x=Read(),y=Read();
		if((long long)aug.size()*x<y){printf("-1\n");continue;}
		long long p=y/x? 1ll*x*pre[y/x-1]:0,q=y;
		if(y%x) p+=1ll*aug[y/x]*(y%x);
		long long gcd=GCD(p,q);
		p/=gcd,q/=gcd;
		printf("%lld/%lld\n",p,q);
	}
	return 0;
}

THE END

Thanks for reading!