P1073 最优贸易 完整代码

朴素做法

点击以返回原文

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10, K = 110;

int n, m, p[N], un[N], ukn[K][N], ou[N], ans;
vector<int> G[N], H[N];
// un[u]: u -> n 
// ukn[k][u] u -> v(p[v] == k) -> n
// ou[u]: one -> u

#define Push(st, x) if(!st[x]) st[x] = 1, q.push(x)
void bfs_n() {
    queue<int> q;
    Push(un, n);
    while(q.size()) {
        int u = q.front(); q.pop();
        for(int v : H[u]) Push(un, v);
    }
}
void bfs_k(int k) {
    queue<int> q;
    for(int u = 1; u <= n; u++)
        if(un[u] && p[u] == k) Push(ukn[k], u);
    while(q.size()) {
        int u = q.front(); q.pop();
         for(int v : H[u]) Push(ukn[k], v);
    }
}
void bfs_1() {
    queue<int> q;
    Push(ou, 1);
    while(q.size()) {
        int u = q.front(); q.pop();
        for(int k = 1; k < K; k++)
            if(ukn[k][u]) ans = max(ans, k - p[u]);
        for(int v : G[u]) Push(ou, v);
    }
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m;
	for(int u = 1; u <= n; u++) cin >> p[u];
	while(m--) {
		int u, v, z;
		cin >> u >> v >> z;
		G[u].push_back(v), H[v].push_back(u);
		if(z == 2) G[v].push_back(u), H[u].push_back(v);
	}
	bfs_n();
	for(int k = 1; k < K; k++) bfs_k(k);
	bfs_1();
	cout << ans << endl;
	return 0;
}

贪心优化

点击以返回原文

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10, K = 110;

int n, m, p[N], un[N], ou[N], mx[N], ans;
vector<int> G[N], H[N];

void bfs_n() {
	queue<int> q;
	un[n] = 1, q.push(n);
	while(q.size()) {
		int u = q.front(); q.pop();
		for(int v : H[u]) if(!un[v]) un[v] = 1, q.push(v);
	}
}
void bfs_k(int k) {
	queue<int> q;
    for(int u = 1; u <= n; u++)
        if(un[u] && p[u] == k && mx[u] < k) mx[u] = k, q.push(u);
	while(q.size()) {
		int u = q.front(); q.pop();
 		for(int v : H[u]) if(mx[v] < k) mx[v] = k, q.push(v);
	}
}
void bfs_1() {
	queue<int> q;
	ou[1] = 1, q.push(1);
	while(q.size()) {
		int u = q.front(); q.pop();
		ans = max(ans, mx[u] - p[u]);
		for(int v : G[u]) if(!ou[v]) ou[v] = 1, q.push(v);
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m;
	for(int u = 1; u <= n; u++) cin >> p[u];
	while(m--) {
		int u, v, z;
		cin >> u >> v >> z;
		G[u].push_back(v), H[v].push_back(u);
		if(z == 2) G[v].push_back(u), H[u].push_back(v);
	}
	bfs_n();
	for(int k = K - 1; k; k--) bfs_k(k);
	bfs_1();
	cout << ans << endl;
	return 0;
}

离散化优化

点击以返回原文

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10, K = 110;

int n, m, p[N], un[N], ou[N], mx[N], ans;
vector<int> G[N], H[N];
set<int> P;

void bfs_n() {
	queue<int> q;
	un[n] = 1, q.push(n);
	while(q.size()) {
		int u = q.front(); q.pop();
		for(int v : H[u]) if(!un[v]) un[v] = 1, q.push(v);
	}
}
void bfs_k(int k) {
	queue<int> q;
    for(int u = 1; u <= n; u++)
        if(un[u] && p[u] == k && mx[u] < k) mx[u] = k, q.push(u);
	while(q.size()) {
		int u = q.front(); q.pop();
 		for(int v : H[u]) if(mx[v] < k) mx[v] = k, q.push(v);
	}
}
void bfs_1() {
	queue<int> q;
	ou[1] = 1, q.push(1);
	while(q.size()) {
		int u = q.front(); q.pop();
		ans = max(ans, mx[u] - p[u]);
		for(int v : G[u]) if(!ou[v]) ou[v] = 1, q.push(v);
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m;
	for(int u = 1; u <= n; u++) cin >> p[u], P.insert(p[u]);
	while(m--) {
		int u, v, z;
		cin >> u >> v >> z;
		G[u].push_back(v), H[v].push_back(u);
		if(z == 2) G[v].push_back(u), H[u].push_back(v);
	}
	bfs_n();
	for(int k : P) bfs_k(k);
	bfs_1();
	cout << ans << endl;
	return 0;
}

奇技淫巧

点击以返回原文

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10, K = 110;

int n, m, p[N], un[N], ukn[K][N], ou[N], ans;
vector<int> G[N], H[N];

void bfs(vector<int> (&M)[N], int (&st)[N], function<bool(int)> push, function<void(int)> op) {
	queue<int> q;
	for(int u = 1; u <= n; u++) if(push(u)) st[u] = 1, q.push(u);
	while(q.size()) {
		int u = q.front();
		q.pop();
		op(u);
		for(int v : M[u]) if(!st[v]) st[v] = 1, q.push(v);
	}
}
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	cin >> n >> m;
	for(int u = 1; u <= n; u++) cin >> p[u];
	while(m--) {
		int u, v, z;
		cin >> u >> v >> z;
		G[u].push_back(v), H[v].push_back(u);
		if(z == 2) G[v].push_back(u), H[u].push_back(v);
	}
	bfs(H, un, [](int u){ return u == n; }, [](int _){});
	for(int k = 1; k < K; k++) bfs(H, ukn[k], [&k](int u){ return un[u] && p[u] == k; }, [](int _){});
	bfs(G, ou, [](int u){ return u == 1; }, [](int u){
		for(int k = K - 1; k; k--)
			if(ukn[k][u]) { ans = max(ans, k - p[u]); return; }
	});
	cout << ans << endl;
	return 0;
}