文章
7
粉丝
387
获赞
7
访问
67.5k
首先把每个点拆成起点和终点(网络流建模的套路之一),每个点自己的花费就是从自己的起点到终点,a是b的前驱则可以把a的终点连到b的起点
计算f的话很简单,直接正向图拓扑排序,每一个时间取max,取终点的最大值即可
计算g的话则需要对反向图拓扑排序,取起点的max,然后用上面的最大值减去起点即可
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
int n, m;
int task_time;
int u, v;
ll ans_1, ans_2;
int read() {
int k = 0, f = 1;
char c = getchar_unlocked();
while (c < '0' || c>'9') {
if (c == '-')f = -1;
c = getchar_unlocked();
}
while (c >= '0' && c <= '9') {
k = (k << 1) + (k << 3) + c - 48;
c = getchar_unlocked();
}
return k * f;
}
void write(ll x) {
if (x < 0)putchar_unlocked('-'), x = -x;
if (x > 9)write(x / 10);
putchar_unlocked(x % 10 + 48);
}
ll AmulBmodP(ll a, ll b, ll p) {
ll ret = 0;
while (b) {
if (b & 1)
ret = (ret + a) % p;...
登录后发布评论
暂无评论,来抢沙发