六省联考2017 問題の解法
P3745 [六省聯考 2017] 期末試験
m 種の試験があり、各試験 i は第 b_i 日に成績が発表される予定である。n 人の学生が成績を待っている。学生 i は第 t_i 日までにすべての成績を知りたいと思っている。最終的に最も遅く成績が出る試験の日を T とする。以下の3種類の不快度が生じる。
各学生は C × max(T - t_i, 0) の不快度を負担する。
試験 x を1日遅らせて試験 y ...
10月6日 06:50 投稿
ネットワークフローのテンプレート集
テンプレートは非常に重要です。
以下に、いくつかの高速で短いネットワークフローのテンプレートを紹介します。
1. 最大フロー
a. HLPP
バージョン1:
このバージョンには激しい最適化が施されています。
行数: 46行
実行時間: 全体で44ms
#include <cstdio>
using namespace std;
#define getchar() (S == T && (T = (S = BB) + fread(BB, 1, 1 << 15 ...
9月15日 06:54 投稿
ネットワーク最大流アルゴリズムの実装と最適化
ネットワーク最大流問題は、有向グラフ上で容量制限付きの辺を持つネットワークにおいて、ソース（始点）からシンク（終点）へ送ることのできる最大流量を求める古典的な最適化問題である。この問題は二部マッチングや資源配分など多くの応用に利用される。
基本概念
フローネットワーク：ソース s とシンク t を持つ有向グラフ。s からは流出のみ、t へは流入のみが許 ...
6月26日 18:51 投稿