BZOJ4669 抢夺（网络流）

题目描述

大战将至, 美国决定实行计划经济。美国西部总共有 N 个城市，编号为 0 ∼ N − 1，以及 M 条道路，道路是单向的。其中城市 0 是一个大城市，里面住着 K 个人，而城市 N − 1 是一个农业城市。现在所有城市 0 的居民都需要到城市 N − 1 去领取食物。由于担心体力不支，所以居民都会采取开车的形式出行。但道路不是无限宽的，对于一条道路，会有 ci 的限制，表示在同一天内，最多只能有 ci 辆车同时在这条道路上行驶。一条道路的长度为 1，每辆车的行驶速度也可以假定为 1 每天。城市 N − 1 会在每个居民都到达后马上开始发放食物。现在 Reddington 想知道，假如在最优安排下，居民最早能在多少天后领到食物。假如没有居民那就不需要发放食物，默认为第 0 天。

数据范围

(1 le N le 1000, 1 le M le 5000, 0 le K le10^9)
(0 le u, v lt N, 1 le ci le 109，数据组数不超过 10 组)

解题思路

不太一样的题目

首先一眼网络流并有了一个非常暴力的思路，将图按时间分层跑最大流，但事实上太慢了跑不过去

给一个新奇的做法

贪心的想肯定是走最短路好啊，但最短路可能会拥挤，会有很多人等待导致答案不优，如果我们选择多条较短路一起走呢

设当前所有路径的流量和是 (f)，走完最长的“较短路”要用时间 (t) ，t 时间过后所有人都按着这些路径每天都可以走流量的人

考虑每次增广一条路径，上次的路径长度是 (T')，这次路径长度是 (T)，那么走完这次路径新增的人是 ((T-T')*sum)

代码

#include <queue>
#include <vector>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MP make_pair
#define ll long long
#define fi first
#define se second
using namespace std;

template <typename T>
void read(T &x) {
    x = 0; bool f = 0;
    char c = getchar();
    for (;!isdigit(c);c=getchar()) if (c=='-') f=1;
    for (;isdigit(c);c=getchar()) x=x*10+(c^48);
    if (f) x=-x;
}

template<typename F>
inline void write(F x)
{
	static short st[30];short tp=0;
	if(x<0) putchar('-'),x=-x;
	do st[++tp]=x%10,x/=10; while(x);
	while(tp) putchar('0'|st[tp--]);
	putchar('
');
}

template <typename T>
inline void Mx(T &x, T y) { x < y && (x = y); }

template <typename T>
inline void Mn(T &x, T y) { x > y && (x = y); }

const int N = 100500;
int h[N], ne[N<<1], to[N<<1], w[N<<1], cost[N<<1], tot = 1, m, n, k;

inline void add(int x, int y, int z, int c) {
	ne[++tot] = h[x], to[h[x] = tot] = y, w[tot] = z, cost[tot] = c;
}


const ll inf = 0x3f3f3f3f3f3f3f3f;
ll dis[N], vis[N], fr[N];
queue<int> q;
bool spfa(void) {
	memset(dis, 0x3f, sizeof(dis));
	q.push(1), dis[1] = 0;
	while (q.size()) {
		int x = q.front(); q.pop(); vis[x] = 0;
		for (int i = h[x], y; i; i = ne[i]) {
			if (!w[i] || dis[y = to[i]] <= dis[x] + cost[i]) continue;
			fr[y] = i; dis[y] = dis[x] + cost[i];
			if (!vis[y]) vis[y] = 1, q.push(y);
		}
	}
	return dis[n] < inf;
}

void work(void) {
	if (k == 0) return puts("0"), void();
	ll ans = inf, las = 0, sum = 0;
	while (k > 0 && spfa()) {
		ll f = inf;
		for (int t = n ; fr[t]; t = to[fr[t] ^ 1]) Mn(f, (ll)w[fr[t]]);
		for (int t = n ; fr[t]; t = to[fr[t] ^ 1]) w[fr[t]] -= f, w[fr[t] ^ 1] += f;
		k -= f + (dis[n] - las) * sum, sum += f, las = dis[n];
		Mn(ans, dis[n] + ((k - 1) / sum) + 1);
	}
	if (ans < inf) write(ans); else puts("No solution");
}

 
 
int main() {
	while (scanf ("%d %d %d
", &n, &m, &k) != EOF) {
		tot = 1; memset(h, 0, n * 4 + 200);
		for (int i = 1, x, y, z;i <= m; i++) {
			read(x), read(y), read(z), x++, y++;
			add(x, y, z, 1), add(y, x, 0, -1);
		}
		work();
	}
	return 0;
}

/*

2 1 1
0 1 555

*/