新智认知杯:CSL的训练计划(拓扑排序)

新智认知杯:CSL的训练计划(拓扑排序)

众所周知，CSL 是一个负责的集训队队长。为了让集训队的学弟们训练更加饱和，他根据每个人的能力，提出了 m 个题数要求。假如 CSL 认为 yi 比 xi 强，那么如果 xi 做了 a 题，那 CSL 会要求 yi 需要做至少 a+ri×k，其中 ri 是已知的常数。CSL 现在一共有 s 道题目可以分给大家，因为 CSL 马上就要考OS了，所以他不想再出其他题了，请问正整数 k 最大是多少。

从题目中可以看到一个不等式关系，不难想到可以用差分约束来解，将a = 0, k = 1代入建边，可以求出k最小的情况下每个人在满足所有约束下至少要做的题量，当k增大时，每个人做的题量数会增加为 k 倍 ，所有人做的总题量数sum(d[i])也会增加k倍，已知总题量为s,我们可以直接用除法计算出最大倍数，然后判断一下即可。

这题题目数据特殊，强调是一个不会出现任何环的图，可以用拓扑排序来搞，而spfa被无情的卡掉了。
还是贴出两份代码，一份spfa,一份tpsort
拓扑排序:

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
const int maxn = 6e5+10;
long long n,m,s;
vector<pii> g[maxn];
long long d[maxn];
int vis[maxn],ind[maxn];
long long bfs(int s){queue<int> pq;memset(d,-1,sizeof(d));d[s] = 0;pq.push(s);while(!pq.empty()){int top = pq.front();pq.pop();for(int i = 0;i < g[top].size(); i++){int v = g[top][i].first,w = g[top][i].second;ind[v]--;d[v]=max(d[v],d[top]+w);if(!ind[v]) pq.push(v);}}long long res = 0;for(int i = 1; i <= n; i++) res+=d[i];return res;
}
int main(){scanf("%lld%lld%lld",&n,&m,&s);for(int i = 1; i <= m; i++){int x,y,r;scanf("%d%d%d",&x,&y,&r);g[x].push_back(pii(y,r));ind[y]++;}for(int i = 1; i <= n; i++){				//这个建图方式，也可以用在tp排序，就不用入队所有度数为1的点g[0].push_back(pii(i,0));		//同样的，如果不建这一步，也可以搞spfa，把起点全部入队就行ind[i]++;}long long res = bfs(0);if(res==0) puts("-1");else if(res>s) puts("0");else printf("%lldn",s/res);
} 

贴出一份正确带判环的差分约束代码:(在这题会超时，但可作为板子学习)

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
const int maxn = 6e5+10;
long long n,m,s;
vector<pii> g[maxn];
long long d[maxn];
int vis[maxn];
bool spfa(int s){vis[s] = 1;for(int i = 0; i < g[s].size(); i++){int v = g[s][i].first,w = g[s][i].second;if(d[v]<d[s]+w){d[v] = d[s] + w;if(vis[v]) return true;if(spfa(v)) return true;}}vis[s] = 0;return false;
}
int main(){scanf("%lld%lld%lld",&n,&m,&s);for(int i = 1; i <= m; i++){int x,y,r;scanf("%d%d%d",&x,&y,&r);g[x].push_back(pii(y,r));}memset(d,-1,sizeof(d));d[0]=0;for(int i = 1; i <= n; i++)g[0].push_back(pii(i,0));bool f = spfa(0);long long res = 0;for(int i = 1; i <= n; i++) res+=d[i];//if(f) 有环 if(res==0) puts("-1");else if(res>s) puts("0");else printf("%lldn",s/res);
}