做网站推广需要花多少钱,网站建设丶金手指下拉15,中国建筑人才网下载,wordpress转移插件题干#xff1a;
链接#xff1a;https://ac.nowcoder.com/acm/contest/551/G 来源#xff1a;牛客网
题目描述
众所周知#xff0c;CSL 是一个负责的集训队队长。为了让集训队的学弟们训练更加饱和#xff0c;他根据每个人的能力#xff0c;提出了 m 个题数要求。假如…题干
链接https://ac.nowcoder.com/acm/contest/551/G 来源牛客网
题目描述
众所周知CSL 是一个负责的集训队队长。为了让集训队的学弟们训练更加饱和他根据每个人的能力提出了 m 个题数要求。假如 CSL 认为 yi 比 xi 强那么如果 xixi 做了 a 题那 CSL 会要求 yi 需要做至少 ari×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只要ress直接return。优化2不能每次check的时候都遍历一遍边来更新in数组需要先预存in数组然后用ON的复杂度来更新如果Om的复杂度就炸了。优化3这题r不能取1e18其实不难发现右端点r最多取值就是s并且r可取s 当且仅当 只有一个点的ri1其他全为0而全零这个特殊情况已经判-1判掉了所以r直接取上界s就行。
emmm其实这题貌似不需要二分直接拓扑一遍求个res然后s/res就是答案啊。。
AC代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define FF first
#define SS second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pairint,ll PIL;
const int MAX 2e5 5;
int n,m;
ll s;
int in[MAX],IN[MAX];
ll num[MAX];
vectorPIL vv[MAX];
mapint,int mp[MAX];
bool ok(ll x) {queueint q;for(int i 1; in; i) in[i] IN[i],num[i] 0;for(int i 1; in; 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()
{cinnms;ll w;int flag 0;for(int a,b,i 1; im; 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; in; i) {for(PIL v : vv[i]) IN[v.FF];}ll l 0,r s,mid (lr)1,ans -1;while(lr) {mid (lr)1;if(ok(mid)) lmid1,ansmid;else r mid-1;}printf(%lld\n,ans);return 0 ;
}
