3597: [Scoi2014]方伯伯运椰子

时间:2022-12-16 13:41:43

3597: [Scoi2014]方伯伯运椰子

Time Limit: 30 Sec   Memory Limit: 64 MB
Submit: 388   Solved: 239
[ Submit][ Status][ Discuss]

Description

 3597: [Scoi2014]方伯伯运椰子

Input

 第一行包含二个整数N,M

接下来M行代表M条边,表示这个交通网络
每行六个整数,表示Ui,Vi,Ai,Bi,Ci,Di
接下来一行包含一条边,表示连接起点的边

Output

一个浮点数,保留二位小数。表示答案,数据保证答案大于0

Sample Input

5 10
1 5 13 13 0 412
2 5 30 18 396 148
1 5 33 31 0 39
4 5 22 4 0 786
4 5 13 32 0 561
4 5 3 48 0 460
2 5 32 47 604 258
5 7 44 37 75 164
5 7 34 50 925 441
6 2 26 38 1000 22

Sample Output

103.00

HINT

 1<=N<=5000


0<=M<=3000

1<=Ui,Vi<=N+2

0<=Ai,Bi<=500

0<=Ci<=10000

0<=Di<=1000

Source

[ Submit][ Status][ Discuss]

很显然是分数规划,假设当前二分的答案为ans
那么X - Y >= k*ans 即 Y + k*ans <= X
首先,题目保证了ans > 0,那么不等式成立,当Y < X,也就是能构造出更优的解
然后这张图给人很明显的网络流即视感--尝试构图
一开始整张图是满流的,,我们能做的,是修改一些边的容量,但是又得保证最大流不变
假设扩充了一条边的容量,,那么相邻一定要有条边相应减少--这样找下去一定会出一个环
对于原图的每条边(x,y,a,b,c,d)
从x到y连一条权值为b + d的边,代表容量扩充的费用
从y到x连一条权值为a - d的边,代表容量缩小的费用,该边仅当c > 0时存在
假如图中存在一个负环,那么修改流量时沿着这个环绕一圈,答案一定更优
而且因为容量限制,这个环不能无限绕,,所以是合法的
那么二分答案,对应修改边权,最后用SPFA判断是否存在负环就行了
据说这个叫绕圈法??
#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
#include<bitset>
#include<algorithm>
#include<cstring>
#include<map>
#include<stack>
#include<set>
#include<cmath>
#include<ext/pb_ds/priority_queue.hpp>
using namespace std;

const int maxn = 5E3 + 50;
typedef double DB;
const DB INF = 1E14;

struct E{
	int to; DB w; E(){}
	E(int to,DB w): to(to),w(w){}
}edgs[maxn*20];

int n,m,cnt,s;
DB dis[maxn];
bool vis[maxn];

vector <int> v[maxn];

void Add(int x,int y,DB w)
{
	v[x].push_back(cnt);
	edgs[cnt++] = E(y,w);
}

bool SPFA(int x)
{
	for (int i = 0; i < v[x].size(); i++) {
		E e = edgs[v[x][i]];
		if (dis[e.to] > dis[x] + e.w) {
			dis[e.to] = dis[x] + e.w;
			if (vis[e.to]) return 1;
			vis[e.to] = 1;
			bool flag = SPFA(e.to);
			if (flag) return 1;
		}
	}
	vis[x] = 0;
	return 0;
}

bool Judge(DB now)
{
	for (int i = 0; i < cnt; i++) edgs[i].w += now;
	for (int i = 1; i <= n; i++)
		dis[i] = INF,vis[i] = 0;
	dis[s] = 0; vis[s] = 1;
	bool flag = SPFA(s);
	for (int i = 0; i < cnt; i++) edgs[i].w -= now;
	return flag;
}

int main()
{
	#ifdef DMC
		freopen("DMC.txt","r",stdin);
	#endif
	
	cin >> n >> m; n += 2; s = n - 1;
	for (int i = 1; i <= m; i++) {
		int x,y,a,b,c,d;
		scanf("%d%d%d%d%d%d",&x,&y,&a,&b,&c,&d);
		Add(x,y,b + d);
		if (c) Add(y,x,a - d);
	}
	
	DB L = 0,R = 1E12;
	for (int I = 0; I < 50; I++) {
		DB mid = (L + R) / 2.00;
		if (Judge(mid)) L = mid;
		else R = mid;
	}
	printf("%.2lf",(L + R)/2.00);
	return 0;
}