很奇怪啊，这是个什么奇怪的数据。不管怎么优化，第六个点始终过不去。总时间都只有3.08秒，六号点占了1.7秒。有大佬帮帮蒟蒻吗```cpp #include #include #include #include<string.h> #include #define datatype double #define Int register int template inline void read(T& t) { t = 0; char c = getchar(); int f = 1; while (c < '0' || c > '9') { if (c == '-') f = -f; c = getchar(); }while (c >= '0' && c <= '9') { t = (t << 3) + (t << 1) + c - '0'; c = getchar(); } t = f; } template <typename T, typename ... Args> inline void read(T& t, Args&... args) { read(t); read(args...); } template inline void write(T x) { if (x < 0) { x = -x; putchar('-'); }if (x > 9) write(x / 10); putchar(x % 10 + '0'); } using namespace std; typedef long long ll; enum { maxn =200, maxm = 50010, inf = 0x3f3f3f3f }; int too[2 * maxm], nextt[2 * maxm], floww[maxm * 2]; datatype coss[maxm * 2]; int head[maxn2], e_tot; double tans, eps = 1e-8; inline void add_edge(int from, int to, int flow, datatype c) { nextt[e_tot] = head[from];too[e_tot] = to; floww[e_tot] = flow;coss[e_tot] = c; head[from] = e_tot++; } bool vis[maxn];datatype dis[maxn]; inline void map_init(int n = maxn) { memset(head, 0xff, sizeof(head)); e_tot = 0; } bool SPFA(int s, int e) { memset(vis, 0, sizeof vis); //深搜前先清0 for (int i = 0; i < maxn; i++)dis[i] = 1e9; dis[e] = 0; vis[e] = 1; //SPFA维护距离标号要倒着跑，维护出到终点的最短路径 dequeq; q.push_back(e); //使用了SPFA的队列优化 while (!q.empty()) { int now = q.front(); q.pop_front(); for (int k = head[now]; k > -1; k = nextt[k]) { //下一行的k^1可保证正流 if (floww[k ^ 1] && dis[too[k]] > dis[now] - coss[k] - eps) { //SPFA倒着跑故flow[k]对应反向边是为正 dis[too[k]] = dis[now] - coss[k];//已经倒着，建边时反向边权为负，故负负得正 if (!vis[too[k]]) { vis[too[k]] = 1; if (!q.empty() && dis[too[k]] < dis[q.front()])q.push_front(too[k]); else q.push_back(too[k]); //距离最短的放前面，否则放队末 } } } vis[now] = 0; //此点搜完退出就要清0 } return dis[s] < 1e9; } pair<ll, datatype> dfs(int u, int e, int f) { if (u == e) { vis[e] = 1; return { f,0 }; } vis[u] = 1; pair<ll, datatype> res(0, 0); for (int p = head[u]; ~p; p = nextt[p]) { Int v = too[p]; if (!vis[v] && floww[p] && fabs(dis[u] - coss[p] - dis[v]) < eps) { auto temp = dfs(v, e, min(floww[p], f)); if (temp.first) { res.first += temp.first; res.second += temp.first * coss[p] + temp.second; floww[p] -= temp.first; floww[p ^ 1] += temp.first; f = max(0, f - floww[p]); } } } return res; } pair<ll, datatype> MCMF(int s, int e) {//first: maxflow, second: min cost pair<ll, datatype> ans(0, 0); while (SPFA(s, e)) { vis[e] = 1; while (vis[e]) { memset(vis, 0, sizeof(vis)); auto t = dfs(s, e, inf); ans.first += t.first; ans.second += t.second; } } return ans; } inline int read() { int s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar())if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar()) s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; } int a[110][110], b[110][110], n, m; bool check() { map_init(); for (int i = 1; i <= n; ++i) { add_edge(0, i, 1, 0); add_edge(i, 0, 0, 0); } for (int i = 1; i <= n; ++i) { add_edge(i + n, maxn - 1, 1, 0); add_edge(maxn - 1, i + n, 0, 0); } for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { double cost = a[i][j] - b[i][j] * tans; add_edge(i, j + n, 1, -cost); add_edge(j + n, i, 0, cost); } } auto ans = MCMF(0, maxn - 1); if (ans.second - eps < 0)return true; return false; } int main() { cin >> n; for (Int i = 1; i <= n; ++i) for (Int j = 1; j <= n; ++j) cin>>a[i][j]; for (Int i = 1; i <= n; ++i) for (Int j = 1; j <= n; ++j) cin>>b[i][j]; double l = 0, r = 10000, mid = 5000, ans = 0; while (r - l > eps) { mid = (l + r) / 2; tans = mid; if (check()) ans = l = mid; else r = mid; } printf("%.6lf", ans); }