@[Boimet](/user/807950) 优化了吗
by HonkaiStarRail @ 2023-08-10 11:20:20
@[HonkaiStarRail](/user/592527) 不懂，有什么优化方法吗？
by Boimet @ 2023-08-10 11:35:44
@[HonkaiStarRail](/user/592527) 代码：
```cpp
#include<cstdio>
#include<climits>
#include<queue>
#include<cstring>
#include<cmath>
using namespace std;
#define ll long long
const int MAX_V = 5e3 + 1;
struct edge
{
int to, cap, cost, rev;
};
vector<edge> G[MAX_V];
int dist[MAX_V], prevv[MAX_V], preve[MAX_V], h[MAX_V], V, cost, flow;
typedef pair<int, int> P;
inline void add_edge(int from, int to, int cap, int cost)
{
G[from].push_back(edge{to, cap, cost, G[to].size()});
G[to].push_back(edge{from, 0, -cost, G[from].size() - 1});
}
void min_cost_flow(int s, int t)
{
for (;;)
{
priority_queue<P, vector<P>, greater<P> > que;
que.push(P(0, s));
fill(dist, dist + MAX_V, INT_MAX);
dist[s] = 0;
for (int dis, v; !que.empty(); )
{
v = que.top().second, dis = que.top().first;
que.pop();
if (dis > dist[v])
continue;
for (int i = 0; i < G[v].size(); ++i)
{
edge& e = G[v][i];
if (e.cap && dist[e.to] > dis + e.cost + h[v] - h[e.to])
{
dist[e.to] = dis + e.cost + h[v] - h[e.to],
prevv[e.to] = v,
preve[e.to] = i;
que.push(P(dist[e.to], e.to));
}
}
}
if (dist[t] == INT_MAX)
return;
for (int v = 1; v <= V; ++v)
h[v] += dist[v];
int d = INT_MAX;
for (int v = t; v != s; v = prevv[v])
d = min(d, G[prevv[v]][preve[v]].cap);
flow += d,
cost += d * h[t];
for (int v = t; v != s; v = prevv[v])
{
edge& e = G[prevv[v]][preve[v]];
e.cap -= d,
G[v][e.rev].cap += d;
}
}
}
int main()
{
int m, s, t;
scanf("%d%d%d%d", &V, &m, &s, &t);
for (int u, v, w, c; m--; )
{
scanf("%d%d%d%d", &u, &v, &w, &c);
add_edge(u, v, w, c);
}
min_cost_flow(s, t);
printf("%d %d\n", flow, cost);
return 0;
}
```
by Boimet @ 2023-08-10 11:36:20
@[Boimet](/user/807950) 堆优化啊
by HonkaiStarRail @ 2023-08-10 11:36:30
诶用了啊为啥过不了呢？？？
by HonkaiStarRail @ 2023-08-10 11:36:58
@[HonkaiStarRail](/user/592527) 我用的优先队列，不知道是不是常数原因
by Boimet @ 2023-08-10 11:37:10
这不对吧
by HonkaiStarRail @ 2023-08-10 11:37:28
@[Boimet](/user/807950) 应该是数据的事
by HonkaiStarRail @ 2023-08-10 11:40:19
dijkstra能处理有负权的吗？
by Richard_Whr @ 2023-10-01 09:58:54