Submission #27842541

---

Source Code Expand

#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
#include <queue>
#define int long long
using namespace std;
int N, M;
int c[2010][2010];
int f[2010][2010];
int ca[2010][2010];
int inq[2010];
pair<int, int>d[2010];
vector<int>l[2010];
signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int K;
	cin >> N >> M>>K;
	int i;
	int sum = 0;
	for (i = 0; i < N; i++)
	{
		ca[0][i + 1] = -1;
		l[0].push_back(i + 1);
		l[i + 1].push_back(0);
	}
	for (i = 0; i < M; i++)
	{
		ca[i + N + 1][M + N + 1] = -1;
		l[M + N + 1].push_back(i + 1 + N);
		l[i + N + 1].push_back(1 + M + N);
	}
	for (i = 0; i < K; i++)
	{
		int a,b,cc;
		cin >> a>> b >> cc;
		a--;
		b--;
		ca[0][a+1]++;
		ca[b + N+1][M+N+1]++;
		ca[a + 1][b + N + 1] = 1;
		c[a + 1][b + N + 1] = -cc;
		c[b + N + 1][a + 1] = cc;
		l[a + 1].push_back(b + N + 1);
		l[b + N + 1].push_back(a + 1);
		sum += cc;
	}
	int ans = 0;
	int ans2 = 0;
	while (1)
	{
		memset(d, 1, sizeof(d));
		memset(inq, 0, sizeof(inq));
		d[0] = { 0,-1 };
		queue<int>q;
		q.push(0);
		while (q.size())
		{
			int j = q.front();
			q.pop();
			inq[j] = 0;
			int k;
			for (k = 0; k < l[j].size(); k++)
			{
				if (f[j][l[j][k]] != ca[j][l[j][k]] && (d[l[j][k]].first > d[j].first + c[j][l[j][k]]))
				{
					d[l[j][k]] = { d[j].first + c[j][l[j][k]],j };
					if (inq[l[j][k]] == 0)
					{
						q.push(l[j][k]);
						inq[l[j][k]] = 1;
					}
				}
			}
		}
		if (d[N + M + 1].first > (1LL << 40))
			break;
		int s = N + M + 1;
		int flow = 1000000000, cost = 0;
		while (s)
		{

			flow = min(flow, ca[d[s].second][s] - f[d[s].second][s]);
			s = d[s].second;
		}

		s = N + M + 1;
		while (s)
		{
			cost += c[d[s].second][s] * flow;
			f[d[s].second][s] += flow;
			f[s][d[s].second] -= flow;
			s = d[s].second;
		}
		if (cost > 0)
			break;
		ans2 += cost;
		ans += flow;
	}
	cout << sum+ans2;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:65:18: warning: comparison of integer expressions of different signedness: ‘long long int’ and ‘std::vector<long long int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   65 |    for (k = 0; k < l[j].size(); k++)
      |                ~~^~~~~~~~~~~~~

Judge Result