流れ

二部マチ

```c++
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
using namespace std;
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const int dx[4] = { 0, -1, 1, 0 };
const int dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}

template<class T1, class T2> void chmin(T1 &a, T2 b) { if (a>b)a = b; }

template<class T1, class T2> void chmax(T1 &a, T2 b) { if (a<b)a = b; }
template<class T>
void Add(T &a, const T &b, const T &mod = 1000000007) {
	int val = ((a % mod) + (b % mod)) % mod;
	if (val < 0) { val += mod; }
	a = val;
}
////////////////////////////////////////
int X, Y, E;
vector<int>G[210];
int match[210];
int visited[210];
bool dfs(int v,int cnt) {
	if (visited[v] == cnt) {
		return false;
	}
	visited[v] = cnt;
	for (int x : G[v]) {
		if (match[x] == -1) {
			match[x] = v;
			return true;
		}
		else {
			if (dfs(match[x],cnt)) {
				match[x] = v;
				return true;
			}
		}
	}
	return false;
}
int main() {
	cin >> X >> Y >> E;
	REP(i, E) {
		int x, y;
		cin >> x >> y;
		G[x].push_back(y);
	}
	REP(i, 210)match[i] = -1;
	int num = 0;
	REP(i, X) {
		if (dfs(i,i+1))num++;
	}
	cout << num << endl;
	return 0;
}
```
最大通信量
ネットワーク上の2台のコンピュータs,tがあり、sからtにデータを送りたい。このネットワーク上には全部でN台のコンピュータがありいくつかのコンピュータの間は一方向性の通信ケーブルで接続されていてそれぞれ1秒間に通信できる最大のデータ量が決まっている。他のコンピュータが通信を行っていない時sからtへ1秒間で最大どれだけのデータを送信することができるか？

これはford-fulkersonのアルゴリズムで解くことができる

```cpp

//辺を表す構造体:toは行先,capは容量,revは逆
struct edge { int to, cap, rev; };
vector<edge>G[10010];//グラフの隣接リスト表現
bool used[10010];//DFSですでに調べたかのグラフ
//fromからtoへ向かう容量capの辺をグラフに追加する
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 });
}
//増加パスをDFSで探す.
//sからtへ移動可能ならそのルートの最大流用を返し不可能なら0を返す。
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;
}
//sからtへの最大流量を返す
int max_flow(int s, int t) {
	int flow = 0;
	for (;;) {
		memset(used, 0, sizeof(used));
		int f = dfs(s, t, INF);
		if (f == 0) {
			return flow;
		}
		flow += f;
	}
}
int main() {
	int v, e;
	cin >> v >> e;
	REP(i, e) {
		int from, to, cost;
		cin >> from >> to >> cost;
		add_edge(from, to, cost);
	}
	cout << max_flow(0, v-1) << endl;
	return 0;
}
```
最小カット
ネットワークに対してsからtへのパスが存在しなくなるために除去しなければならない辺の容量の和の最小値はどれだけか

二部マッチング
N台のコンピュータとK個の仕事があります。1台のコンピュータには1つの仕事しか割り当てることができず各コンピュータごとにこなせる仕事の種類が異なる。最大でいくつの仕事をこなすことができるか求めなさい

これはグラフに落として考えることができる。無向二部グラフG=（U∪V,E)を次のように定義する

Uはコンピュータを表す頂点集合、Vは仕事を表す頂点集合でありu∈U,v∈Vに対しコンピュータuで仕事vをこなすことができる⇔(u,v)∈E

これは最大流の特殊ケースであるとみなすことができる。次のようにグラフを変形する
グラフの辺eをUからVへの方向に向き付け、容量を1とする。始点と終点を表す2つの頂点s,tを加え,sからtを加え、sからすべての頂点u∈Uに向かって容量1の辺をすべての頂点v∈Vからtに向かって容量1の辺を張る

