网络流（二分图部分）的一堆题总结

11490DX Re: Master Lv.15
  2024-11-04 16:35:56 2024-11-04 16:35:56 Created   2025-03-21 11:22:29 2025-03-21 11:22:29 Updated      1.6k Words  8 Mins  

 

# P2764 最小路径覆盖问题

回到题目上，发现题目要求你让 中的顶点恰好在 的一条路上。并且 的路径不相交。相当于是每个点必须要被选 次。因为一个点在 中最多一个入度和一个出度，所以我们可以把一个点拆成两个点，入点 和出点 。一个入点/出点最多只能被选一次。然后一条从 连向 的边就被转化成了从 连向 。我们肯定是要让选的边数最大化的，并且每个点只能选一次。

于是这道题就被转化成了二分图的最大匹配。可以用匈牙利算法或是最大流跑一遍（本人用的最大流）即可得到答案。

Img

（图为将一个 DAG 转换为一个可以跑网络流的二分图。）

但是他还要求我们输出这些路径。于是我们想到，选了一条边就说明有一条从 连向 的路径（注意要剔除从 连出来的或是连向 的边，这种边可以用反边的流是否为 来判断。存储这条路径可以用链表来实现。发现这条路径被选了那就让链表中的 点指向 点。链表处理好了之后就可以遍历点 ，看哪个点没有被指向，就从这个点开始输出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include<bits/stdc++.h>
using namespace std;
const int N = 10005, M = 100005;
struct Edge{
    int to, nxt, w, cost;
}edge[M];
int h[N], cnt=1;
void _add(int x, int y, int w, int cost){
    edge[++cnt] = {y, h[x], w, cost};
    h[x] = cnt;
}
void add(int x, int y, int w, int cost){
    _add(x, y, w, cost), _add(y, x, 0, -cost);
}

int dis[N], vis[N];
int s, t, n, m;
bool spfa(){
    memset(dis, 0x3f, sizeof dis);
    vis[s] = 1;
    dis[s] = 0;
    queue<int>q;
    q.push(s);
    while(q.size()){
        int u = q.front();
        q.pop(), vis[u] = 0;
        for(int i=h[u];i;i=edge[i].nxt){
            int v = edge[i].to;
            if(edge[i].w&&dis[v]>dis[u]+edge[i].cost){
                dis[v] = dis[u] + edge[i].cost;
                if(!vis[v]) vis[v] = 1, q.push(v);
            }

        }
    }
    return dis[t] != 0x3f3f3f3f;
}
int cur[N], ret = 0;
int dfs(int x, int flow){
    if(x==t) return flow;
    vis[x] = 1;
    int ans = 0;
    for(int i=cur[x];i&&ans<flow;i=edge[i].nxt){
        cur[x] = i;
        int v = edge[i].to;
        if(edge[i].w&&!vis[v]&&dis[v]==dis[x]+edge[i].cost){
            int fl = dfs(v, min(edge[i].w, flow-ans));
            if(fl){
                ret += fl * edge[i].cost;
                edge[i].w -= fl;
                edge[i^1].w += fl;
                ans += fl;
            }
        }
    }
    vis[x] = 0;
    return ans;
}
int dinic(){
    int ans =0 ;
    while(spfa()){
        memcpy(cur, h, sizeof h);
        int x = 0;
        while(x = dfs(s, 0x3f3f3f3f)) ans += x;
    }
    return ans;
}

struct Chain{
    int nxt, ishead;
    //nxt:指向的下一个点，ishead：是否为一条路径的头
}chain[N];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin>>n>>m;
    int u, v;
    s = 0, t = 2*n+1;
    for(int i=1;i<=m;i++){
        cin>>u>>v;
        add(u, v+n, 1, 0);
    }
    for(int i=1;i<=n;i++){
        add(s, i, 1, 0);
        add(i+n, t, 1, 0);
    }
    int ans = dinic();
    for(int i=1;i<=n;i++){
        chain[i].ishead = 1;
    }
    for(int i=2;i<=cnt;i+=2){
        if(edge[i].to != t && edge[i^1].to != s){
            if(edge[i^1].w){
                chain[edge[i].to-n].ishead = 0;
                chain[edge[i^1].to].nxt = edge[i].to-n;
            }
        }
    }
    for(int i=1;i<=n;i++){
        if(chain[i].ishead){
            for(int j=i;j;j=chain[j].nxt){
                cout<<j<<' ';
            }
            cout<<'\n';
        }
    }
    cout<<n-ans<<'\n';
    return 0;
}

# P3033 Cow Steeplechase G

