結果

問題 No.654 Air E869120
コンテスト
ユーザー tamurin
提出日時 2020-04-01 18:46:51
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 8 ms / 2,000 ms
コード長 2,546 bytes
コンパイル時間 1,237 ms
コンパイル使用メモリ 104,640 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-06-27 03:10:52
合計ジャッジ時間 2,586 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdlib>
#include <map>
#include <iomanip>
#include <set>
#include <stdio.h>
#include <ctype.h>
#include <string.h>
using namespace std;
#define pie 3.141592653589793238462643383279
#define mod 1000000007
#define INF 10000000000000000
#define int long long
#define all(vec) vec.begin(),vec.end()
#define P pair<int,int>
#define S second
#define F first

int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x%y);
}
int lcm(int x, int y) {
	return x / gcd(x, y)*y;
}
bool prime(int x) {
	for (int i = 2; i <= sqrt(x); i++) {
		if (x%i == 0)return false;
	}
	return true;
}
int kai(int x, int y) {
	int res = 1;
	for (int i = x - y + 1; i <= x; i++) {
		res *= i; res %= mod;
	}
	return res;
}
int mod_pow(int x, int y, int m) {
	int res = 1;
	while (y > 0) {
		if (y & 1) {
			res = res * x % m;
		}
		x = x * x % m;
		y >>= 1;
	}
	return res;
}

int comb(int x, int y) {
	if (y > x)return 0;
	return kai(x, y) * mod_pow(kai(y, y), mod - 2, mod) % mod;
}

struct edge { int to, cap, rev; };
vector<edge> g[3010];
bool used[3010];

void add_edge(int from, int to, int cap) {
	g[from].push_back(edge{ to,cap,(int)g[to].size() });
	g[to].push_back(edge{ from,0,(int)g[from].size() - 1 });
}

int dfs(int v, int t, int f) {
	if (v == t)return f;
	used[v] = true;
	for (int i = 0; i < g[v].size(); i++) {
		edge &e = g[v][i];
		if (!used[e.to] && e.cap > 0) {
			int d = dfs(e.to, t, min(f, e.cap));
			if (d > 0) {
				e.cap -= d;
				g[e.to][e.rev].cap += d;
				return d;
			}
		}
	}
	return 0;
}

int max_flow(int s, int t) {
	int flow = 0;
	while(1) {
		memset(used, 0, sizeof(used));
		int f = dfs(s, t, INF);
		if (f == 0)return flow;
		flow += f;
	}
}

int n, m, x, a[1010], b[1010], c[1010], d[1010], e[1010];
vector<P> vec;
int cnt;

signed main() {
	cin >> n >> m >> x;
	for (int i = 0; i < m; i++) {
		cin >> a[i] >> b[i] >> c[i] >> d[i] >> e[i];
		vec.push_back(make_pair(a[i], c[i]));
		vec.push_back(make_pair(b[i], d[i] + x));
	}
	sort(all(vec));
	vec.erase(unique(all(vec)), vec.end());
	for (int i = 0; i < (int)vec.size(); i++) {
		if (i&&vec[i - 1].first == vec[i].first) {
			add_edge(i - 1, i, INF);
		}
	}
	for (int i = 0; i < m; i++) {
		int xx = lower_bound(all(vec), make_pair(a[i], c[i])) - vec.begin();
		int yy = lower_bound(all(vec), make_pair(b[i], d[i] + x)) - vec.begin();
		add_edge(xx, yy, e[i]);
	}
	cout << max_flow(0, (int)vec.size() - 1) << endl;
}
0