过不去样例球调
查看原帖
过不去样例球调
759274
Stevehim楼主2023/9/17 15:53
#include <bits/stdc++.h>
#define maxn 200010
#define int long long
using namespace std;
const int inf = INT_MAX;
int n, m, s, t; //源点和终点
inline int read() {
	int x = 0, f = 1;
	char ch = getchar();
	while (ch < '0' || ch > '9') {
		if (ch == '-') f = -1;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9') {
		x = x  * 10 + ch - '0';
		ch = getchar();
	}
	return x * f;
}
struct EDGE {
	int to, nxt, val, w; //w表示费用
} e[maxn << 1];
int head[maxn << 1];
int cnt = 1; //注意!
void add(int a, int b, int c, int d) {
	e[++cnt].to = b;
	e[cnt].val = c;
	e[cnt].w = d;
	e[cnt].nxt = head[a];
	head[a] = cnt;
}
bool vis[maxn];
struct NODE {
	int from; //该点的前一个点
	int edge; //与这个点相连的边
} node[maxn]; //这是用来存储已找到的赠广路的
//queue<int> q;
int dis[maxn]; //用来spfa

bool bfs() { //判断是否有增广路用的
	memset(vis, false, sizeof vis);
	memset(node, 0, sizeof node);
	memset(dis, 0x3f, sizeof dis);
	queue<int> q;
	q.push(s);
	vis[s] = true; //标记
	dis[s] = 0;
	while (!q.empty()) { //经典的spfa
		int u = q.front();
		vis[u] = false;
		q.pop();
		for (int i = head[u]; i; i = e[i].nxt) {
			int to = e[i].to;
			int w = e[i].w;
			if (e[i].val > 0 && dis[to] > dis[u] + w) {
				dis[to] = dis[u] + w;
				node[to].from = u;
				node[to].edge = i;
				if (!vis[to]) {
					q.push(to);
					vis[to] = true;
				}
			}
		}
	}
	return dis[t] != 0x3f3f3f3f;
}

int cost;
int EK() {
	int maxflow = 0; //最大流和最小费用
	int mi;
	cost = 0;
	while (bfs()) { //直到没有最短路
		mi = inf;
		for (int i = t; i != s; i = node[i].from) {
			mi = min(mi, e[node[i].edge].val);
		}
		for (int i = t; i != s; i = node[i].from) { //不要合并!
			e[node[i].edge].val -= mi; //正向减掉
			e[node[i].edge ^ 1].val += mi; //反向边加上
		}
		maxflow += mi;
		cost += mi * dis[t];
	}
	return maxflow;
}


int u, v, w, val;
signed main() {
	n = read(), m = read(), s = read(), t = read();
	for (int i  = 1; i <= m; i++) {
		u = read(), v = read(), val = read(), w = read();
		add(u, v, val, w);
		add(v, u, 0, -w); //注意:反向边的权值是0
	}
	printf("%lld\n", EK());
	printf("%lld", cost);
	return 0;
}
2023/9/17 15:53
加载中...