Submission #1123360

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123360		Requiem	Travelling Merchant (APIO17_merchant)	C++20	0 / 100	261 ms	6492 KiB

merchant

#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#define MOD 1000000007
#define inf 1e18
#define fi first
#define se second
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define sz(a) ((int)(a).size())
#define endl '\n'
#define pi 3.14159265359
#define TASKNAME "merchant"
using namespace std;
template<typename T> bool maximize(T &res, const T &val) { if (res <= val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res >= val){ res = val; return true; }; return false; }
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;
/**
Đồ thị n đỉnh, m cạnh có hướng.
K vật phẩm riêng biệt

Mỗi chợ có 1 mức giá cho việc mua / bán sản phẩm
Mỗi chợ có thể không mua / bán hết tất cả K sản phẩm mà chỉ mua hoặc bán một vài sản
phẩm.

Ta muốn tìm 1 thứ gọi là chu trình tối ưu lợi nhuận
bắt đầu với cái túi đựng đồ trống và khi quay về cũng với cái túi đựng đồ trống.

Cái túi có thể chứa tối đa 1 món đồ. Lợi nhuận: tổng giá bán - tổng giá mua.
Độ tối ưu: Lợi nhuận / độ dài chu trình.

n <= 100, m <= 1e4, k <= 1e3.

subtask 1: tất cả các món đồ chỉ có thể mua ở tiệm 1.
subtask 2: tất cả con đường đều tốn độ dài 1.
subtask 3: tất cả các món đồ đều được bán và Bij = Sij.
subtask 4: ko còn đk gì

Ý tưởng đầu tiên:

Ta sẽ chặt nhị phân cái efficiency.

lúc effiency * len - profit <= 0.
Mình cần kiểm tra xem đồ thị có tồn tại chu trình âm hay không.
Nhưng mà điều quan trọng là gì.
profit = (tổng của bán) - (tổng của mua).
-profit = tổng của mua - tổng của bán.

dist[u][k][type]: tức là chi phí nhỏ nhất xét đến đỉnh u, nếu như ta đang cầm món đồ là k.
Nếu k != 0 thì mình có thể bán nó đi với độ phức tạp là O(1)
Nếu k = 0 thì mình có thể chọn mua nó, với độ phức tạp là O(K),
Tuc la ta bat dau hanh trinh tai dinh u.

Muc tieu cua minh dist[u][0][0] <= 0.

chỉ có 1 trạng thái mà ta có thể mua và số trạng thái đẫn đến là O(K).
có K trạng thái mà ta có thể bán nhưng nó sẽ vẫn chỉ đến là

**/
const int MAXN = 120;
const int MAXM = 9999;
const int MAXK = 1003;

int dist[MAXN][MAXK][2], inqueue[MAXN][MAXK][2],cnt[MAXN];
iii edge[MAXM];
int S[MAXN][MAXK], B[MAXN][MAXK];
int n, m, k;
vector<int> g[MAXN];

void addState(queue<iii> &q, int newU, int newItem, int newType, int du, int w){
    if (minimize(dist[newU][newItem][newType], du + w)) {
        if (newItem == 0 and newType == 0) cnt[newU]++;
        if (!inqueue[newU][newItem][newType]) {
            q.push({newU, {newItem, newType}});
            inqueue[newU][newItem][newType] = true;
        }
    }
}
bool spfa(int mid){
    queue<iii> q;
    FOR(i, 1, n){
        cnt[i] = 0;
        FOR(j, 0, k) {
            dist[i][j][0] = dist[i][j][1] = inf;
            inqueue[i][j][0] = inqueue[i][j][1] = false;
        }
        dist[i][0][1] = 0;
        q.push({i, {0, 1}});
        inqueue[i][0][1] = true;
    }

    while(!q.empty()){
        int u = q.front().fi;
        int item = q.front().se.fi;
        int type = q.front().se.se;
        inqueue[u][item][type] = false;

        q.pop();

        if (item == 0){
            FOR(i, 1, k){
                if (B[u][i] != -1){
                    addState(q, u, i, type, dist[u][item][type], B[u][i]);
                }
            }
        }
        else{

            if (S[u][item] != -1){
                addState(q, u, 0, type, dist[u][item][type], -S[u][item]);
                if (cnt[u] > n) return true;
            }
        }

        for(auto id: g[u]){
            int v = edge[id].se.fi + edge[id].se.se - u;
            int len = edge[id].fi;

            addState(q, v, item, 0, dist[u][item][type], len * mid);
            if (cnt[v] > n) return true;

        }
    }
    return false;


}
main()
{
    fast;
    if (fopen(TASKNAME".inp","r")){
        freopen(TASKNAME".inp","r",stdin);
        freopen(TASKNAME".out","w",stdout);
    }
    cin >> n >> m >> k;
    FOR(i, 1, n){
        FOR(j, 1, k){
            cin >> B[i][j] >> S[i][j];
        }
    }

    FOR(i, 1, m){
        cin >> edge[i].se.fi >> edge[i].se.se >> edge[i].fi;
        g[edge[i].se.fi].pb(i);
    }

//    if (spfa(5)){
//        cout << "YES" << endl;
//    }
//    else cout << "NO" << endl;
    int l = 1, r = 1e9, res = 0;
    while(l <= r){
        int mid = (l + r) >> 1;
//        cerr << l << ' ' << r << ' ' << mid << endl;
        if (spfa(mid)){
            l = mid + 1;
            res = mid;
        }
        else r = mid - 1;
    }
    cout << res << endl;
}
/**
Warning:
Đọc sai đề???
Cận lmao
Code imple thiếu case nào không.
Limit.
**/

Compilation message (stderr)

merchant.cpp:131:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  131 | main()
      | ^~~~
merchant.cpp: In function 'int main()':
merchant.cpp:135:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  135 |         freopen(TASKNAME".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:136:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  136 |         freopen(TASKNAME".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 12
• Subtask 2: 0 / 21
• Subtask 3: 0 / 33
• Subtask 4: 0 / 34