題干：

鏈接：https://ac.nowcoder.com/acm/contest/551/G
來源：牛客網

題目描述

眾所周知，CSL 是一個負責的集訓隊隊長。為了讓集訓隊的學弟們訓練更加飽和，他根據每個人的能力，提出了 m 個題數要求。假如 CSL 認為 yi?比 xi 強，那么如果 xixi 做了 a 題，那 CSL 會要求 yi 需要做至少 a+ri×k，其中 riri 是已知的常數。CSL 現在一共有 s 道題目可以分給大家，因為 CSL 馬上就要考OS了，所以他不想再出其他題了，請問正整數 k 最大是多少。

輸入描述:

第一行有三個整數 n, m, s，分別表示集訓隊的學弟數量，CSL 的題數要求和 CSL 的題目數量。

接下來 m 行，每行三個整數 xi,yi,ri，含義題目描述中所述。

2≤n≤2?105
1≤m≤6?105
1≤s≤1012
1≤xi,yi≤n
0≤ri≤106

輸出描述:

在一行輸出一個整數表示 k 可取的最大值。特別地，如果題目不夠分則輸出 0；為無窮大輸出 -1。

示例1

輸入

復制

4 5 19 1 3 0 3 4 4 1 4 2 1 3 2 2 4 1

輸出

復制

2

示例2

輸入

復制

5 5 6 5 4 2 3 2 1 3 5 3 2 4 4 5 2 1

輸出

復制

0

備注:

強度是具有傳遞性的，如果 x 比 y 強且 y 比 z 強，那么 CSL 不會認為 z 比 x 強。輸入數據量較大，建議使用高效的輸入輸出方式。例如：在 C++ 中使用 scanf/printf 代替 cin/cout；在 Java 中使用 BufferedReader/PrintWriter 代替 Scanner/System.out。

解題報告：

? ? 這題不優化個常數還真會被卡。優化1：只要res>s直接return。優化2：不能每次check的時候都遍歷一遍邊來更新in數組，需要先預存in數組然后用ON的復雜度來更新，如果Om的復雜度就炸了。優化3：這題r不能取1e18，其實不難發現右端點r最多取值就是s，并且r可取s 當且僅當 只有一個點的ri==1，其他全為0，而全零這個特殊情況已經判-1判掉了，所以r直接取上界s就行。

emmm其實這題貌似不需要二分，直接拓撲一遍求個res，然后s/res就是答案啊。。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define FF first #define SS second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,ll> PIL; const int MAX = 2e5 + 5; int n,m; ll s; int in[MAX],IN[MAX]; ll num[MAX]; vector<PIL> vv[MAX]; map<int,int> mp[MAX]; bool ok(ll x) {queue<int> q;for(int i = 1; i<=n; i++) in[i] = IN[i],num[i] = 0;for(int i = 1; i<=n; i++) {if(in[i] == 0) q.push(i);}ll res = 0;while(q.size()) {int cur = q.front();q.pop();res += num[cur];if(res > s) return 0 ;for(PIL v : vv[cur]) {in[v.FF]--;if(in[v.FF] == 0) q.push(v.FF);num[v.FF] = max(num[v.FF],num[cur] + x * v.SS);}}return res <= s; } int main() {cin>>n>>m>>s;ll w;int flag = 0;for(int a,b,i = 1; i<=m; i++) {scanf("%d%d%lld",&a,&b,&w);if(w != 0) flag = 1;vv[a].pb(pm(b,w));}if(flag == 0) {printf("-1\n");return 0 ;}for(int i = 1; i<=n; i++) {for(PIL v : vv[i]) IN[v.FF]++;}ll l = 0,r = s,mid = (l+r)>>1,ans = -1;while(l<=r) {mid = (l+r)>>1;if(ok(mid)) l=mid+1,ans=mid;else r = mid-1;}printf("%lld\n",ans);return 0 ; }

?

總結

以上是生活随笔為你收集整理的【牛客 - 551G】CSL的训练计划（二分 + 拓扑排序 + 优化卡常）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。