求助dinic是否写假
查看原帖
求助dinic是否写假
48311
altgo楼主2022/1/25 15:33

已经过题,但是时间比其他选手的劣很多。

希望能帮忙看一下,谢谢。

参考提交(别人的,总共59ms):https://www.luogu.com.cn/record/67846830

我的代码(总共279ms):

#include <bits/stdc++.h>
using namespace std;

#define fo(i,a,b) for(int i=a;i<=b;++i)
#define go(i,a) for(int i=cur[a];i;i=edge[i].nxt)
#define mem(a,b) memset(a,b,sizeof(a))
#define ll long long

const int N = 5005;
const int INF = 2e9;

int n, m;
struct nod {
	int y, nxt;
	int c;
}edge[N<<2];
int el = 1;
int Edgehead[N];
int dis[205];
int cur[205];
int S, T;
int q[205], head, tail;

void add (int x, int y, ll c) {
	el++;
	edge[el].y = y, edge[el].c = c, edge[el].nxt = Edgehead[x], Edgehead[x] = el;
	return;
}

void ins (int x, int y, ll c) {
	add (x, y, c);
	add (y, x, 0ll);
	return;
}

bool bfs () {
	mem (dis, -1);
	dis[S] = 0;
	q[head = 1] = S, tail = 2;
	while (head < tail) {
		int x = q[head++];
		cur[x] = 0;
		for (int i = Edgehead[x]; i; i = edge[i].nxt) {
			int y = edge[i].y;
			if (edge[i].c && dis[y] == -1) {
				if (!cur[x]) cur[x] = i;
				dis[y] = dis[x] + 1;
				q[tail++] = y;
			}
		}
	}
	return dis[T] != -1;
}

int dfs (int k, int flow) {
	if (k==T || !flow) return flow;
	int have = 0;
	go (i,k) {
		int y=edge[i].y;
		if (dis[y] == dis[k]+1 && edge[i].c) {
			int back = dfs (y, min(flow-have, edge[i].c));
			have += back;
			edge[i].c -= back;
			edge[i^1].c += back;
			if (have == flow)return flow;
		}
		cur[k] = edge[i].nxt;
	}
	dis[k] = -1;
	return have;
}

int main () {
//	freopen ("3376.in", "r", stdin);
	mem (Edgehead, 0);
	scanf ("%d %d %d %d", &n, &m, &S, &T);
	fo (i,1,m) {
		int x, y, c;
		scanf ("%d %d %d", &x, &y, &c);
		ins (x, y, c);
	}
	ll ans = 0;
	while (bfs ()) {
		ans += dfs (S, INF);
	}
	printf ("%lld\n", ans);
	return 0;
}
2022/1/25 15:33
加载中...