#include <bits/stdc++.h> #define DEBUG(x) cout << '>' << #x << ':' << x << endl; #define fi first #define se second #define ll long long #define ld long double #define pb push_back #define vi vector<int> #define MAXN 100001 using namespace std; const int n = 3; const ll M = 1000000; const ll M2 = M * M; struct state { vi A; ll h; int d; state(int a, int b, int c, int d_) { A.pb(a); A.pb(b); A.pb(c); d = d_; h = (ll)a + M * ((ll)b) + M2 * ((ll)c); } void fill_res(vi &R) { for (int i = 0; i < n; i++) { if (R[A[i]] == -1) R[A[i]] = d; } } void p() { cout<<A[0]<<" "<<A[1]<<" "<<A[2]<<endl; } }; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); vi A(n); int a, b, c; for (int i = 0; i < n; i++) { cin >> A[i]; } cin >> a >> b >> c; state s0(a, b, c, 0); int C = A[n - 1]; vi res(C + 1, -1); set<ll> V; V.insert(s0.h); queue<state> Q; Q.push(s0); while (!Q.empty()) { state s = Q.front(); Q.pop(); s.fill_res(res); // s.p(); for (int p = 0; p < n; p++) { for (int q = 0; q < n; q++) { if(p == q) continue; int flow = min(A[q] - s.A[q], s.A[p]); vector<int> B(s.A); B[p] -= flow; B[q] += flow; state s1(B[0], B[1], B[2], s.d + 1); if (V.find(s1.h) == V.end()) { V.insert(s1.h); Q.push(s1); } } } } for (int i = 0; i < res.size(); i++) cout << res[i] << " "; cout << endl; return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 | #include <bits/stdc++.h> #define DEBUG(x) cout << '>' << #x << ':' << x << endl; #define fi first #define se second #define ll long long #define ld long double #define pb push_back #define vi vector<int> #define MAXN 100001 using namespace std; const int n = 3; const ll M = 1000000; const ll M2 = M * M; struct state { vi A; ll h; int d; state(int a, int b, int c, int d_) { A.pb(a); A.pb(b); A.pb(c); d = d_; h = (ll)a + M * ((ll)b) + M2 * ((ll)c); } void fill_res(vi &R) { for (int i = 0; i < n; i++) { if (R[A[i]] == -1) R[A[i]] = d; } } void p() { cout<<A[0]<<" "<<A[1]<<" "<<A[2]<<endl; } }; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); vi A(n); int a, b, c; for (int i = 0; i < n; i++) { cin >> A[i]; } cin >> a >> b >> c; state s0(a, b, c, 0); int C = A[n - 1]; vi res(C + 1, -1); set<ll> V; V.insert(s0.h); queue<state> Q; Q.push(s0); while (!Q.empty()) { state s = Q.front(); Q.pop(); s.fill_res(res); // s.p(); for (int p = 0; p < n; p++) { for (int q = 0; q < n; q++) { if(p == q) continue; int flow = min(A[q] - s.A[q], s.A[p]); vector<int> B(s.A); B[p] -= flow; B[q] += flow; state s1(B[0], B[1], B[2], s.d + 1); if (V.find(s1.h) == V.end()) { V.insert(s1.h); Q.push(s1); } } } } for (int i = 0; i < res.size(); i++) cout << res[i] << " "; cout << endl; return 0; } |