こうして作られたグラフG`における最大s-tフローの流用がもとの二部グラフGにおける最大マッチングのサイズと等しくなりU-V間の流量が正な辺集合が最大マッチングとなる。

```cpp
//辺を表す構造体:toは行先,capは容量,revは逆
struct edge { int to, cap, rev; };
vector<edge>G[10010];//グラフの隣接リスト表現
bool used[10010];//DFSですでに調べたかのグラフ
//fromからtoへ向かう容量capの辺をグラフに追加する
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 });
}
//増加パスをDFSで探す.
//sからtへ移動可能ならそのルートの最大流用を返し不可能なら0を返す。
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;
}
//sからtへの最大流量を返す
int max_flow(int s, int t) {
	int flow = 0;
	for (;;) {
		memset(used, 0, sizeof(used));
		int f = dfs(s, t, INF);
		if (f == 0) {
			return flow;
		}
		flow += f;
	}
}
int main() {
	int N, K, E;
	cin >> N >> K >> E;
	bool can[110][110];//can[i][j]:=コンピュータiが仕事jをこなせる
	REP(i, 110)REP(j, 110)can[i][j] = false;
	//0～N-1:コンピュータに対応する頂点
	//N～N+K-1:仕事に対応する頂点
	int s = N + K, t = s + 1;
	//sとコンピュータを結ぶ
	for (int i = 0; i < N; ++i) {
		add_edge(s, i, 1);
	}
	//仕事とtを結ぶ
	for (int i = 0; i < K; ++i) {
		add_edge(N + i, t, 1);
	}
	REP(i, E) {
		int x, y;
		cin >> x >> y;
		can[x][y] = true;
	}
	//コンピュータと仕事を結ぶ
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < K; ++j) {
			if (can[i][j]) {
				add_edge(i, N + j, 1);
			}
		}
	}
	cout << max_flow(s, t) << endl;
	return 0;
}
```

```
int V;
int K, E;
vector<int>G[110];
bool used[110];
int match[110];
void add_edge(int u,int v) {
	G[u].push_back(v);
	G[v].push_back(u);
}
bool dfs(int v) {
	used[v] = true;
	for (int i = 0; i < G[v].size(); ++i) {
		int u = G[v][i], w = match[u];
		if (w < 0 || !used[w] && dfs(w)) {
			match[v] = u;
			match[u] = v;
			return true;
		}
	}
	return false;
}
int bipartite_matching() {
	int res = 0;
	memset(match, -1, sizeof(match));
	for (int v = 0; v < V; ++v) {
		if (match[v] < 0) {
			memset(used, 0, sizeof(used));
			if (dfs(v))res++;
		}
	}
	return res;
}
int main() {
	cin >> V >> K >> E;
	bool can[110][110];
	REP(i, 110)REP(j, 110)can[i][j] = false;
	int s = V + K, t = s + 1;
	for (int i = 0; i < V; ++i) {
		add_edge(s, i);
	}
	for (int i = 0; i < K; ++i) {
		add_edge(V + i, t);
	}
	REP(i, E) {
		int x, y;
		cin >> x >> y;
		can[x][y] = true;
	}
	for (int i = 0; i < V; ++i) {
		for (int j = 0; j < K; ++j) {
			if (can[i][j]) {
				add_edge(i, V + j);
			}
		}
	}
	cout << bipartite_matching() << endl;
	return 0;
}
```
なんか間違ってるコード

最小費用流
ネットワーク上の二台のコンピュータs,tがあり、sからtに毎秒サイズFのデータを送りたいとする。このネットワークには全部でN台のコンピュータがありいくつかのコンピュータの間は一方向性の通信ケーブルで接続されていてそれぞれ1秒間に通信できる最大のデータ量が決まっている。また各ケーブルごとに通信量が定まっており、通信量dのケーブルで毎秒サイズxのデータを転送する場合、dxの費用がかかる。データ転送にかかる費用の和を最小化せよ
まずは問題をグラフに直す。コンピュータを頂点としケーブルを辺とした有向グラフを考える。各辺eには容量c(e)とコストd(e)が定まっている。sからtへの流用Fのフローを流した時のΣe f(e)*d(e)の最小値が求めたい最小の費用となる。これは最大流の時のようなネットワークに新たに辺のコストが加わって流用の最大値ではなくある流用Fを流したときのコストの最小値を求める問題になっている。このような問題を最小費用流という。

```cpp
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#define _USE_MATH_DEFINES
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const ll dx[4] = { 0, -1, 1, 0 };
const ll dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
void mul(ll a, ll b) {
	a = a * b % INF;
}
double mysqrt(double x) {
	double l = 0, r = x;
	for (int i = 0; i < 64; ++i) {
		double m = (l + r) / 2.0;
		if (m*m < x)l = m;
		else r = m;
	}
	return l;
}
///////////////////////////////////////

//辺を表す構造体{行先、容量、コスト、逆辺}
struct edge { int to, cap, cost, rev; };
int V, E, F;
vector<edge>G[110];
int dist[110];
int prevv[110], preve[110];

void add_edge(int from, int to, int cap, int cost) {
	G[from].push_back(edge{ to, cap, cost, (int)G[to].size() });
	G[to].push_back(edge{ from,0,-cost,(int)G[from].size() - 1 });
}
//sからtへの流用fの最小費用流を求める
//流せない場合は-1を返す
int min_cost_flow(int s, int t, int f) {
	int res = 0;
	//ベルマンフォードによりs-t間最短路を求める
	while (f > 0) {
		fill(dist, dist + V, INF);
		dist[s] = 0;
		bool upgrade = true;
		while (upgrade) {
			upgrade = false;
			for (int v = 0; v < V; ++v) {
				if (dist[v] == INF)continue;
				for (int i = 0; i < G[v].size(); ++i) {
					edge &e = G[v][i];
					if (e.cap > 0 && dist[e.to] > dist[v] + e.cost) {
						dist[e.to] = dist[v] + e.cost;
						prevv[e.to] = v;
						preve[e.to] = i;
						upgrade = true;
					}
				}
			}
		}
		if (dist[t] == INF) {
			return -1;
		}
		int d = f;
		for (int v = t; v != s; v = prevv[v]) {
			d = min(d, G[prevv[v]][preve[v]].cap);
		}
		f -= d;
		res += d * dist[t];
		for (int v = t; v != s; v = prevv[v]) {
			edge &e = G[prevv[v]][preve[v]];
			e.cap -= d;
			G[v][e.rev].cap += d;
		}
	}
	return res;
}

int main() {
	cin >> V >> E >> F;
	REP(i, E) {
		int from, to, cap, cost;
		cin >> from >> to >> cap >> cost;
		add_edge(from, to, cap, cost);
	}
	cout << min_cost_flow(0,V-1,F) << endl;
	return 0;
}
```
最小費用流に帰着できる問題
abc 004 D マーブル

最大マッチング　最大独立集合

```cpp
//x+yが偶数か奇数かで分けることでグリッドの成すグラフは二部グラフになる。
//グラフの頂点の部分集合V'でどのv,uも辺で結ばれていない時V'を独立集合という。
//この問題は最大の独立集合を求める問題である。
//二部グラフの最大独立集合の大きさは 頂点の個数 - 最大マッチングの数 と等しくなる

char C[41][41];
vector<int>G[1700];
bool used[1700];
int match[1700];
bool dfs(int v) {
	used[v] = true;
	for (int i = 0; i < G[v].size(); ++i) {
		int u = G[v][i];
		int w = match[u];
		if (w < 0 || !used[w] && dfs(w)) {
			match[v] = u;
			match[u] = v;
			return true;
		}
	}
	return false;
}
```