这道题要求我们选出最多的线段使他们不相交。那我们就想一想他们相交的情况。

首先判定相交是很简单的。然后我们可以把横着的线段分一个区域，竖着的线段分一个区域，每一个线段建一个点，有相交的情况就连边。这样就建出来了一个二分图。

接下来有一个结论：最多选出来的线段数 = 总线段数 - 二分图的最多匹配的线段数。怎么证明呢？

我们可以把最多选出来的线段数看成最少不能选的线段数，也就是只要不选这些线段，就是删除这些点，那么这个图的二分图最大匹配（最大流）就是 。

想到了什么？这就是最小割！又因为最小割 = 最大流定理，用最大流跑一遍求出最少不能选的线段数，再用 减去他就得到了答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include<bits/stdc++.h>
using namespace std;

const int N = 605, M = 200005;
struct Edge{
    int to, nxt, w, cost;
}edge[M];
int h[N], cnt=1;
void _add(int x, int y, int w, int cost){
    edge[++cnt] = {y, h[x], w, cost};
    h[x] = cnt;
}
void add(int x, int y, int w, int cost){
    _add(x, y, w, cost), _add(y, x, 0, -cost);
}

int dis[N], vis[N];
int s, t, n, m;
bool spfa(){
    memset(dis, 0x3f, sizeof dis);
    vis[s] = 1;
    dis[s] = 0;
    queue<int>q;
    q.push(s);
    while(q.size()){
        int u = q.front();
        q.pop(), vis[u] = 0;
        for(int i=h[u];i;i=edge[i].nxt){
            int v = edge[i].to;
            if(edge[i].w&&dis[v]>dis[u]+edge[i].cost){
                dis[v] = dis[u] + edge[i].cost;
                if(!vis[v]) vis[v] = 1, q.push(v);
            }

        }
    }
    return dis[t] != 0x3f3f3f3f;
}
int cur[N], ret = 0;
int dfs(int x, int flow){
    if(x==t) return flow;
    vis[x] = 1;
    int ans = 0;
    for(int i=cur[x];i&&ans<flow;i=edge[i].nxt){
        cur[x] = i;
        int v = edge[i].to;
        if(edge[i].w&&!vis[v]&&dis[v]==dis[x]+edge[i].cost){
            int fl = dfs(v, min(edge[i].w, flow-ans));
            if(fl){
                ret += fl * edge[i].cost;
                edge[i].w -= fl;
                edge[i^1].w += fl;
                ans += fl;
            }
        }
    }
    vis[x] = 0;
    return ans;
}
int dinic(){
    int ans =0 ;
    while(spfa()){
        memcpy(cur, h, sizeof h);
        int x = 0;
        while(x = dfs(s, 0x3f3f3f3f)) ans += x;
    }
    return ans;
}

struct Seg{
    int x1, y1, x2, y2;
}row[N>>1], col[N>>1];
int rowcnt = 0, colcnt = 0;
int main(){
    // freopen("P3033_2.in", "r", stdin);
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin>>n;
    int u, v, w, x;
    for(int i=1;i<=n;i++){
        cin>>u>>v>>w>>x;
        if(v==x&&u>w) swap(u, w);
        if(u==w&&v>x) swap(v, x);
        if(v==x){
            row[++rowcnt] = {u, v, w, x};
        }else col[++colcnt] = {u, v, w, x};
    }
    for(int i=1;i<=rowcnt;i++){
        for(int j=1;j<=colcnt;j++){
            int interx = col[j].x1, intery = row[i].y1;
            if(row[i].x1<=interx&&interx<=row[i].x2&&col[j].y1<=intery&&intery<=col[j].y2){
                add(i, j+rowcnt, 1, 0);
            }
        }
    }
    s=0, t=rowcnt+colcnt+1;
    for(int i=1;i<=rowcnt;i++)
        add(s, i, 1, 0);
    for(int i=1;i<=colcnt;i++){
        add(i+rowcnt, t, 1, 0);
    }
    int ans = dinic();
    cout<<n-ans<<'\n';
    return 0;
}
  • Title: 网络流（二分图部分）的一堆题总结
  • Author: 11490DX
  • Created at : 2024-11-04 16:35:56
  • Updated at : 2025-03-21 11:22:29
  • Link: https://11490dx.net/2024/11/04/flow-sum/
  • License: This work is licensed under CC BY-NC-SA 4.0.
Comments
On this page
网络流（二分图部分）的一堆题总结
  1. # P2764 最小路径覆盖问题
  2. # P3033 Cow Steeplechase G