# 挑战程序竞赛系列（26）：3.5二分图匹配（1）

## POJ 1274: The perfect Stall

```    class Edge{
int from;
int to;
int cap;
int rev;
public Edge(int from, int to, int cap, int rev){
this.from = from;
this.to = to;
this.cap = cap;
this.rev = rev;
}
}

List<Edge>[] g;
int V;
void solve() {
Scanner in = new Scanner(System.in);
while (in.hasNext()){
int N = in.nextInt();
int M = in.nextInt();
V = N + M + 2;
int s = 0, t = N + M + 1;
g = new ArrayList[V];
for (int i = 0; i < V; ++i) g[i] = new ArrayList<Edge>();

for (int i = 1; i <= N; ++i){
}

for (int j = 1; j <= M; ++j){
}

for (int i = 1; i <= N; ++i){
int m = in.nextInt();
for (int j = 0; j < m; ++j){
int stall = in.nextInt();
}
}
System.out.println(fordFulkerson(s, t));
}
in.close();
}

public void addEdge(int from, int to, int cap){
g[to].add(new Edge(to, from, 0, g[from].size() - 1));
}

static final int INF = 1 << 30;
public int fordFulkerson(int s, int t){
int flow  = 0;
for (;;){
int f = dfs(s, t, INF, new boolean[V]);
if (f > 0) flow += f;
else break;
}
return flow;
}

public int dfs(int s, int t, int f, boolean[] visited){
if (s == t) return f;
visited[s] = true;
for (Edge e : g[s]){
int to = e.to;
if (!visited[to] && e.cap > 0){
int d = dfs(to, t, Math.min(f, e.cap), visited);
if (d > 0){
e.cap -= d;
g[to].get(e.rev).cap += d;
return d;
}
}
}
return 0;
}

void run() throws Exception {
solve();
}

public static void main(String[] args) throws Exception {
new SolutionDay21_P1274().run();
}```

```    List<Integer>[] g;
int V;
int N;
void solve() {
Scanner in = new Scanner(System.in);
while (in.hasNext()){
N = in.nextInt();
int M = in.nextInt();
V = N + M;
g = new ArrayList[V];
for (int i = 0; i < V; ++i) g[i] = new ArrayList<Integer>();

for (int i = 0; i < N; ++i){
int m = in.nextInt();
for (int j = 0; j < m; ++j){
int stall = in.nextInt();
addEdge(i, stall + N - 1);
}
}

System.out.println(bipartite_matching());
}
in.close();
}

public void addEdge(int from, int to){
}

public int bipartite_matching(){
int res = 0;
matching = new int[V];
Arrays.fill(matching, -1);
for (int i = 0; i < N; ++i){
if (matching[i] < 0){
if (dfs(i, new boolean[V])){
res ++;
}
}
}
return res;
}

int[] matching;
public boolean dfs(int v, boolean[] used){
used[v] = true;
for (int u : g[v]){
int w = matching[u];
if (w < 0 || !used[w] && dfs(w, used)){
matching[u] = v;
matching[v] = u;
return true;
}
}
return false;
}```

## POJ 2112: Optimal Milking

```    int[][] graph;
int V;
int K;
int C;
int M;
void solve() {
K = ni();
C = ni();
M = ni();
V = K + C + 2;

graph = new int[K + C][K + C];
for (int i = 0; i < K + C; ++i){
for (int j = 0; j < K + C; ++j){
int d = ni();
graph[i][j] = d != 0 ? d : INF;
}
}

int n = K + C;
for (int k = 0; k < n; ++k){
for (int i = 0; i < n; ++i){
for (int j = 0; j < n; ++j){
graph[i][j] = Math.min(graph[i][j], graph[i][k] + graph[k][j]);
}
}
}

int lb = 0, ub = 200 * n;
while (ub - lb > 1){
int mid = (ub + lb) / 2;
if (check(mid)) ub = mid;
else lb = mid;
}
out.println(ub);
}

public boolean check(int limit){
g = new ArrayList[V];
for (int i = 0; i < V; ++i) g[i] = new ArrayList<Edge>();

int s = 0;
int t = V - 1;

//源点到奶牛
for (int id = 0; id < C; ++id){
addEdge(s, id + 1 + K, 1);
}

//机器到汇点
for (int id = 0; id < K; ++id){
}

for (int cow = 0; cow < C; ++cow){
for (int ml = 0; ml < K; ++ml){
if (graph[cow + K][ml] <= limit){
addEdge(cow + K + 1, ml + 1, 1);
}
}
}

return maxFlow(s, t) == C;
}

public void addEdge(int from, int to, int cap){
g[to].add(new Edge(to, from, 0, g[from].size() - 1));
}

/************dinic************/
class Edge{
int from;
int to;
int cap;
int rev;
public Edge(int from, int to, int cap, int rev){
this.from = from;
this.to = to;
this.cap = cap;
this.rev = rev;
}
}

static final int INF = 1 << 28;
List<Edge>[] g;
public int maxFlow(int s, int t){
int flow = 0;
for (;;){
bfs(s);
if (level[t] < 0) break;
int f = 0;
while ((f = dfs(s, t, INF, new boolean[V])) > 0) flow += f;
}
return flow;
}

int[] level;
public void bfs(int s){
level = new int[V];
Arrays.fill(level, -1);
level[s] = 0;
queue.offer(s);
while (!queue.isEmpty()){
int v = queue.poll();
for (Edge e : g[v]){
int to = e.to;
if (level[to] < 0 && e.cap > 0){
level[to] = level[v] + 1;
queue.offer(to);
}
}
}
}

public int dfs(int s, int t, int f, boolean[] visited){
if (s == t) return f;
visited[s] = true;
for (Edge e : g[s]){
int to = e.to;
if (!visited[to] && e.cap > 0 && level[e.from] + 1 == level[to]){
int d = dfs(to, t, Math.min(f, e.cap), visited);
if (d > 0){
e.cap -= d;
g[to].get(e.rev).cap += d;
return d;
}
}
}
return 0;
}```

