Сколько доминошек максимум?
Сколько уголков максимум?
Инструменты и работы?
Max по включению в первую половину mincut?
Самолёты: максимальная вместимость самолёта?
Дан двудольный граф: выберите максимальное количество рёбер так, чтобы степени вершин были не более a_i?
Выберите ориентацию графа так, чтобы степени вершин были не более a_i?

Паросочетание "вес ребра = вес вершины первой доли"  (в конце)?