先舉個例子，有N臺計算機和K個任務，每個計算機只能執行一個任務，但可以執行多種任務。現在給出N和K，和其關系，求出最多能處理的任務數。

這就是典型的二分圖，整張圖被分為兩半，一半是電腦，一半是任務。

這是多源點多匯點問題，我們只要加上兩個點后，就可以把問題轉換為單源單匯點問題。
如圖：

看到這個圖片大家肯定特別的熟悉，這不就轉換為了我們的最大流問題了，權值只不過都是固定的1而已，其他的都是套模板就行。下面代碼是FF，可以把其換位Dicnic，不過這道題FF也過了。

下面是poj3041例題AC代碼：http://poj.org/problem?id=3041

#include <iostream> #include <vector> #include <cstring> #include <cstdio> using namespace std;const int MAX_N = 500001; const int INF = 0x3f3f3f3f; struct edge {int to, cap, ves; };vector<edge> G[MAX_N]; bool used[MAX_N]; int N, K;void add_edge(int from, int to, int cost) {struct edge e = {to, cost, G[to].size()};G[from].push_back(e);struct edge v = {from, 0, G[from].size() - 1};G[to].push_back(v); }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.ves].cap += d;return d;}}}return 0; }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;} }void slove() {int s = N+K+1, t = s+1;for (int i=1; i<=N; i++){add_edge(s, i, 1);}for (int i=1; i<=K; i++){add_edge(N+i, t, 1);}for (int i=0; i<K; i++){int a, b;cin >> a >> b;add_edge(a, N+b, 1);} printf("%d\n", max_flow(s, t)); }int main() {scanf("%d %d", &N, &K);slove();return 0; }

總結

以上是生活随笔為你收集整理的二分图最大匹配（最大流）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。