题干:
链接: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 ;
}