제출 #1123370

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1123370		Requiem	여행하는 상인 (APIO17_merchant)	C++20	100 / 100	118 ms	2340 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 1e15
#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][MAXN], profit[MAXN][MAXN];
int graph[MAXN][MAXN];
int B[MAXN][MAXK], S[MAXN][MAXK];
int n, m, k;

void floyd_warshall(int dist[MAXN][MAXN]){
    for(int k = 1; k <= n; k++){
        FOR(i, 1, n){
            FOR(j, 1, n){
                minimize(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }
}
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];
        }
    }
    memset(dist, 0x3f, sizeof(dist));
    FOR(i, 1, m){
        int u, v, w;
        cin >> u >> v >> w;
        dist[u][v] = w;
    }

    floyd_warshall(dist);
//    FOR(i, 1, n){
//        FOR(j, 1, n){
//            cout << dist[i][j] << ' ';
//        }
//        cout << endl;
//    }
//    cout << endl;

    FOR(i, 1, n){
        FOR(j, 1, n){
            FOR(t, 1, k){
                if (B[i][t] != -1 and S[j][t] != -1) maximize(profit[i][j], S[j][t] - B[i][t]);
            }
        }
    }

    int l = 1, r = 1e11, res = 0;
    while(l <= r){
        int mid = (l + r) >> 1;
        FOR(i, 1, n){
            FOR(j, 1, n){
                graph[i][j] = ((dist[i][j] >= inf / mid) ? inf : dist[i][j] * mid) - profit[i][j];
            }
        }
        floyd_warshall(graph);
        bool neg_cycle = false;

        FOR(i, 1, n){
            if (graph[i][i] <= 0) neg_cycle = true;
        }

        if (neg_cycle) {
            res = mid;
            l = mid + 1;
        }
        else r = mid - 1;
    }
    cout << res << endl;
}
/**
Warning:
Đọc sai đề???
Cận lmao
Code imple thiếu case nào không.
Limit.
**/

컴파일 시 표준 에러 (stderr) 메시지

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

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