## POJ 1486: Sorting Slides

```5
1 4 1 4
2 7 2 7
5 11 5 11
8 13 9 14
9 14 8 13
3 3
3 3
6 6
10 10
12 12

(c,3)

```    class Point{
int x;
int y;
public Point(int x, int y){
this.x = x;
this.y = y;
}
}

class Slide{
int minX;
int maxX;
int minY;
int maxY;

public Slide(int minX, int maxX, int minY, int maxY){
this.minX = minX;
this.maxX = maxX;
this.minY = minY;
this.maxY = maxY;
}

public boolean contain(Point point){
int x = point.x;
int y = point.y;
return minX < x && x < maxX && minY < y && y < maxY;
}
}

Slide[] slides;
Point[] points;
int[] sliding;
int V;
void solve() {
int cnt = 0;
while (true){
int n = ni();
if (n == 0) break;
++cnt;
V = 2 * n;
init(V);

slides = new Slide[n];
points = new Point[n];

for (int i = 0; i < n; ++i) {
int minX = ni();
int maxX = ni();
int minY = ni();
int maxY = ni();
slides[i] = new Slide(minX, maxX, minY, maxY);
}

for (int i = 0; i < n; ++i) {
int x = ni();
int y = ni();
points[i] = new Point(x, y);
}

sliding = new int[n];
Arrays.fill(sliding, -1);
for (int i = 0; i < n; ++i){

for (int j = 0; j < n; ++j){
if (slides[i].contain(points[j])){
clear();
for (int k = 0; k < n; ++k){
for (int l = 0; l < n; ++l){
if (l == j && k == i) continue;
if (slides[k].contain(points[l])){
}
}
}

if (bipartiteMatching() == n - 1){
sliding[i] = j;
}
}
}
}
out.println("Heap " + cnt);
StringBuilder sb = new StringBuilder();
boolean hasOne = false;
for (int i = 0; i < n; ++i){
if (sliding[i] >= 0){
char c = (char) ('A' + i);
sb.append("(" + c + "," + (sliding[i] + 1) + ")" + " ");
hasOne = true;
}
}
if (hasOne)
out.println(sb.toString().substring(0, sb.length() - 1));
else
out.println("none");
out.println();
}
}

//二分图匹配
List<Integer>[] g;
int[] matching;
public void init(int V){
g = new ArrayList[V];
for (int i = 0; i < V; ++i) g[i] = new ArrayList<Integer>();
matching = new int[V];
}

public void clear(){
for (int i = 0; i < V; ++i){
g[i].clear();
}
}

public void addEdge(int from, int to){
}

public boolean dfs(int v, boolean[] visited){
visited[v] = true;
for (int u : g[v]){
int w = matching[u];
if (w == -1 || !visited[w] && dfs(w, visited)){
matching[u] = v;
matching[v] = u;
return true;
}
}
return false;
}

public int bipartiteMatching(){
int cnt = 0;
Arrays.fill(matching, -1);
for (int i = 0; i < V; ++i){
if (matching[i] < 0){
if (dfs(i, new boolean[V])){
cnt ++;
}
}
}
return cnt;
}```

0 条评论

• ### 挑战程序竞赛系列（21）：3.2反转

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.n...

• ### 挑战程序竞赛系列（28）：3.5最小费用流

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.n...

• ### K-th Smallest Prime Fraction

思路1： 一种聪明的做法，如果A = [1, 7, 23, 29, 47]，那么有：

• ### 挑战程序竞赛系列（32）：4.5 A*与IDA*

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.n...

• ### Day2上午解题报告

预计分数：100+0+60=160 实际分数：100+0+60=160 mmpT1数据错了。。。 T1遭遇 题目描述 你是能看到第一题的 friends呢。 —...

• ### 口算训练 HDU - 6287

小Q非常喜欢数学，但是他的口算能力非常弱。因此他找到了小T，给了小T一个长度为n的正整数序列a1,a2,…,an，要求小T抛出m个问题以训练他的口算能力。

• ### 基数排序简介及其并行化

基数排序号称线性时间排序算法中性能最好，速度最快的排序算法。本文将简要概括其算法思想，串行代码及其并行化。

• ### 浙大版《C语言程序设计（第3版）》题目集 习题6-2 使用函数求特殊a串数列和

给定两个均不超过9的正整数a和n，要求编写函数求a+aa+aaa++⋯+aa⋯a（n个a）之和。

• ### 浙大版《C语言程序设计（第3版）》题目集 习题5-4 使用函数求素数和

其中函数prime当用户传入参数p为素数时返回1，否则返回0；函数PrimeSum返回区间[m, n]内所有素数的和。题目保证用户传入的参数m≤n。

• ### 洛谷P1043 数字游戏

题目描述 丁丁最近沉迷于一个数字游戏之中。这个游戏看似简单，但丁丁在研究了许多天之后却发觉原来在简单的规则下想要赢得这个游戏并不那么容易。游戏是这样的，在你面前...