UVa 10594 Data Flow

題意：
    給你一個無向圖，兩點之間的邊的容量是K，每條邊有不同的cost，現在有大小為D的資料，要從起點傳到終點，問把全部資料傳過去的最小cost是多少，如果不能全部傳過去則輸出Impossible.

• 第一行輸入N M：總共N個點，編號從1~N，然後底下有M行
• 有M行，每行u v c：表示點u和點v之間的cost為c(雙向圖)
• 最後一行D K：要傳的資料大小為D，每個邊的容量為K

想法：

    最小cost最大流題型(MCMF)，基本上就是建圖，然後套MCMF演算法模板，但提交後發現時間根本是壓秒過@@，花了2.979s(時限3s)，但是這個秒數排名還在前一半以內...。

    不過還是要壓一下秒數，看了同學的code後，發現這題可以最佳化的地方在於"每條邊的容量都是一樣的"，所以你可以把每條邊的容量當成1，然後再乘以K就好了。底下附上兩種code，第一個是差點TLE的模板code，第二個是最佳化的code，兩者的差別只差在MCMF()這個function的寫法。第二個的時間是0.135s， 和原本差了20幾倍。

1.

	#include <cstdio>
	#include <cstring>
	#include <vector>
	#include <queue>
	#include <algorithm>
	using namespace std;
	#define INF 999999
	using llt = long long int;
	llt N, M, D, K;
	vector<int> edge[105];
	llt cap[105][105], flow[105][105], cost[105][105];
	llt pre[105], dis[105];
	void Initial();
	llt MCMF(llt S, llt T);
	bool SPFA(llt S, llt T);
	llt FindMinFlow(llt S, llt T);
	void UpdateFlow(llt S, llt T, llt bottleneck);
	int main()
	{
	while (scanf("%d %d", &N, &M) == 2) {
	Initial();
	llt u, v, c;
	for (llt i = 0; i < M; ++i) {
	scanf("%lld %lld %lld", &u, &v, &c);
	edge[u].push_back(v);
	edge[v].push_back(u);
	cost[u][v] = cost[v][u] = c;
	}
	scanf("%lld %lld", &D, &K);
	for (llt i = 1; i <= N; ++i)
	for (llt j : edge[i]) cap[i][j] = K;
	edge[0].push_back(1);
	cap[0][1] = D;
	llt result = MCMF(0, N);
	if (result == -1) puts("Impossible.");
	else printf("%lld\n", result);
	}
	}
	void Initial()
	{
	for (llt i = 0; i <= N; ++i)
	edge[i].clear();
	memset(flow, 0, sizeof(flow));
	}
	llt MCMF(llt S, llt T)
	{
	llt max_flow = 0;
	llt min_cost = 0;
	while (SPFA(S, T)) {
	llt ff = FindMinFlow(S, T);
	UpdateFlow(S, T, ff);
	max_flow += ff;
	min_cost += (ff * dis[T]);
	}
	if (max_flow != D) return -1;
	else return min_cost;
	}
	bool SPFA(llt S, llt T)
	{
	fill(begin(dis), end(dis), INF);
	dis[S] = 0;
	queue<int> Q;
	bool inQueue[105] = {0};
	Q.push(S);
	inQueue[S] = true;
	while (!Q.empty()) {
	llt u = Q.front();
	inQueue[u] = false;
	Q.pop();
	for (llt v : edge[u]) {
	if (flow[v][u] > 0 && dis[u] + (-cost[v][u]) < dis[v]) {
	dis[v] = dis[u] + (-cost[v][u]);
	pre[v] = u;
	if (!inQueue[v]) {inQueue[v] = true; Q.push(v);}
	}
	else if (cap[u][v] > flow[u][v] && dis[u] + cost[u][v] < dis[v]) {
	dis[v] = dis[u] + cost[u][v];
	pre[v] = u;
	if (!inQueue[v]) {inQueue[v] = true; Q.push(v);}
	}
	}
	}
	if (dis[T] == INF) return false;
	else return true;
	}
	llt FindMinFlow(llt S, llt T)
	{
	llt bottleneck = INF;
	for (llt u = T; u != S; u = pre[u])
	bottleneck = min(bottleneck, cap[pre[u]][u] - flow[pre[u]][u]);
	return bottleneck;
	}
	void UpdateFlow(llt S, llt T, llt bottleneck)
	{
	for (llt u = T; u != S; u = pre[u]) {
	flow[pre[u]][u] += bottleneck;
	flow[u][pre[u]] -= bottleneck;
	}
	}

view raw [UVa] 10594 Data Flow1.cpp hosted with ❤ by GitHub

2.

	#include <cstdio>
	#include <cstring>
	#include <vector>
	#include <queue>
	#include <algorithm>
	using namespace std;
	#define INF 999999
	using llt = long long int;
	llt N, M, D, K;
	vector<int> edge[105];
	llt cap[105][105], flow[105][105], cost[105][105];
	llt pre[105], dis[105];
	void Initial();
	llt MCMF(llt S, llt T);
	bool SPFA(llt S, llt T);
	void UpdateFlow(llt S, llt T, llt bottleneck);
	int main()
	{
	while (scanf("%d %d", &N, &M) == 2) {
	Initial();
	llt u, v, c;
	for (llt i = 0; i < M; ++i) {
	scanf("%lld %lld %lld", &u, &v, &c);
	edge[u].push_back(v);
	edge[v].push_back(u);
	cost[u][v] = cost[v][u] = c;
	cap[u][v] = cap[v][u] = 1;
	}
	scanf("%lld %lld", &D, &K);
	llt result = MCMF(1, N);
	if (result == -1) puts("Impossible.");
	else printf("%lld\n", result);
	}
	}
	void Initial()
	{
	for (llt i = 0; i <= N; ++i)
	edge[i].clear();
	memset(flow, 0, sizeof(flow));
	}
	llt MCMF(llt S, llt T)
	{
	llt min_cost = 0;
	while (SPFA(S, T)) {
	if (D > K) min_cost += (K * dis[T]);
	else min_cost += (D * dis[T]);
	D -= K;
	UpdateFlow(S, T, 1);
	if (D <= 0) break;
	}
	if (D > 0) return -1;
	else return min_cost;
	}
	bool SPFA(llt S, llt T)
	{
	fill(begin(dis), end(dis), INF);
	dis[S] = 0;
	queue<int> Q;
	bool inQueue[105] = {0};
	Q.push(S);
	inQueue[S] = true;
	while (!Q.empty()) {
	llt u = Q.front();
	inQueue[u] = false;
	Q.pop();
	for (llt v : edge[u]) {
	if (flow[v][u] > 0 && dis[u] + (-cost[v][u]) < dis[v]) {
	dis[v] = dis[u] + (-cost[v][u]);
	pre[v] = u;
	if (!inQueue[v]) {inQueue[v] = true; Q.push(v);}
	}
	else if (cap[u][v] > flow[u][v] && dis[u] + cost[u][v] < dis[v]) {
	dis[v] = dis[u] + cost[u][v];
	pre[v] = u;
	if (!inQueue[v]) {inQueue[v] = true; Q.push(v);}
	}
	}
	}
	if (dis[T] == INF) return false;
	else return true;
	}
	void UpdateFlow(llt S, llt T, llt bottleneck)
	{
	for (llt u = T; u != S; u = pre[u]) {
	flow[pre[u]][u] += bottleneck;
	flow[u][pre[u]] -= bottleneck;
	}
	}

view raw [UVa] 10594 Data Flow2.cpp hosted with ❤ by GitHub