为什么用dij会比spfa还慢一些?是我写残了吗
查看原帖
为什么用dij会比spfa还慢一些?是我写残了吗
291939
lihuazou楼主2020/11/3 19:09
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<queue>

#define int long long
#define inf 0x3f3f3f3f

using namespace std;

const int N = 110000;

struct node {
	int flow;
	int cost;
	int nxt;
	int to;
}edge[N << 1];

struct line {
	int pos;
	int dis;
	line() {};
	line(int p, int d) : pos(p), dis(d) {};
	bool operator <(const line& x)const {
		return dis > x.dis;
	}
};//堆优化

int cnt = 1, head[N], h[N], dis[N], vis[N], pre[N], nowflows[N];
int n, m, s, t, maxflows, mincost;

priority_queue<line> q;

int dijkstra() {
	for (int i = 1; i <= n; i++) {
		dis[i] = inf;
		vis[i] = 0;
	}
	while (!q.empty()) q.pop();
	dis[s] = 0, nowflows[s] = inf;
	q.push(line(s, dis[s]));
	while (!q.empty()) {
		int pos = q.top().pos;
		q.pop();
		if (vis[pos]) continue;
		vis[pos] = 1;
		for (int i = head[pos]; i; i = edge[i].nxt) {
			if (edge[i].flow <= 0) continue;
			int v = edge[i].to;
			if (dis[v] > dis[pos] + edge[i].cost + h[pos] - h[v]) {
				dis[v] = dis[pos] + edge[i].cost + h[pos] - h[v];
				q.push(line(v, dis[v]));
				nowflows[v] = min(nowflows[pos], edge[i].flow);
				pre[v] = i;
			}
		}
	}
	return dis[t] != inf;
}

void dinic() {
	while (dijkstra()) {
		for (int i = 1; i <= n; i++) {
			if (dis[i] != inf) {
				h[i] += dis[i];
			}
		}
		maxflows += nowflows[t];
		mincost += nowflows[t] * h[t];
		int x = t;
		while (x != s) {
			int y = pre[x];
			edge[y].flow -= nowflows[t];
			edge[y ^ 1].flow += nowflows[t];
			x = edge[y ^ 1].to;
		}
	}
}

void add(int u, int v, int flow, int w) {
	edge[++cnt].cost = w;
	edge[cnt].flow = flow;
	edge[cnt].to = v;
	edge[cnt].nxt = head[u];
	head[u] = cnt;
}

signed main() {
	scanf("%lld %lld %lld %lld", &n, &m, &s, &t);
	for (int i = 1; i <= m; i++) {
		int u, v, f, w;
		scanf("%lld %lld %lld %lld", &u, &v, &f, &w);
		add(u, v, f, w);
		add(v, u, 0, -w);
	}
	dinic();
	printf("%lld %lld\n", maxflows, mincost);
}
2020/11/3 19:09
加载中...