笔记汇总

差分约束

赛车游戏

转换思路，与其设置边权使路径长度相等，不如设置路径长度去拟合边权的限制。

设 $d_i$ 为 $1→i$ 的最短路，只需保证对于所有可从 $1→n$ 的路径上的边 $(u,v)$ 有 $w_{u,v}=dv−du$ 即可使任意一条简单路径长相等。于是 $1≤d_v−d_u≤9$，转化为 $du+9≥dv$ 与 $dv−1≥du$，差分约束求解即可。注意不在 $1→n$ 的任意一条路径上的边没有用，这些边不应计入限制，随便标权值。

#include<bits/stdc++.h>
#define ll long long
using namespace std;

/*
约束条件
d[a] + val<a,b> = d[b]
1 <= d[b] - d[a] <= 9
*/

const int N = 1e5 + 10, M = N << 2;
int head[N], Next[M], ver[M];
int edge[M], cnt = 1;
struct rec {
    int x, y;
} e[M >> 1];

void add(int x, int y, int v) {
    ver[++cnt] = y, edge[cnt] = v;
    Next[cnt] = head[x], head[x] = cnt;
}

void Add(int x, int y) {
    add(x, y, 0), add(y, x, 0);
}

bool v1[N], v2[N];
void check(int x, bool *flag, int op) {
    if(flag[x]) return;
    flag[x] = 1;
    for(int i = head[x]; i; i = Next[i]) {
        if((i & 1) == op) continue;
        int y = ver[i];
        check(y, flag, op);
    }
}

int dis[N], tot[N];
bool v[N];
void spfa(int n) {
    memset(dis, ~0x7f, sizeof dis), dis[1] = 0;
    queue<int> q;
    q.push(1), v[1] = 1;

    while(q.size()) {
        int x = q.front();
        q.pop(), v[x] = 0;

        for(int i = head[x]; i; i = Next[i]) {
            int y = ver[i], val = edge[i];
            if(dis[y] < dis[x] + val) {
                dis[y] = dis[x] + val;
                if(!v[y]) q.push(y), tot[y]++, v[y] = 1;
                if(tot[y] > n) puts("-1"), exit(0);
            }
        }
    }
    if(dis[n] < 0) puts("-1"), exit(0);
}

void clear() {
    memset(head, 0, sizeof head);
    memset(Next, 0, sizeof Next);
    memset(ver, 0, sizeof ver);
    cnt = 0;
}

bool is[N];
int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= m; i++) {
        scanf("%d %d", &e[i].x, &e[i].y);
        Add(e[i].x, e[i].y);
    }
    check(1, v1, 1), check(n, v2, 0);
    for(int i = 1; i <= n; i++)
        if(v1[i] && v2[i]) is[i] = 1;

    is[1] = is[n] = 1;
    clear();
    for(int i = 1; i <= m; i++) {
        if(is[e[i].x] && is[e[i].y]) {
            add(e[i].x, e[i].y, 1);
            add(e[i].y, e[i].x, -9);
        }
    }
    spfa(n);
    printf("%d %d\n", n, m);
    for(int i = 1; i <= m; i++) {
        printf("%d %d ", e[i].x, e[i].y);
        if(is[e[i].x] && is[e[i].y])
            printf("%d\n", dis[e[i].y] - dis[e[i].x]);
        else printf("1\n");
    }
    return 0;
}

倍杀测量者

将乘法计算转为 $log$ 计算。

/*
差分约束实现判断不等式组是否有解
有数值的地方记得double
存在女装的地方有两个
一、确定的点条件有问题
二、未确定的点有矛盾
*/
#include <bits/stdc++.h>
#define ak(t) printf("%d\n", t);
using namespace std;

const double ops = 1e-7;
const int N = 5e5 + 10;

int n, s, t;
int h[N], e[N], ne[N], idx;
double w[N], dist[N], k[N], c[N];   // k 是倍数，c 是分数
int op[N], a[N], b[N], p[N], cnt[N];// op 是符号，p 是人
bool st[N];         

void add(int a, int b, double c)
{
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++;
}

