結果

問題 No.654 Air E869120
コンテスト
ユーザー suikameron1
提出日時 2019-06-14 18:11:33
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 40 ms / 2,000 ms
コード長 2,689 bytes
コンパイル時間 2,235 ms
コンパイル使用メモリ 187,240 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-11-08 02:51:41
合計ジャッジ時間 3,809 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <math.h>
#include <bits/stdc++.h>//一括で読み込み
typedef long long ll;
using namespace std;

struct flowEdge 
{
	ll to, cap, rev;
};

class Max_Flow//最大流問題のDinic法。頂点数10^3,辺数10^4程度なら大体間に合う
{
public:
	vector<vector<flowEdge>> G;
	vector<ll>level, iter;

	void init(ll size_) 
  {
		G.resize(size_);
		level.resize(size_);
		iter.resize(size_);
	}

	void add_flowEdge(ll from, ll to, ll cap) 
  {
		G[from].push_back(flowEdge{to, cap, (ll)G[to].size()});
		G[to].push_back(flowEdge{from, 0, (ll)G[from].size()-1});
	}

	void bfs(ll s) 
  {
		for (ll i = 0; i < level.size(); i++) level[i] = -1;
		queue<ll> que;
		level[s] = 0;
		que.push(s);
		while (!que.empty())
    {
			ll v = que.front(); que.pop();
			for (ll i = 0; i < G[v].size(); i++)
      {
				flowEdge &e = G[v][i];
				if (e.cap > 0 && level[e.to] < 0) 
        {
					level[e.to] = level[v] + 1;
					que.push(e.to);
				}
			}
		}
	}

	ll dfs(ll v, ll t, ll f) 
  {
		if (v == t) return f;
		for (ll &i = iter[v]; i < G[v].size(); i++)
    {
			flowEdge &e = G[v][i];
			if (e.cap > 0 && level[v] < level[e.to])
      {
				ll 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;
	}

	ll max_flow(ll s, ll t)
  {
		ll flow = 0;
		for(;;)
    {
			bfs(s);
			if (level[t] < 0) return flow;
			for (int i = 0; i < iter.size(); i++) iter[i] = 0;
			ll f;
			while ((f = dfs(s, t, (1LL<<60))) > 0)
      {
				flow += f;
			}
		}
	}
};

ll n, m, d, u[1009], v[1009], p[1009], q[1009], w[1009];

vector<pair<ll, ll>> L;//最大流の頂点

int main()
{
	cin >> n >> m >> d;
	for (int i = 0; i < m; i++)//辺数
  {
		cin >> u[i] >> v[i] >> p[i] >> q[i] >> w[i];
    q[i] += d;
		L.push_back(make_pair(u[i], p[i]));//出発座標と時刻
		L.push_back(make_pair(v[i], q[i]));//到着座標と時刻
	}
	sort(L.begin(), L.end());
  
  Max_Flow X;
  X.init(L.size()+2);//頂点数で初期化
	for (int i = 0; i < m; i++) 
  {
		int pos1 = lower_bound(L.begin(), L.end(), make_pair(u[i], p[i])) - L.begin();//ソート後の頂点番号を求める
		int pos2 = lower_bound(L.begin(), L.end(), make_pair(v[i], q[i])) - L.begin();
		X.add_flowEdge(pos1, pos2, w[i]);//つなぐ頂点とコスト
	}
	for (int i = 1; i < L.size(); i++) 
  {
		if (L[i-1].first == L[i].first) X.add_flowEdge(i-1, i, (1LL<<60));
	}
	if(L[0].first == 1) X.add_flowEdge(L.size(), 0, (1LL<<60));
	if(L[L.size()-1].first == n) X.add_flowEdge(L.size()-1, L.size()+1, (1LL<<60));
  
	cout << X.max_flow(L.size(), L.size()+1) << endl;//開始頂点から終了頂点までの最大流を求める
	return 0;
}
0