牛客上海高校程序设计竞赛 G CSL 的训练计划（拓扑排序）
链接：https://ac.nowcoder.com/acm/contest/551/G
来源：牛客网
时间限制：C/C++ 2秒，其他语言4秒
空间限制：C/C++ 524288K，其他语言1048576K
64bit IO Format: %lld
题目描述
众所周知，CSL 是一个负责的集训队队长。为了让集训队的学弟们训练更加饱和，他根据每个人的能力，提出了 m 个题数要求。假如 CSL 认为 yi 比 xi 强，那么如果 xi 做了 a 题，那 CSL 会要求 yi 需要做至少 a+ri×k，其中 ri 是已知的常数。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。
（我的超时思路：当时做的时候想到二分枚举答案，然后深搜检验，当时觉得思路巨好，结果一直T，还是太菜了。。。）
（思路：只有所有r都为0，才会出现“-1”这种情况。否则，直接一遍拓扑求出需要的最少的题数，用s除以该值即可。当时没有画图，想着，孙子节点的值是其爷爷节点的值得K的二次方倍。其实，对于每个节点，其值是该节点到根节点的最远距离乘以k。（其实看不出来，直接二分枚举k，拓扑排序检验也可以。）k最小为1，先按1求出每个节点的值，然后求其和sum，那么答案就是s/sum。）
（至于搜索为啥超时，大牛队友给了一种case。）
1.直接拓扑排序代码（380ms）
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
#include <stack>
#include <set>
#include <cmath>
#include <string>
#define ll long long
using namespace std;
const int maxn=2e5+10;
const int maxm=6e5+10;
int n,m;
ll s;
int head[maxn],cnt;
int in[maxn];
bool vis[maxn];
ll ans[maxn];
struct node
{
int to,next,w;
}E[maxm];
void add(int u,int v,int w)
{
E[cnt].to=v;
E[cnt].w=w;
E[cnt].next=head[u];
head[u]=cnt++;
}
void Toposort()
{
ll sum=0;
queue <int> q;
for(int i=1;i<=n;i++)
{
vis[i]=0;
ans[i]=0;
if(in[i]==0)
{
q.push(i);
vis[i]=1;
}
}
while(q.size())
{
int now=q.front();
q.pop();
vis[now]=0;
for(int i=head[now];i!=-1;i=E[i].next)
{
int v=E[i].to;
ll tmp=ans[now]+E[i].w;
ans[v]=max(ans[v],tmp);
if(--in[v]==0&&!vis[v])
{
q.push(v);
vis[v]=1;
}
}
}
for(int i=1;i<=n;i++)
{
sum+=ans[i];
}
printf("%lld\n",s/sum);
}
int main(void)
{
scanf("%d%d%lld",&n,&m,&s);
int u,v,w,f=1;
cnt=0;
for(int i=1;i<=n;i++)
{
head[i]=-1;
}
for(int i=0;i<m;i++)
{
scanf("%d%d%d",&u,&v,&w);
if(u==v) continue;
in[v]++;
if(w!=0) f=0;
add(u,v,w);
}
if(f)
{
printf("-1\n");
return 0;
}
Toposort();
return 0;
}
2.二分+拓扑（1589ms）
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
#include <stack>
#include <set>
#include <cmath>
#include <string>
#define ll long long
using namespace std;
const int maxn=2e5+10;
const int maxm=6e5+10;
int n,m;
ll s;
int head[maxn],cnt;
int in[maxn],temp[maxn];
bool vis[maxn];
ll ans[maxn];
struct node
{
int to,next,w;
}E[maxm];
void add(int u,int v,int w)
{
E[cnt].to=v;
E[cnt].w=w;
E[cnt].next=head[u];
head[u]=cnt++;
}
bool check(ll k)
{
ll sum=0;
queue <int> q;
for(int i=1;i<=n;i++)
{
vis[i]=0;
ans[i]=0;
temp[i]=in[i];
if(in[i]==0)
{
q.push(i);
vis[i]=1;
}
}
while(q.size())
{
int now=q.front();
q.pop();
vis[now]=0;
for(int i=head[now];i!=-1;i=E[i].next)
{
int v=E[i].to;
ll tmp=ans[now]+E[i].w*k;
if(tmp>s)
{
return 0;
}
ans[v]=max(ans[v],tmp);
if(--temp[v]==0&&!vis[v])
{
q.push(v);
vis[v]=1;
}
}
}
for(int i=1;i<=n;i++)
{
sum+=ans[i];
if(sum>s) return 0;
}
return 1;
}
int main(void)
{
scanf("%d%d%lld",&n,&m,&s);
int u,v,w,f=1;
cnt=0;
for(int i=1;i<=n;i++)
{
head[i]=-1;
}
for(int i=0;i<m;i++)
{
scanf("%d%d%d",&u,&v,&w);
if(u==v) continue;
in[v]++;
if(w!=0) f=0;
add(u,v,w);
}
if(f)
{
printf("-1\n");
return 0;
}
ll l=0,r=2*s,res=0;
while(l<=r)
{
ll m=(l+r)/2;
if(check(m))
{
res=max(m,res);
l=m+1;
}
else
{
r=m-1;
}
}
printf("%lld\n",res);
return 0;
}