文章

7

粉丝

387

获赞

7

访问

67.9k

头像
拆点二分图+拓扑排序+正向反向建图
P1536 清华大学2019年机试题
发布于2021年1月12日 20:45
阅读数 9.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;...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发