为什么我跑得这么慢
查看原帖
为什么我跑得这么慢
254733
Night_Bringer楼主2020/12/4 13:05

题解就一共跑了几十毫秒,我最慢的就有一秒多

#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
#define LL long long
#define INF 0x3f3f3f3f
#define Min(a, b) ((a) < (b) ? (a) : (b))
void Quick_Read(LL &N) {
	N = 0;
	LL op = 1;
	char c = getchar();
	while(c < '0' || c > '9') {
		if(c == '-')
			op = -1;
		c = getchar();
	}
	while(c >= '0' && c <= '9') {
		N = (N << 1) + (N << 3) + (c ^ 48);
		c = getchar();
	}
	N *= op;
}
const LL MAXN = 2e2 + 5;
struct Node {
	LL to, value, rev;
	Node() {}
	Node(LL T, LL V, LL R) {
		to = T;
		value = V;
		rev = R;
	}
};
vector<Node> v[MAXN];
queue<LL> q;
LL de[MAXN], be[MAXN];
LL n, m, s, t;
bool bfs_Dinic() {
	memset(de, 0, sizeof(de));
	while(!q.empty())
		q.pop();
	q.push(s);
	de[s] = 1; be[s] = 0;
	while(!q.empty()) {
		LL now = q.front();
		q.pop();
		LL SIZ = v[now].size();
		for(int i = 0; i < SIZ; i++) {
			LL next = v[now][i].to;
			if(v[now][i].value && !de[next]) {
				q.push(next);
				be[next] = 0;
				de[next] = de[now] + 1;
				if(next == t)
					return true;
			}
		}
	}
	return false;
}
LL dfs_Dinic(LL now, LL flow) {
	if(now == t)
		return flow;
	int i, surp = flow;
	LL SIZ = v[now].size();
	for(i = be[now]; i < SIZ && surp; i++) {
		LL next = v[now][i].to, valedge = v[now][i].value;
		if(valedge && de[next] == de[now] + 1) {
			LL maxnow = dfs_Dinic(next, Min(surp, valedge));
			if(!maxnow)
				de[next] = 0;
			v[now][i].value -= maxnow;
			v[next][v[now][i].rev].value += maxnow;
			surp -= maxnow;
		}
	}
	be[now] = i;
	return flow - surp;
}
LL Dinic() {
	LL res = 0, flow = 0;
	while(bfs_Dinic())
		while(flow = dfs_Dinic(s, INF))
			res += flow;
	return res;
}
void Read() {
	LL A, B, C;
	Quick_Read(n);
	Quick_Read(m);
	Quick_Read(s);
	Quick_Read(t);
	for(int i = 1; i <= m; i++) {
		Quick_Read(A);
		Quick_Read(B);
		Quick_Read(C);
		LL idA = v[A].size(), idB = v[B].size();
		v[A].push_back(Node(B, C, idB));
		v[B].push_back(Node(A, 0, idA));
	}
}
int main() {
	Read();
	printf("%lld", Dinic());
	return 0;
}
2020/12/4 13:05
加载中...