結果

問題 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0