bool spfa() // 求最长路
{
    memset(st, false, sizeof st);   
    memset(dist, 0, sizeof dist);
    queue<int> q;
    q.push(0);
    st[0] = true;
    while (q.size())
    {
        int t = q.front();
        q.pop();
        st[t] = false;
        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] < dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;
                if (cnt[j] >= n) return true;
                if (!st[j])
                {
                    st[j] = true;
                    q.push(j);
                }
            }
        }
    }
    return false;
}

bool check(double del)
{
    idx = 0;
    memset(h, -1, sizeof h);
    memset(cnt, 0, sizeof cnt);
    for (int i = 1; i <= s; i ++ )  
    {
        if (op[i] == 1)
        {
            if (c[a[i]] && c[b[i]] && log2(c[a[i]]) < log2(c[b[i]])+log2(k[i]-del)) return true; // 提前判无解
            add(b[i], a[i], log2(k[i]-del));     // a[i] >= b[i] * (k[i] - del)
        }
        else 
        {
            if (c[a[i]] && c[b[i]] && log2(c[a[i]]) < log2(c[b[i]])-log2(k[i]+del)) return true; // 提前判无解
            add(b[i], a[i], -log2(k[i]+del));   // a[i] >= b[i] / (k[i] + del)
        }
    }
    for (int i = 1; i <= t; i ++ )
    {
        add(0, p[i], log2(c[p[i]]));
        add(p[i], 0, -log2(c[p[i]]));
    }
    for (int i = 1; i <= n; i ++ )
    {
        add(0, i, 0);
    }
    return spfa();
}
int main()
{
    scanf("%d%d%d", &n, &s, &t);
    for (int i = 1; i <= s; i ++ )
    {
        scanf("%d%d%d%lf", &op[i], &a[i], &b[i], &k[i]);
    }
    for (int i = 1; i <= t; i ++ )
    {
        scanf("%d", &p[i]);
        scanf("%lf", &c[p[i]]);
    }
    double l = 0, r = 10;

    while (r - l > ops)
    {
        double mid = (l + r) / 2.0;
        if (check(mid)) l = mid;
        else r = mid;
    }
    if (l == 0) puts("-1");     // 因为一直无解l是一直不会变的
    else printf("%0.4lf", l);
}

矩阵游戏

我们可以靠调整未确定的 $n+m-1$ 个元得到最终答案。

通过调整数据，我们可以转化为，$-a_{i, j} <= y - x <= 1e6 - a_{i, j}$

#include <bits/stdc++.h>
using namespace std;
const int N = 600 + 5;
int n, m, vis[N], len[N];
long long a[N][N], dis[N];
vector<pair<int, int>> e[N];
void solve() {
    cin >> n >> m;

    for (int i = 2; i <= n; i++)
        for (int j = 2; j <= m; j++) {
            scanf("%lld", &a[i][j]);
            a[i][j] -= a[i - 1][j] + a[i][j - 1] + a[i - 1][j - 1];
        }

    for (int i = 1; i <= n + m; i++)
        e[i].clear();

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            int x = i, y = n + j;

            if (i + j & 1 ^ 1)
                swap(x, y);

            e[x].push_back(make_pair(y, a[i][j]));  // x - y <= a(i, j) -- y - x >= -a(i, j)
            e[y].push_back(make_pair(x, 1e6 - a[i][j]));// y - x <= 1e6 - a(i, j)
        }

    memset(dis, 0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    queue<int> q;
    dis[1] = len[1] = 0, q.push(1);

    while (!q.empty()) {
        int t = q.front();
        q.pop(), vis[t] = 0;

        for (auto _ : e[t]) {
            int it = _.first;
            long long d = dis[t] + _.second;

            if (d < dis[it]) {
                dis[it] = d;

                if ((len[it] = len[t] + 1) >= n + m)
                    return puts("NO"), void();

                if (!vis[it])
                    vis[it] = 1, q.push(it);
            }
        }
    }

    puts("YES");

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            int x = i, y = n + j;

            if (i + j & 1 ^ 1)
                swap(x, y);

            printf("%lld%c", a[i][j] + dis[x] - dis[y], j == m ? '\n' : ' ');
        }
}
int main() {
    int T;
    cin >> T;
    while (T--) solve();

    return 0;
}