Hướng dẫn giải của TOUR
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này
Code mẫu của happyboy99x
#include <iostream> #include <cassert> #include <cstdio> using namespace std; const int N = 1000; const int M = 10000; int firstEdge[N]; int nextEdge[M]; int to[M]; int weight[M]; double minDist[N]; int numEnqueue[N]; int q[N + 1]; bool inQueue[N]; int n; double myAbs(double x) { return x < 0 ? -x : x; } bool hasNegativeCycleMaybeFaster(double average) { for (int i = 0; i < n; ++i) { minDist[i] = 0; } for (int run = 0; run <= n; ++run) { bool updated = false; for (int u = 0; u < n; ++u) { for (int e = firstEdge[u]; e != -1; e = nextEdge[e]) { int v = to[e]; if (minDist[u] + weight[e] - average + 1e-6 < minDist[v]) { if (run == n) return true; minDist[v] = minDist[u] + weight[e] - average; updated = true; } } } if (!updated) break; } return false; } bool hasNegativeCycle(double average) { for (int i = 0; i < n; ++i) { q[i] = i; numEnqueue[i] = 0; inQueue[i] = true; } int qHead = 0; int qTail = n; while (qHead != qTail) { int u = q[qHead]; qHead = qHead == n ? 0 : qHead + 1; inQueue[u] = false; for (int e = firstEdge[u]; e != -1; e = nextEdge[e]) { int v = to[e]; if (minDist[u] + weight[e] - average + 1e-6 < minDist[v]) { minDist[v] = minDist[u] + weight[e] - average; if (!inQueue[v]) { qHead = qHead == 0 ? n : qHead - 1; q[qHead] = v; inQueue[v] = true; if (++numEnqueue[v] > n) { return true; } } } } } return false; } int main() { #ifndef ONLINE_JUDGE assert(freopen("tour.inp", "r", stdin)); assert(freopen("tour.out", "w", stdout)); #endif ios::sync_with_stdio(false); cin >> n; int m; cin >> m; for (int i = 0; i < n; ++i) { firstEdge[i] = -1; } int heaviest = 0; for (int i = 0; i < m; ++i) { int u; cin >> u; --u; int v; cin >> v; --v; int w; cin >> w; to[i] = v; weight[i] = w; nextEdge[i] = firstEdge[u]; firstEdge[u] = i; heaviest = max(heaviest, w); } double low = 0; double high = heaviest + 100; for (int run = 0; myAbs(low - high) > 1e-4 && run < 40; ++run) { double middle = (low + high) / 2; if (hasNegativeCycle(middle)) { high = middle; } else { low = middle; } } double answer = (low + high) / 2; if (answer > heaviest + 50) { puts("NO TOUR"); } else { printf("%.2lf\n", (low + high) / 2); } return 0; }
Code mẫu của ladpro98
#include <iostream> #include <cstdio> #include <algorithm> #include <cassert> #include <vector> #include <queue> #include <set> #include <map> #include <ctime> #include <iomanip> #include <cstdlib> #include <cstring> #include <string> #define FOR(i, a, b) for(int i = (a); i < (b); i++) #define REP(i, a, b) for(int i = (a); i <=(b); i++) #define REPD(i, a, b) for(int i = (a); i >=(b); i--) #define TR(i, a) for(typeof((a).begin()) i = (a).begin(); i != (a).end(); i++) #define LL long long #define LD long double #define II pair<int, int> #define X first #define Y second #define MP make_pair #define PB push_back const int N = 1111; using namespace std; vector<II> a[N]; bool inQ[N], was[N]; double d[N]; int cnt[N]; int n, m; queue<int> start; bool ok(double r) { REP(i, 1, n) inQ[i] = 0; inQ[1] = 1; queue<int> Q = start; REP(i, 1, n) d[i] = 1e16, cnt[i] = 0; Q.push(1); d[1] = 0; while (!Q.empty()) { int u = Q.front(); Q.pop(); inQ[u] = 0; TR(it, a[u]) { int v = it -> X; double uv = it -> Y - r; if (d[v] > d[u] + uv) { d[v] = d[u] + uv; cnt[v] = cnt[u] + 1; if (cnt[v] > n) return 1; if (!inQ[v]) { inQ[v] = 1; Q.push(v); } } } } return 0; } void dfs(int u) { was[u] = 1; TR(it, a[u]) { int v = it -> X; if (!was[v]) dfs(v); } } int main() { ios :: sync_with_stdio(0); cin.tie(0); cin >> n >> m; int u, v, c; FOR(i, 0, m) { cin >> u >> v >> c; a[u].PB(MP(v, c)); } REP(i, 1, n) if (!was[i]) { start.push(i); dfs(i); } double l = 0, r = 1e9 + 9, ans = -10; FOR(step, 0, 50) { double mid = (l + r) / 2; if (ok(mid)) { ans = r = mid; } else l = mid; } if (ans < 0) cout << "NO TOUR"; else cout << setprecision(2) << fixed << ans; return 0; }
Code mẫu của RR
#include <set> #include <map> #include <list> #include <cmath> #include <queue> #include <stack> #include <cstdio> #include <string> #include <vector> #include <cstdlib> #include <cstring> #include <sstream> #include <iomanip> #include <complex> #include <iostream> #include <algorithm> #include <ctime> #include <deque> #include <bitset> #include <cctype> #include <utility> #include <cassert> using namespace std; #define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++) #define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--) #define REP(i,a) for(int i=0,_a=(a); i<_a; i++) #define EACH(it,a) for(__typeof(a.begin()) it = a.begin(); it != a.end(); ++it) #define DEBUG(x) { cout << #x << " = " << x << endl; } #define PR(a,n) { cout << #a << " = "; FOR(_,1,n) cout << a[_] << ' '; cout << endl; } #define PR0(a,n) { cout << #a << " = "; REP(_,n) cout << a[_] << ' '; cout << endl; } long double d[1011]; int n, m; vector< pair<int,int> > ke[1011]; int cnt[1011]; bool inQ[1011]; bool check(double val) { FOR(i,1,n) d[i] = 1e10; d[1] = 0; FOR(i,1,n) inQ[i] = false; FOR(i,1,n) cnt[i] = 0; inQ[1] = true; queue<int> q; q.push(1); while (!q.empty()) { int u = q.front(); q.pop(); inQ[u] = false; REP(i,ke[u].size()) { int v = ke[u][i].first; double cur = ke[u][i].second - val; if (d[v] > d[u] + cur) { d[v] = d[u] + cur; ++cnt[v]; if (cnt[v] > n) return true; if (!inQ[v]) { inQ[v] = true; q.push(v); } } } } return false; } int main() { ios :: sync_with_stdio(false); cin.tie(NULL); cout << (fixed) << setprecision(6); while (cin >> n >> m) { FOR(i,1,m) { int u, v, c; cin >> u >> v >> c; ke[u].push_back(make_pair(v, c)); } long double l = 0, r = 1e9 * 1.2; long double res = r; REP(turn,40) { long double mid = (l + r) / 2.0; if (check(mid)) r = res = mid; else l = mid; } if (res > 1e9 * 1.1) cout << "NO TOUR" << endl; else cout << (fixed) << setprecision(2) << res << endl; } return 0; }
Code mẫu của skyvn97
#include<cstdio> #include<queue> #include<vector> #define MAX 1010 #define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i=i+1) #define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1) #define fi first #define se second using namespace std; const double INF=1e13; const double eps=1e-9; const double maxCost=1e9+7; const char noCycle[]="NO TOUR"; vector<pair<int,double> > g[MAX]; double dis[MAX]; bool inQueue[MAX]; int n,m; void loadgraph(void) { scanf("%d%d",&n,&m); REP(zz,m) { int u,v,c; scanf("%d%d%d",&u,&v,&c); g[u].push_back(make_pair(v,c)); } FOR(i,1,n) g[n+1].push_back(make_pair(i,10.0)); n++; } bool negativeCycle(int s) { queue<int> q; dis[s]=0.0; q.push(s); REP(zz,n+1) { if (q.empty()) return (false); vector<int> toPush; while (!q.empty()) { int u=q.front();q.pop(); REP(i,g[u].size()) { int v=g[u][i].fi; if (dis[v]>dis[u]+g[u][i].se+eps) { dis[v]=dis[u]+g[u][i].se; if (!inQueue[v]) { inQueue[v]=true; toPush.push_back(v); } } } } REP(i,toPush.size()) { q.push(toPush[i]); inQueue[toPush[i]]=false; } } return (true); } bool ok(double x) { FOR(i,1,n) { dis[i]=INF+7.0; inQueue[i]=false; } FOR(u,1,n) REP(i,g[u].size()) g[u][i].se-=x; bool res=negativeCycle(n); FOR(u,1,n) REP(i,g[u].size()) g[u][i].se+=x; return (res); } void process(void) { if (!ok(maxCost)) { printf("%s",noCycle); return; } double L=0; double R=maxCost; REP(zz,45) { double M=(L+R)/2.0; if (ok(M)) R=M; else L=M; } printf("%.2lf\n",(L+R)/2.0); } int main(void) { loadgraph(); process(); return 0; }
Bình luận