社区讨论
求助各位大佬帮助卡常数
P3705[SDOI2017] 新生舞会参与者 4已保存回复 6
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 6 条
- 当前快照
- 1 份
- 快照标识符
- @mi7x55f1
- 此快照首次捕获于
- 2025/11/21 05:03 4 个月前
- 此快照最后确认于
- 2025/11/21 05:03 4 个月前
RT,已经卡到 分了……
是因为使用才导致了TLE吗?
CPP是因为使用才导致了TLE吗?
#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 条回复,欢迎继续交流。
正在加载回复...