……为什么我也是63分
查看原帖
……为什么我也是63分
792595
wbw_121124楼主2024/8/15 20:49

能帮我调一下吗?这次是真的不会,不信看记录。

#include<bits/stdc++.h>
typedef int int32;
#define int long long
using namespace std;
const int N = 5e3 + 5;
int n, m, s, t, ans, dis[N], incf[N], maxi, sum[N], tot[N], cnt, c[N];
bool vis[N];
vector<pair<int, pair<int, int>>>nbr[N];
pair<int, pair<int, pair<int, int>>*>pre[N];
vector<int>b[N];
vector<pair<int, int>>d;
int work()
{
	memset(dis, 0x3f, sizeof dis);
	queue<int>q;
	q.push(s);
	dis[s] = incf[t] = 0;
	incf[s] = INT_MAX;
	while (!q.empty())
	{
		int u = q.front();
		q.pop();
		vis[u] = false;
		int cnt = 0;
		for (auto& [nxt, w] : nbr[u])
		{
			if (w.first && dis[u] + w.second < dis[nxt])
			{
				dis[nxt] = dis[u] + w.second;
				incf[nxt] = min(w.first, incf[u]);
				pre[nxt].first = u;
				pre[nxt].second = &nbr[u][cnt];
				if (!vis[nxt])
				{
					vis[nxt] = true;
					q.push(nxt);
				}
			}
			cnt++;
		}
	}
	return incf[t];
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m >> s >> t;
	for (int i = 1; i <= m; i++)
	{
		int x, y, z, a;
		cin >> x >> y >> z >> a;
		nbr[x].push_back({ y,{z,a} });
	}
	while (work())
	{
		ans += incf[t];
		int x = t;
		while (x != s)
		{
			pre[x].second->second.first -= incf[t];
			maxi += incf[t] * pre[x].second->second.second;
			x = pre[x].first;
		}
	}
	cout << ans << ' ' << maxi;
	return 0;
}
2024/8/15 20:49
加载中...