社区讨论

求助各位大佬帮助卡常数

P3705[SDOI2017] 新生舞会参与者 4已保存回复 6

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
6 条
当前快照
1 份
快照标识符
@mi7x55f1
此快照首次捕获于
2025/11/21 05:03
4 个月前
此快照最后确认于
2025/11/21 05:03
4 个月前
查看原帖
RT,已经卡到 9090 分了……
是因为使用SPFA+DFS\text{SPFA+DFS}才导致了TLE吗?
CPP
#include <queue>
#include <iomanip>
#include <iostream>
#include <algorithm>

const int maxn = 100;
const double inf = 1.0 / 0.0, maxv = 1e7;

int a[105][105], b[105][105];

double ans, cost;
int n, s, t = 666, ptr = 1, temp = 0;

struct Node {
    bool vis = false;
    double dist = 0;
    int head = 0, cur = 0;
} node[1005];
struct Edge {
    double cost;
    int from, to, next, cap;
    Edge(int __from = 0, int __to = 0, int __next = 0, int __cap = 0) :
        cost(0), from(__from), to(__to), next(__next), cap(__cap) {}
} edge[1000005];

void addEdge(int u, int v) {
    edge[++ptr] = Edge(u, v, node[u].head, 1), node[u].head = ptr;
    edge[++ptr] = Edge(v, u, node[v].head, 0), node[v].head = ptr;
}

bool BFS() {
    bool flag = false;
    for (int i = s; i <= t; ++i)
        node[i].dist = inf,
        node[i].cur = node[i].head,
        node[i].vis = false;
    std::queue<int> q;
    q.push(s), node[s].dist = 0;
    while (!q.empty()) {
        int p = q.front();
        // std::cout << p << std::endl; 
        q.pop(), node[p].vis = false;
        for (int i = node[p].head; i; i = edge[i].next) {
            int x = edge[i].to;
            if (node[x].dist < node[p].dist + edge[i].cost || !edge[i].cap)
                continue;
            node[x].dist = node[p].dist + edge[i].cost;
            if (!node[x].vis) node[x].vis = true, q.push(x);
            if (x == t) flag = true;
        }
    }
    return flag;
}

int argue(int p, int flow) {
    // std::cout << "--- " << p << std::endl;
    if (node[p].vis) return 0;
    if (p == t || !flow)
        return flow;
    node[p].vis = true;
    int temp = 0, ans = 0;
    for (int &i = node[p].cur; i; i = edge[i].next) {
        int x = edge[i].to;
        if (node[x].dist != node[p].dist + edge[i].cost || !edge[i].cap)
            continue;
        if (temp = argue(x, std::min(flow - ans, edge[i].cap))) {
            edge[i].cap -= temp;
            edge[i ^ 1].cap += temp;
            ans += temp;
            cost += temp * edge[i].cost;
            if (ans >= flow)
                return ans;
        }
    }
    node[p].vis = false;
    return ans;
}

void Dinic() {
    int temp;
    while (BFS())
        while (temp = argue(s, 19260817))
            continue;
            // std::cout << "=== " << temp << std::endl;
}

bool check(double mid) {
    for (int i = temp + 1; i <= ptr; i += 2) {
        double val = b[edge[i].from][edge[i].to - maxn] * mid - a[edge[i].from][edge[i].to - maxn];
        edge[i].cost = val, edge[i ^ 1].cost = - val;
    }
    for (int i = 2; i <= ptr; i += 2)
        edge[i].cap = 1, edge[i + 1].cap = 0;
    cost = 0, Dinic();
    // std::cout << "----- " << cost << std::endl;
    return cost > 0;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin >> n;
    for (int i = 1; i <= n; ++i)
        addEdge(s, i),
        addEdge(i + maxn, t);
    temp = ptr;
    for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j)
        addEdge(i, j + maxn);
    for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j)
        std::cin >> a[i][j];
    for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j)
        std::cin >> b[i][j];
    double l = 0, r = maxv;
    // check(5.357143);
    for (int i = 0; i < 50; ++i) {
        double mid = (l + r) / 2;
        if (check(mid))
            r = mid;
        else
            l = mid;
        // std::cout << std::fixed << std::setprecision(6) << l << ' ' << r << std::endl;
    }
    std::cout << std::fixed << std::setprecision(6) << l << std::endl;
    return 0;
}

回复

6 条回复,欢迎继续交流。

正在加载回复...