网络流2.0

一些网络流的常见建模方法：

  • 拆点：Luogu P1402 酒店之王、Luogu P2053 [SCOI2007] 修车、HDU7298 Coin
  • 二分图最小点覆盖：UVA11419 SAM I AM
  • 染色法：Luogu P2774 方格取数问题、Luogu P3355 骑士共存问题、Luogu P5030 长脖子鹿放置
  • 划分问题：Luogu P4313 文理分科
  • 平面图最小割转对偶图最短路：Luogu P2046 [NOI2010] 海拔、Luogu P4001 [ICPC-Beijing 2006] 狼抓兔子
  • DAG最小路径覆盖：Luogu P2764 最小路径覆盖问题、POJ2594 Treasure Exploration、Luogu P4298 [CTSC2008] 祭祀
  • 分层图：Luogu P2754 [CTSC1999] 家园 / 星际转移问题
  • 费用流：Luogu P2045 方格取数加强版、Luogu P1251 餐巾计划问题
  • 最大权闭合子图：Luogu P2762 太空飞行计划问题
  • 有源汇上下界可行流：ABC285G Tatami

（本文中没有用作例题的题目给出链接，它们的难度都不算大，在做完例题后应该可以独立完成）

Luogu P1402 酒店之王

题意

一家酒店有 pp 间房间，qq 道菜，每个房间只能住一位客人，每道菜也只能给一位客人吃。有 nn 个客人，每个人有喜欢的房间和菜。一位客人满意当且仅当他住进喜欢的房间并且吃到喜欢的菜，求最多能让多少客人满意。

题解

比较简单的题目。

将源点向每个房间连容量为 11 的边，每个房间向客人连容量为 00 或 11 的边，每个客人向每道菜连容量为 00 或 11 的边，每道菜向汇点连容量为 11 的边。

需要注意的是，要将每个客人拆成两个点，中间连一条容量为 11 的边，避免多个房间和多道菜分给了同一位客人的情况。

代码

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
#include <bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=405;
const int maxm=405*405;
struct edge
{
    int to,nxt;
    int c;
}e[2*maxm];
int cnt=1,head[maxn];
int s,t;
int d[maxn],cur[maxn];
void add(int u,int v,int c)
{
    e[++cnt]={v,head[u],c};head[u]=cnt;
    e[++cnt]={u,head[v],0};head[v]=cnt;
}
bool bfs()
{
    memset(d,0,sizeof(d));
    queue<int> q;
    d[s]=1;q.push(s);
    while(!q.empty())
    {
        int u=q.front();q.pop();
        for(int i=head[u];i;i=e[i].nxt)
        {
            int v=e[i].to;
            if(d[v]==0&&e[i].c)
            {
                d[v]=d[u]+1;q.push(v);
                if(v==t) return true;
            }
        }
    }
    return false;
}
int dfs(int u,int mf)
{
    if(u==t) return mf;
    int sum=0;
    for(int i=cur[u];i;i=e[i].nxt)
    {
        cur[u]=i;
        int v=e[i].to;
        if(d[v]==d[u]+1&&e[i].c)
        {
            int res=dfs(v,min(mf,e[i].c));
            e[i].c-=res;
            e[i^1].c+=res;
            sum+=res;
            mf-=res;
            if(mf==0) break;
        }
    }
    if(sum==0) d[u]=0;
    return sum;
}
int dinic()
{
    int flow=0;
    while(bfs())
    {
        memcpy(cur,head,sizeof(cur));
        flow+=dfs(s,inf);
    }
    return flow;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,p,q;cin>>n>>p>>q;
    s=0,t=p+n*2+q+1;
    for(int i=1;i<=p;i++) add(s,i,1);
    for(int i=p+1;i<=p+n;i++) add(i,i+n,1);
    for(int i=p+n*2+1;i<=p+n*2+q;i++) add(i,t,1);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=p;j++)
        {
            int c;cin>>c;
            add(j,i+p,c);
        }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=q;j++)
        {
            int c;cin>>c;
            add(p+n+i,p+n*2+j,c);
        }
    cout<<dinic()<<'\n';
    return 0;
}

UVA11419 SAM I AM

题意

有一个 r×cr\times c 的网格，有一些网格中有怪物。每次操作可以消灭一整行或一整列的怪物，求将所有怪物消灭的最小操作次数。

题解

二分图的最小点覆盖问题。

对于每一个怪物 (ri,ci)(r_i,c_i)，由 rir_i 向 cic_i 连边。最终的问题就转化为了在左侧和右侧选择一些点，使得每条边至少有一个端点被选。

为此，我们需要介绍一下König 定理：在二分图中，最小点覆盖=最大匹配数。

给出一个构造方案：从左侧未匹配的结点出发，走交错路。由于已求出最大匹配，原图中不存在增广路，所以这样的交错路一定以匹配边结束。最后，我们选择的集合为左侧未打标记的结点和右侧打了标记的结点。

（证明有待补充，感觉OI-Wiki上的证明有问题）

回到这道题目，考虑用网络流解决：事实上，我们只需要在残量网络上走有剩余容量的边。因为从 ss 出发有剩余容量的边一定指向了未匹配点，从该点出发有剩余容量的边一定是未匹配边，而从右侧点回到左侧点的是反边，有剩余容量代表原边没有剩余容量，则原边为匹配边，刚好满足条件。

代码

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
#include <bits/stdc++.h>
using namespace std;
const int maxn=2005;
const int maxm=1005*1005;
const int inf=0x3f3f3f3f;
struct edge
{
    int to,nxt;
    int c;
}e[2*maxm];
int cnt=1,head[maxn];
int s,t;
int d[maxn],cur[maxn];
bool vis[maxn];
void add(int u,int v,int c)
{
    e[++cnt]={v,head[u],c};head[u]=cnt;
    e[++cnt]={u,head[v],0};head[v]=cnt;
}
bool bfs()
{
    memset(d,0,sizeof(d));
    queue<int> q;
    d[s]=1;q.push(s);
    while(!q.empty())
    {
        int u=q.front();q.pop();
        for(int i=head[u];i;i=e[i].nxt)
        {
            int v=e[i].to;
            if(d[v]==0&&e[i].c)
            {
                d[v]=d[u]+1;q.push(v);
                if(v==t) return true;
            }
        }
    }
    return false;
}
int dfs(int u,int mf)
{
    if(u==t) return mf;
    int sum=0;
    for(int i=cur[u];i;i=e[i].nxt)
    {
        cur[u]=i;
        int v=e[i].to;
        if(d[v]==d[u]+1&&e[i].c)
        {
            int res=dfs(v,min(mf,e[i].c));
            e[i].c-=res;
            e[i^1].c+=res;
            sum+=res;
            mf-=res;
            if(mf==0) break;
        }
    }
    if(sum==0) d[u]=0;
    return sum;
}
int dinic()
{
    int flow=0;
    while(bfs())
    {
        memcpy(cur,head,sizeof(cur));
        flow+=dfs(s,inf);
    }
    return flow;
}
void dfs(int u)
{
    vis[u]=1;
    for(int i=head[u];i;i=e[i].nxt)
    {
        if(!e[i].c||vis[e[i].to]) continue;
        dfs(e[i].to);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int r,c,n;
    while(cin>>r>>c>>n,r||c|n)
    {
        cnt=1;
        memset(vis,0,sizeof(vis));
        for(int i=0;i<=r+c+1;i++) head[i]=0;
        s=0,t=r+c+1;
        for(int i=1;i<=r;i++) add(s,i,1);
        for(int i=r+1;i<=r+c;i++) add(i,t,1);
        for(int i=1;i<=n;i++)
        {
            int x,y;cin>>x>>y;
            add(x,y+r,1);
        }
        cout<<dinic()<<' ';
        dfs(0);
        for(int i=1;i<=r;i++)
            if(!vis[i]) cout<<"r"<<i<<' ';
        for(int i=r+1;i<=r+c;i++)
            if(vis[i]) cout<<"c"<<i-r<<' ';
        cout<<'\n';
    }
    return 0;
}

Luogu P2053 [SCOI2007] 修车

题意

有 nn 位顾客，每个顾客有一辆车要修。有 mm 名技术人员，不同技术人员对不同的车维修需要的时间不同，一名技术人员同一时间只能修一辆车。现在需要安排 mm 名技术人员所维修的车及顺序，使得顾客平均等待的时间最短。

题解

当一名技术人员修多辆车时，这种情况难以处理。我们考虑一下如果它修了 KK 辆车，他对总的等待时间的贡献是什么样的。设 TiT_i 为他修第 ii 辆车所需要的时间，那么总时间为

∑i=1KTi(K−i+1)\sum_{i=1}^KT_i(K-i+1)

我们发现，对于一辆车，如果知道它是技术人员修的第几辆车（或倒数第几辆车，这样更方便），那么它的贡献就可以算了。

所以我们想到拆点，将一名技术人员拆成 nn 个点，表示他修的倒数第 ii 辆车。将每辆车向这 nn 个点连边，若该技术人员修该车的时间为 TT，则连向第 ii 个点的边权为 T×iT\times i。然后跑最小费用最大流即可。

可能会有这样一种担心：如果某名技术人员的第 ii 个点选了，但第 i−1i-1 个点没选，这样是不是就不符合事实了。但是，对于同一辆车，向第 i−1i-1 个点的边费用肯定更小，所以不会出现这样的情况。

代码

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
#include <bits/stdc++.h>
using namespace std;
const int maxn=1005;
const int maxm=1005*1005;
const int inf=0x3f3f3f3f;
struct edge
{
    int to,nxt;
    int c,w;
}e[2*maxm];
int cnt=1,head[maxn];
int n,m,s,t;
int flow,val;
int d[maxn],vis[maxn],cur[maxn];
void add(int u,int v,int c,int w)
{
    e[++cnt]={v,head[u],c,w};head[u]=cnt;
    e[++cnt]={u,head[v],0,-w};head[v]=cnt;
}
bool spfa()
{
    memset(d,0x3f,sizeof(d));
    queue<int> q;
    q.push(s);d[s]=0;vis[s]=1;
    while(!q.empty())
    {
        int u=q.front();q.pop();vis[u]=0;
        for(int i=head[u];i;i=e[i].nxt)
        {
            int v=e[i].to;
            if(d[v]>d[u]+e[i].w&&e[i].c)
            {
                d[v]=d[u]+e[i].w;
                if(!vis[v]) q.push(v),vis[v]=1;
            }
        }
    }
    return d[t]!=inf;
}
int dfs(int u,int mf)
{
    if(u==t) return mf;
    vis[u]=1;
    int sum=0;
    for(int i=cur[u];i;i=e[i].nxt)
    {
        cur[u]=i;
        int v=e[i].to;
        if(!vis[v]&&d[v]==d[u]+e[i].w&&e[i].c)
        {
            int res=dfs(v,min(mf,e[i].c));
            e[i].c-=res;e[i^1].c+=res;
            sum+=res;
            val+=res*e[i].w;
            mf-=res;
            if(mf==0) break;
        }
    }
    if(sum==0) d[u]=0;
    vis[u]=0;
    return sum;
}
void ssp()
{
    while(spfa())
    {
        memcpy(cur,head,sizeof(cur));
        flow+=dfs(s,inf);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int m,n;cin>>m>>n;
    s=0,t=n+n*m+1;
    for(int i=1;i<=n;i++) add(s,i,1,0);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++) 
        {
            int x;cin>>x;
            for(int k=1;k<=n;k++) add(i,n+(k-1)*m+j,1,k*x);
        }
    for(int i=n+1;i<=n+n*m;i++) add(i,t,1,0);
    ssp();
    cout<<fixed<<setprecision(2)<<1.0*val/n<<'\n';
    return 0;
}

Luogu P2774 方格取数问题

题意

给出一个 n×mn\times m 的方格，每个方格中写了一个正整数。现要从方格中取数，要求取出的任意两数所在方格没有公共边，且取出的数的总和最大，求出最大的和。

题解

我们将方格黑白染色，可以发现当取了黑点以后，相邻的白点就不能取了，很像是二分图。将源点向所有的黑点连容量为点权的边，将黑点向相邻白点连容量为inf的边，将白点向汇点连容量为点权的边。只要求出图中的最小割，这就意味着我们先选择了所有的数，然后花费最少的代价删除了一些数，使得剩下的数两两之间没有公共边。（可以这样理解，源点到黑点的边意味着选择了这个点，那么与它相邻的白点一定可达（容量为inf），所以这些白点与汇点的边必须被割开）

代码

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
#include <bits/stdc++.h>
using namespace std;
const int maxn=105*105;
const int maxm=105*105*10;
const int inf=0x3f3f3f3f;
struct edge
{
    int to,nxt;
    int c;
}e[2*maxm];
int cnt=1,head[maxn];
int n,m,s,t;
int d[maxn],cur[maxn];
void add(int u,int v,int c)
{
    e[++cnt]={v,head[u],c};head[u]=cnt;
    e[++cnt]={u,head[v],0};head[v]=cnt;
}
bool bfs()
{
    memset(d,0,sizeof(d));
    queue<int> q;
    d[s]=1;q.push(s);
    while(!q.empty())
    {
        int u=q.front();q.pop();
        for(int i=head[u];i;i=e[i].nxt)
        {
            int v=e[i].to;
            if(d[v]==0&&e[i].c)
            {
                d[v]=d[u]+1;q.push(v);
                if(v==t) return true;
            }
        }
    }
    return false;
}
int dfs(int u,int mf)
{
    if(u==t) return mf;
    int sum=0;
    for(int i=cur[u];i;i=e[i].nxt)
    {
        cur[u]=i;
        int v=e[i].to;
        if(d[v]==d[u]+1&&e[i].c)
        {
            int res=dfs(v,min(mf,e[i].c));
            e[i].c-=res;
            e[i^1].c+=res;
            sum+=res;
            mf-=res;
            if(mf==0) break;
        }
    }
    if(sum==0) d[u]=0;
    return sum;
}
int dinic()
{
    int flow=0;
    while(bfs())
    {
        memcpy(cur,head,sizeof(cur));
        flow+=dfs(s,inf);
    }
    return flow;
}
bool inside(int x,int y) {return x>=1&&x<=n&&y>=1&&y<=m;}
int dir[4][2]={0,1,1,0,0,-1,-1,0};
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>m;
    s=0,t=n*m+1;
    int sum=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++) 
        {
            int a;cin>>a;
            sum+=a;
            if((i+j)&1) 
            {
                add(s,(i-1)*m+j,a);
                for(int k=0;k<4;k++)
                {
                    int x=i+dir[k][0],y=j+dir[k][1];
                    if(inside(x,y)) add((i-1)*m+j,(x-1)*m+y,inf);
                }
            }
            else add((i-1)*m+j,t,a);
        }
    cout<<sum-dinic()<<'\n';
    return 0;
}

Luogu P4313 文理分科

题意

有 n×mn\times m 位同学，用一个方阵表示。他们要选择学文科还是理科。

  • 若第 ii 行第 jj 列同学选择了文科，他将获得 arti,jart_{i,j} 的满意值；若选择了理科，他将获得 sciencei,jscience_{i,j} 的满意值。
  • 若第 ii 行第 jj 列同学选择了文科，且与他相邻的同学都选择了文科，他将获得 same_arti,jsame\_art_{i,j} 的满意值；若选择了理科，且与他相邻的同学都选择了理科，他将获得 same_sciencei,jsame\_science_{i,j} 的满意值。

求出所有人满意值之和的最大值。

题解

先考虑刻画一名同学只能选择文科或者理科。根据上一题，很容易想到由源点 ss 向每名同学连容量为 artart 的边，由每名同学向汇点 tt 连容量为 sciencescience 的边，用总和减去最小割，就是最大满意值。

但是，我们还需要处理相邻同学都选择文科或理科的情况。显然我们需要新加一些点，并且保证当这些点取得时，它所代表的那些同学都选择了对应的科目。可以这样考虑，对于每位同学，新建一个点，由源点向它连容量为 same_artsame\_art 的边，由它向它所代表的点连容量为 infinf 的边。这样，如果源点向它的边被选了，那么就可以通过这条边和 infinf 边走向它所代表的点。这时，这些点向汇点的边一定不能被选，代表这些人都选择了文科。对于理科也是同样的道理，反过来连边就可以了。

代码

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
111
112
113
114
115
116
117
#include <bits/stdc++.h>
using namespace std;
const int maxn=105*105*3;
const int maxm=105*105*20;
const int inf=0x3f3f3f3f;
struct edge
{
    int to,nxt;
    int c;
}e[2*maxm];
int cnt=1,head[maxn];
int n,m,s,t;
int d[maxn],cur[maxn];
void add(int u,int v,int c)
{
    e[++cnt]={v,head[u],c};head[u]=cnt;
    e[++cnt]={u,head[v],0};head[v]=cnt;
}
bool bfs()
{
    memset(d,0,sizeof(d));
    queue<int> q;
    d[s]=1;q.push(s);
    while(!q.empty())
    {
        int u=q.front();q.pop();
        for(int i=head[u];i;i=e[i].nxt)
        {
            int v=e[i].to;
            if(d[v]==0&&e[i].c)
            {
                d[v]=d[u]+1;q.push(v);
                if(v==t) return true;
            }
        }
    }
    return false;
}
int dfs(int u,int mf)
{
    if(u==t) return mf;
    int sum=0;
    for(int i=cur[u];i;i=e[i].nxt)
    {
        cur[u]=i;
        int v=e[i].to;
        if(d[v]==d[u]+1&&e[i].c)
        {
            int res=dfs(v,min(mf,e[i].c));
            e[i].c-=res;
            e[i^1].c+=res;
            sum+=res;
            mf-=res;
            if(mf==0) break;
        }
    }
    if(sum==0) d[u]=0;
    return sum;
}
int dinic()
{
    int flow=0;
    while(bfs())
    {
        memcpy(cur,head,sizeof(cur));
        flow+=dfs(s,inf);
    }
    return flow;
}
bool inside(int x,int y) {return x>=1&&x<=n&&y>=1&&y<=m;}
int dir[4][2]={1,0,0,1,-1,0,0,-1};
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>m;
    s=0,t=3*n*m+1;
    int sum=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++) 
        {
            int x;cin>>x;sum+=x;
            add(s,(i-1)*m+j,x);
        }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            int x;cin>>x;sum+=x;
            add((i-1)*m+j,t,x);
        }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            int x;cin>>x;sum+=x;
            add(s,n*m+(i-1)*m+j,x);
            add(n*m+(i-1)*m+j,(i-1)*m+j,inf);
            for(int k=0;k<4;k++)
            {
                int x=i+dir[k][0],y=j+dir[k][1];
                if(inside(x,y)) add(n*m+(i-1)*m+j,(x-1)*m+y,inf);
            }
        }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            int x;cin>>x;sum+=x;
            add(2*n*m+(i-1)*m+j,t,x);
            add((i-1)*m+j,2*n*m+(i-1)*m+j,inf);
            for(int k=0;k<4;k++)
            {
                int x=i+dir[k][0],y=j+dir[k][1];
                if(inside(x,y)) add((x-1)*m+y,2*n*m+(i-1)*m+j,inf);
            }
        }
    cout<<sum-dinic()<<'\n';
    return 0;
}

Luogu P5030 长脖子鹿放置

题意

在 n×mn\times m 的方格中放置一些长脖子鹿，使得它们不互相攻击。

题解

和方格取数很类似，但我们不能按 i+ji+j 的奇偶进行染色，因为我们会发现在这种情况下，长脖子鹿会攻击相同颜色的格子，这样就不是二分图了。

但是我们可以按照行的奇偶进行染色，这时就能得到一张二分图了。

代码

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 maxn=205*205;
const int maxm=205*205*10;
const int inf=0x3f3f3f3f;
struct edge
{
    int to,nxt;
    int c;
}e[2*maxm];
int cnt=1,head[maxn];
int s,t;
int d[maxn],cur[maxn];
void add(int u,int v,int c)
{
    e[++cnt]={v,head[u],c};head[u]=cnt;
    e[++cnt]={u,head[v],0};head[v]=cnt;
}
bool bfs()
{
    memset(d,0,sizeof(d));
    queue<int> q;
    d[s]=1;q.push(s);
    while(!q.empty())
    {
        int u=q.front();q.pop();
        for(int i=head[u];i;i=e[i].nxt)
        {
            int v=e[i].to;
            if(d[v]==0&&e[i].c)
            {
                d[v]=d[u]+1;q.push(v);
                if(v==t) return true;
            }
        }
    }
    return false;
}
int dfs(int u,int mf)
{
    if(u==t) return mf;
    int sum=0;
    for(int i=cur[u];i;i=e[i].nxt)
    {
        cur[u]=i;
        int v=e[i].to;
        if(d[v]==d[u]+1&&e[i].c)
        {
            int res=dfs(v,min(mf,e[i].c));
            e[i].c-=res;
            e[i^1].c+=res;
            sum+=res;
            mf-=res;
            if(mf==0) break;
        }
    }
    if(sum==0) d[u]=0;
    return sum;
}
int dinic()
{
    int flow=0;
    while(bfs())
    {
        memcpy(cur,head,sizeof(cur));
        flow+=dfs(s,inf);
    }
    return flow;
}
int n,m,k,tot,id[205][205],dir[8][2]={3,1,1,3,3,-1,-1,3,-3,1,1,-3,-3,-1,-1,-3};
bool vis[205][205];
bool inside(int x,int y) {return x>=1&&x<=n&&y>=1&&y<=m;}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>m>>k;
    for(int i=1;i<=k;i++)
    {
        int x,y;cin>>x>>y;
        vis[x][y]=1;
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(!vis[i][j]) id[i][j]=++tot;
    s=0,t=tot+1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            if(vis[i][j]) continue;
            if(i&1)
            {
                add(s,id[i][j],1);
                for(int k=0;k<8;k++)
                {
                    int x=i+dir[k][0],y=j+dir[k][1];
                    if(vis[x][y]||!inside(x,y)) continue;
                    add(id[i][j],id[x][y],inf);
                }
            }
            else add(id[i][j],t,1);
        }
    cout<<tot-dinic()<<'\n';
    return 0;
}

Luogu P2046 [NOI2010] 海拔

题意

有一张 n×nn\times n 的网格，每个格点有海拔 hh，每条双向边有流量 cc（正向与反向不一定相同）。一条边 (u,v)(u,v) 的代价为 max⁡(0,hv−hu)×c\max(0,h_v-h_u)\times c。规定左上角海拔为 00，右下角海拔为 11。要求标注其余点的海拔，使得总代价最小。

题解

一个并不显然的结论：每个点的海拔只会是 00 或者 11。在此基础上，我们可以知道 00 和 11 一定组成了两个连通块，它们之间的边的边权就是要付出的代价。所以，问题就转化为了求原图的最小割（割成的两部分分别是 00 和 11）。

然而，直接跑最小割会喜提TLE（我也没试过）。下面介绍一下我们需要用到的科技：平面图转对偶图。

对于平面图，有源点 ss，汇点 tt，且都在无限面的边界上。那么将 ss 和 tt 连一条边，新得到的面为 s∗s^*，无限面为 t∗t^*。将原平面图的各个面视为点，面与面的边界视为边（边界顺时针旋转90度），就将原图转换为了对偶图。

举个例子：

图1

一个重要的性质是：原图的 s−ts-t 最小割等于对偶图 s∗s^* 到 t∗t^* 的最短路。

所以只要用原图建出对偶图，跑一遍最短路就可以了。

代码

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
#include <bits/stdc++.h>
using namespace std;
const int N=500*500+5;
struct edge 
{
    int v,w;
};
struct node 
{
    int dis,u;
    bool operator<(const node& a)const {return dis>a.dis;}
};
vector<edge> g[N];
int dis[N];
bool vis[N];
priority_queue<node> q;
void dijkstra(int s) 
{
    memset(dis,0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    dis[s]=0;
    q.push({0,s});
    while(!q.empty()) 
    {
        int u=q.top().u;
        q.pop();
        if(vis[u]) continue;
        vis[u]=1;
        for(auto e:g[u]) 
        {
            int v=e.v,w=e.w;
            if(dis[v]>dis[u]+w) 
            {
                dis[v]=dis[u]+w;
                q.push({dis[v],v});
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;cin>>n;
    int s=0,t=n*n+1;
    for(int i=1;i<=n*(n+1);i++)
    {
        int w;cin>>w;
        g[max(0,i-n)].push_back({min(i,n*n+1),w});
    }
    for(int i=1;i<=n*(n+1);i++)
    {
        int w;cin>>w;
        if(i%(n+1)==1) g[i/(n+1)*n+1].push_back({t,w});
        else if(i%(n+1)==0) g[s].push_back({i/(n+1)*n,w});
        else g[i/(n+1)*n+i%(n+1)].push_back({i/(n+1)*n+i%(n+1)-1,w});
    }
    for(int i=1;i<=n*(n+1);i++)
    {
        int w;cin>>w;
        g[min(i,n*n+1)].push_back({max(0,i-n),w});        
    }
    for(int i=1;i<=n*(n+1);i++)
    {
        int w;cin>>w;
        if(i%(n+1)==1) g[t].push_back({i/(n+1)*n+1,w});
        else if(i%(n+1)==0) g[i/(n+1)*n].push_back({s,w});
        else g[i/(n+1)*n+i%(n+1)-1].push_back({i/(n+1)*n+i%(n+1),w});
    }
    dijkstra(s);
    cout<<dis[t]<<'\n';
    return 0;
}

Luogu P2764 最小路径覆盖问题

题意

给出一张DAG，要求用尽可能少的简单路径覆盖所有的点，满足所有路径不相交。

题解

首先将每个点当作一条路径，然后考虑合并。对于每条边 (u,v)(u,v)，它可以使得 uu 和 vv 合并。这让我们想到了二分图匹配。

将每个点 uu 拆成 u′u' 和 u′′u''。每条边 (u,v)(u,v) 看作是 u′u' 向 v′′v'' 连边，所有的 u′u' 构成 XX 点集，v′v' 构成 YY 点集，跑最大流即可。

输出方案时，可以根据 XX 点集向 YY 点集的满流的边得到每个点的后继结点，然后入度为 00 的点就是每条路径的起点。

代码

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
#include <bits/stdc++.h>
using namespace std;
const int maxn=150*2+5;
const int maxm=6005;
const int inf=0x3f3f3f3f;
struct edge
{
    int to,nxt;
    int c;
}e[2*maxm];
int cnt=1,head[maxn];
int s,t;
int d[maxn],cur[maxn];
void add(int u,int v,int c)
{
    e[++cnt]={v,head[u],c};head[u]=cnt;
    e[++cnt]={u,head[v],0};head[v]=cnt;
}
bool bfs()
{
    memset(d,0,sizeof(d));
    queue<int> q;
    d[s]=1;q.push(s);
    while(!q.empty())
    {
        int u=q.front();q.pop();
        for(int i=head[u];i;i=e[i].nxt)
        {
            int v=e[i].to;
            if(d[v]==0&&e[i].c)
            {
                d[v]=d[u]+1;q.push(v);
                if(v==t) return true;
            }
        }
    }
    return false;
}
int dfs(int u,int mf)
{
    if(u==t) return mf;
    int sum=0;
    for(int i=cur[u];i;i=e[i].nxt)
    {
        cur[u]=i;
        int v=e[i].to;
        if(d[v]==d[u]+1&&e[i].c)
        {
            int res=dfs(v,min(mf,e[i].c));
            e[i].c-=res;
            e[i^1].c+=res;
            sum+=res;
            mf-=res;
            if(mf==0) break;
        }
    }
    if(sum==0) d[u]=0;
    return sum;
}
int dinic()
{
    int flow=0;
    while(bfs())
    {
        memcpy(cur,head,sizeof(cur));
        flow+=dfs(s,inf);
    }
    return flow;
}
int in[maxn],f[maxn],nxt[maxn];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;cin>>n>>m;
    s=0,t=2*n+1;
    for(int i=1;i<=n;i++) add(s,2*i-1,1),add(2*i,t,1);
    for(int i=1;i<=m;i++)
    {
        int u,v;cin>>u>>v;
        add(u*2-1,v*2,1);
    }
    int ans=dinic();
    for(int i=1;i<=n;i++)
        for(int j=head[2*i-1];j;j=e[j].nxt)
        {
            if(!e[j].c&&e[j].to)
            {
                nxt[i]=e[j].to/2;
                in[e[j].to/2]++;
            }
        }
    for(int i=1;i<=n;i++)
    {
        if(in[i]) continue;
        for(int j=i;j;j=nxt[j]) cout<<j<<' ';
        cout<<'\n';
    }
    cout<<n-ans<<'\n';
    return 0;
}

POJ2594 Treasure Exploration

题意

给出一张DAG，要求用尽可能少的简单路径覆盖所有的点，不要求路径不相交。

题解

和上一题不同之处在于，不要求路径不相交。回想一下上一题我们是通过什么方式来限制路径不相交的？对，对于每一个结点，我们只与相邻的结点连边。而在这道题目中，我们要将每个结点与所有可达的结点连边。可达性的判断可以使用Floyd。

代码

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
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cstdio>
#include <queue>
using namespace std;
const int maxn=500*2+5;
const int maxm=500*500+5;
const int inf=0x3f3f3f3f;
struct edge
{
    int to,nxt;
    int c;
}e[2*maxm];
int cnt=1,head[maxn];
int s,t;
int d[maxn],cur[maxn];
void add(int u,int v,int c)
{
    e[++cnt]={v,head[u],c};head[u]=cnt;
    e[++cnt]={u,head[v],0};head[v]=cnt;
}
bool bfs()
{
    memset(d,0,sizeof(d));
    queue<int> q;
    d[s]=1;q.push(s);
    while(!q.empty())
    {
        int u=q.front();q.pop();
        for(int i=head[u];i;i=e[i].nxt)
        {
            int v=e[i].to;
            if(d[v]==0&&e[i].c)
            {
                d[v]=d[u]+1;q.push(v);
                if(v==t) return true;
            }
        }
    }
    return false;
}
int dfs(int u,int mf)
{
    if(u==t) return mf;
    int sum=0;
    for(int i=cur[u];i;i=e[i].nxt)
    {
        cur[u]=i;
        int v=e[i].to;
        if(d[v]==d[u]+1&&e[i].c)
        {
            int res=dfs(v,min(mf,e[i].c));
            e[i].c-=res;
            e[i^1].c+=res;
            sum+=res;
            mf-=res;
            if(mf==0) break;
        }
    }
    if(sum==0) d[u]=0;
    return sum;
}
int dinic()
{
    int flow=0;
    while(bfs())
    {
        memcpy(cur,head,sizeof(cur));
        flow+=dfs(s,inf);
    }
    return flow;
}
int dis[505][505];
int main()
{
    int n,m;
    while(scanf("%d %d",&n,&m),n||m)
    {
        cnt=1;
        memset(head,0,sizeof(head));
        memset(dis,0x3f,sizeof(dis));
        for(int i=1;i<=m;i++)
        {
            int u,v;scanf("%d %d",&u,&v);
            dis[u][v]=1;
        }
        for(int k=1;k<=n;k++)
            for(int i=1;i<=n;i++)
                for(int j=1;j<=n;j++) dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
        s=0,t=2*n+1;
        for(int i=1;i<=n;i++) add(s,i*2-1,1),add(i*2,t,1);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(dis[i][j]<0x3f3f3f3f) add(i*2-1,j*2,1);
        printf("%d\n",n-dinic());
    }
    return 0;
}

*Luogu P4298 [CTSC2008] 祭祀

题意

给出一张DAG，选择尽可能多的点，满足任意两点互不可达。要求求出这个值，给出一种可行的方案并对于每个点，判断是否有一种可行方案包含它。

题解

不是特别明白的一道题目，感觉要彻底弄懂还是得看相关的证明。

本题要求的是最长反链，由Dilworth定理，一个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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include <bits/stdc++.h>
using namespace std;
const int maxn=100*2+5;
const int maxm=100*100+5;
const int inf=0x3f3f3f3f;
struct edge
{
    int to,nxt;
    int c;
}e[2*maxm];
int cnt=1,head[maxn];
int s,t;
int d[maxn],cur[maxn];
void add(int u,int v,int c)
{
    e[++cnt]={v,head[u],c};head[u]=cnt;
    e[++cnt]={u,head[v],0};head[v]=cnt;
}
bool bfs()
{
    memset(d,0,sizeof(d));
    queue<int> q;
    d[s]=1;q.push(s);
    while(!q.empty())
    {
        int u=q.front();q.pop();
        for(int i=head[u];i;i=e[i].nxt)
        {
            int v=e[i].to;
            if(d[v]==0&&e[i].c)
            {
                d[v]=d[u]+1;q.push(v);
                if(v==t) return true;
            }
        }
    }
    return false;
}
int dfs(int u,int mf)
{
    if(u==t) return mf;
    int sum=0;
    for(int i=cur[u];i;i=e[i].nxt)
    {
        cur[u]=i;
        int v=e[i].to;
        if(d[v]==d[u]+1&&e[i].c)
        {
            int res=dfs(v,min(mf,e[i].c));
            e[i].c-=res;
            e[i^1].c+=res;
            sum+=res;
            mf-=res;
            if(mf==0) break;
        }
    }
    if(sum==0) d[u]=0;
    return sum;
}
int dinic()
{
    int flow=0;
    while(bfs())
    {
        memcpy(cur,head,sizeof(cur));
        flow+=dfs(s,inf);
    }
    return flow;
}
int dis[maxn][maxn],ans1[maxn],ans2[maxn];
bool vis[maxn],del[maxn];
void dfs(int u)
{
    vis[u]=1;
    for(int i=head[u];i;i=e[i].nxt)
    {
        if(!e[i].c||vis[e[i].to]) continue;
        dfs(e[i].to);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;cin>>n>>m;
    memset(dis,0x3f,sizeof(dis));
    for(int i=1;i<=m;i++) 
    {
        int u,v;cin>>u>>v;
        dis[u][v]=1;
    }
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++) dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
    s=0,t=2*n+1;
    for(int i=1;i<=n;i++) add(s,i*2-1,1),add(i*2,t,1);
    for(int i=1;i<=n;i++)  
        for(int j=1;j<=n;j++) 
            if(dis[i][j]<0x3f3f3f3f) add(i*2-1,j*2,1);
    int ans=n-dinic();
    cout<<ans<<'\n';
    dfs(0);
    for(int i=1;i<=n;i++)
        if(vis[i*2-1]&&!vis[i*2]) ans1[i]=1;
    for(int i=1;i<=n;i++) cout<<ans1[i];
    cout<<'\n';
    for(int k=1;k<=n;k++)
    {
        cnt=1;
        memset(head,0,sizeof(head));memset(del,0,sizeof(del));
        int tot=n-1;del[k]=1;
        for(int i=1;i<=n;i++)
            if(dis[k][i]<0x3f3f3f3f||dis[i][k]<0x3f3f3f3f) tot--,del[i]=1;
        for(int i=1;i<=n;i++) 
            if(!del[i]) add(s,i*2-1,1),add(i*2,t,1);
        for(int i=1;i<=n;i++)  
        {
            for(int j=1;j<=n;j++) 
                if(dis[i][j]<0x3f3f3f3f&&!del[i]&!del[j]) add(i*2-1,j*2,1);
        }
        if(tot-dinic()==ans-1) ans2[k]=1;
        else ans2[k]=0;
    }
    for(int i=1;i<=n;i++) cout<<ans2[i];
    return 0;
}

Luogu P2754 [CTSC1999] 家园 / 星际转移问题

题意

现有 nn 个太空站位于地球与月球之间，且有 mm 艘公共交通太空船在其间来回穿梭。每个太空站可容纳无限多的人，而太空船的容量是有限的，第 ii 艘太空船只可容纳 hih_i 个人。每艘太空船将周期性地停靠一系列的太空站，例如 (1,3,4)(1,3,4) 表示该太空船将周期性地停靠太空站 134134⋯134134\cdots。每一艘太空船从一个太空站驶往任一太空站耗时均为 11。人们只能在太空船停靠太空站(或月球、地球)时上、下船。

初始时所有人全在地球上，太空船全在初始站。试设计一个算法，找出让所有人尽快地全部转移到月球上的运输方案。

题解

根据时间动态加点加边。

枚举时间，将 ss 连向当前时刻的地球，当前时刻的月球连向 tt。对每艘太空船，从上一时刻经停位置连向当前时刻经停位置。增加这些边后，在残量网络上跑最大流，直到流量大于等于总人数。

代码

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
111
112
113
114
115
116
117
118
119
120
121
122
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
const int maxm=1e5+5;
const int inf=0x3f3f3f3f;
struct edge
{
    int v,nxt;
    int c;
}e[2*maxm];
int cnt=1,head[maxn];
int n,m,k,s=0,t=10000;
int d[maxn],cur[maxn];
void add(int u,int v,int w)
{
    e[++cnt]={v,head[u],w};head[u]=cnt;
    e[++cnt]={u,head[v],0};head[v]=cnt;
}
int h[25],r[25];
vector<int> vec[25];
int f[20];
int find(int x) {return f[x]==x?x:f[x]=find(f[x]);}
void merge(int x,int y)
{
    x=find(x),y=find(y);
    if(x!=y) f[x]=y;
}
bool bfs()
{
    memset(d,0,sizeof(d));
    queue<int> q;
    d[s]=1;q.push(s);
    while(!q.empty())
    {
        int u=q.front();q.pop();
        for(int i=head[u];i;i=e[i].nxt)
        {
            int v=e[i].v;
            if(d[v]==0&&e[i].c)
            {
                d[v]=d[u]+1;q.push(v);
                if(v==t) return true;
            }
        }
    }
    return false;
}
int dfs(int u,int mf)
{
    if(u==t) return mf;
    int sum=0;
    for(int i=cur[u];i;i=e[i].nxt)
    {
        cur[u]=i;
        int v=e[i].v;
        if(d[v]==d[u]+1&&e[i].c)
        {
            int res=dfs(v,min(mf,e[i].c));
            e[i].c-=res;
            e[i^1].c+=res;
            sum+=res;
            mf-=res;
            if(mf==0) break;
        }
    }
    if(sum==0) d[u]=0;
    return sum;
}
int dinic()
{
    int flow=0;
    while(bfs())
    {
        memcpy(cur,head,sizeof(cur));
        flow+=dfs(s,0x3f3f3f3f);
    }
    return flow;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>m>>k;
    for(int i=1;i<=n+2;i++) f[i]=i;
    for(int i=1;i<=m;i++)
    {
        cin>>h[i]>>r[i];
        for(int j=1;j<=r[i];j++)
        {
            int x;cin>>x;
            if(x==-1) x=n+2;
            else if(x==0) x=n+1;
            vec[i].push_back(x);
            if(j>1) merge(x,vec[i][(int)vec[i].size()-2]);
        }
    }
    if(find(n+1)!=find(n+2)) cout<<0<<'\n';
    else
    {
        n+=2;
        add(s,n-1,inf),add(n,t,inf);
        int sum=0,T=0;
        while(1)
        {
            T++;
            for(int i=1;i<=m;i++)
            {
                int now=vec[i][T%r[i]],pre=vec[i][(T-1+r[i])%r[i]];
                add(n*(T-1)+pre,n*T+now,h[i]);
            }
            add(s,n*T+n-1,inf),add(n*T+n,t,inf);
            for(int j=1;j<=n;j++) add((T-1)*n+j,T*n+j,inf);
            sum+=dinic();
            if(sum>=k) 
            {
                cout<<T<<'\n';
                break;
            }
        }
    }
    return 0;
}

Luogu P2045 方格取数加强版

题意

有一个 n×nn\times n 的矩阵，每一格有一个非负整数 ai,ja_{i,j}。现在从 (1,1)(1,1) 出发，可以往右或者往下走，最后到达 (n,n)(n,n)。每到达一格，把该格子的数取出来，该格子的数就变成 00。这样一共走 kk 次。要求取出的所有数之和最大。

题解

源点向 (1,1)(1,1)，(n,n)(n,n) 向汇点连容量为 kk，费用为 00 的边，表示一共可以走 kk 次。每个格子拆成两个点，连一条容量为 11，费用为 aa 的边，表示取一次数；再连一条容量为 infinf，费用为 00 的边，表示可以经过无数次。每个点和下方和右边的点连一条容量为 infinf，费用为 00 的边。

因为要求最大值，所以要跑最大费用最大流。可以将费用设为负数，跑完以后将得到的费用取反。

代码

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
#include <bits/stdc++.h>
using namespace std;
const int maxn=50*50*2+5;
const int maxm=50*50*8+5;
const int inf=0x3f3f3f3f;
struct edge
{
    int to,nxt;
    int c,w;
}e[2*maxm];
int cnt=1,head[maxn];
int n,m,s,t;
int flow,val;
int d[maxn],vis[maxn],cur[maxn];
void add(int u,int v,int c,int w)
{
    e[++cnt]={v,head[u],c,w};head[u]=cnt;
    e[++cnt]={u,head[v],0,-w};head[v]=cnt;
}
bool spfa()
{
    memset(d,0x3f,sizeof(d));
    queue<int> q;
    q.push(s);d[s]=0;vis[s]=1;
    while(!q.empty())
    {
        int u=q.front();q.pop();vis[u]=0;
        for(int i=head[u];i;i=e[i].nxt)
        {
            int v=e[i].to;
            if(d[v]>d[u]+e[i].w&&e[i].c)
            {
                d[v]=d[u]+e[i].w;
                if(!vis[v]) q.push(v),vis[v]=1;
            }
        }
    }
    return d[t]!=inf;
}
int dfs(int u,int mf)
{
    if(u==t) return mf;
    vis[u]=1;
    int sum=0;
    for(int i=cur[u];i;i=e[i].nxt)
    {
        cur[u]=i;
        int v=e[i].to;
        if(!vis[v]&&d[v]==d[u]+e[i].w&&e[i].c)
        {
            int res=dfs(v,min(mf,e[i].c));
            e[i].c-=res;e[i^1].c+=res;
            sum+=res;
            val+=res*e[i].w;
            mf-=res;
            if(mf==0) break;
        }
    }
    if(sum==0) d[u]=0;
    vis[u]=0;
    return sum;
}
void ssp()
{
    while(spfa())
    {
        memcpy(cur,head,sizeof(cur));
        flow+=dfs(s,inf);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,k;cin>>n>>k;
    s=0,t=n*n*2+1;
    add(s,1,k,0),add(n*n*2,t,k,0);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            int x;cin>>x;
            int id=(i-1)*n+j;
            add(id*2-1,id*2,1,-x);
            add(id*2-1,id*2,inf,0);
            if(j+1<=n) add(id*2,(id+1)*2-1,inf,0);
            if(i+1<=n) add(id*2,(id+n)*2-1,inf,0);
        }
    ssp();
    cout<<-val<<'\n';
    return 0;
}

Luogu P1251 餐巾计划问题

题意

一个餐厅在相继的 NN 天里,每天需用的餐巾数不尽相同。假设第 ii 天需要 rir_i块餐巾。餐厅可以购买新的餐巾,每块餐巾的费用为 pp 分;或者把旧餐巾送到快洗部,洗一块需 mm 天,其费用为 ff 分;或者送到慢洗部,洗一块需 nn 天(n>mn>m),其费用为 ss 分(s<fs<f)。

每天结束时,餐厅必须决定将多少块脏的餐巾送到快洗部,多少块餐巾送到慢洗部,以及多少块保存起来延期送洗。但是每天洗好的餐巾和购买的新餐巾数之和,要满足当天的需求量。

试设计一个算法为餐厅合理地安排好 NN 天中餐巾使用计划,使总的花费最小。编程找出一个最佳餐巾使用计划。

题解

由于每天开始时只有干净的餐巾可以使用，每天结束时只有脏的餐巾需要处理，所以可以把每一天拆成起始点和结束点。

  • 送到快洗部：从结束点连向 i+mi+m 天后的起始点，费用为 ff。
  • 送到慢洗部：从结束点连向 i+ni+n 天后的起始点，费用为 ss。
  • 延期送洗：从结束点连向下一天的结束点，不需要费用。
  • 购买餐巾：从源点连向每天的起始点，费用为 pp。

注意到快洗和慢洗是从结束点连向起始点，所以我们建图的时候一定是源点连向结束点，起始点连向汇点，这样这些边才具有意义。

代码

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=4005;
const int maxm=4005*20;
const int inf=0x3f3f3f3f;
struct edge
{
    int to,nxt;
    int c,w;
}e[2*maxm];
int cnt=1,head[maxn];
int s,t;
ll flow,val;
int d[maxn],vis[maxn],cur[maxn];
void add(int u,int v,int c,int w)
{
    e[++cnt]={v,head[u],c,w};head[u]=cnt;
    e[++cnt]={u,head[v],0,-w};head[v]=cnt;
}
bool spfa()
{
    memset(d,0x3f,sizeof(d));
    queue<int> q;
    q.push(s);d[s]=0;vis[s]=1;
    while(!q.empty())
    {
        int u=q.front();q.pop();vis[u]=0;
        for(int i=head[u];i;i=e[i].nxt)
        {
            int v=e[i].to;
            if(d[v]>d[u]+e[i].w&&e[i].c)
            {
                d[v]=d[u]+e[i].w;
                if(!vis[v]) q.push(v),vis[v]=1;
            }
        }
    }
    return d[t]!=inf;
}
int dfs(int u,int mf)
{
    if(u==t) return mf;
    vis[u]=1;
    int sum=0;
    for(int i=cur[u];i;i=e[i].nxt)
    {
        cur[u]=i;
        int v=e[i].to;
        if(!vis[v]&&d[v]==d[u]+e[i].w&&e[i].c)
        {
            int res=dfs(v,min(mf,e[i].c));
            e[i].c-=res;e[i^1].c+=res;
            sum+=res;
            val+=res*e[i].w;
            mf-=res;
            if(mf==0) break;
        }
    }
    if(sum==0) d[u]=0;
    vis[u]=0;
    return sum;
}
void ssp()
{
    while(spfa())
    {
        memcpy(cur,head,sizeof(cur));
        flow+=dfs(s,inf);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;cin>>N;
    s=0,t=2*N+1;
    for(int i=1;i<=N;i++) 
    {
        int r;cin>>r;
        add(s,i,r,0);
        add(i+N,t,r,0);
    }
    int p,m,f,n,ss;cin>>p>>m>>f>>n>>ss;
    for(int i=1;i<=N;i++)
    {
        add(s,i+N,inf,p);
        if(i+1<=N) add(i,i+1,inf,0);
        if(i+m<=N) add(i,i+N+m,inf,f);
        if(i+n<=N) add(i,i+N+n,inf,ss);
    }
    ssp();
    cout<<val<<'\n';
    return 0;
}

Luogu P2762 太空飞行计划问题

题意

W 教授正在为国家航天中心计划一系列的太空飞行。每次太空飞行可进行一系列商业性实验而获取利润。现已确定了一个可供选择的实验集合 $ E = { E_1, E_2, \cdots, E_m } $，和进行这些实验需要使用的全部仪器的集合 $ I = { I_1, I_2, \cdots, I_n } $。实验 $ E_j $ 需要用到的仪器是 $ I $ 的子集 $ R_j \subseteq I $。

配置仪器 $ I_k $ 的费用为 $ c_k $ 美元。实验 $ E_j $ 的赞助商已同意为该实验结果支付 $ p_j $ 美元。W 教授的任务是找出一个有效算法，确定在一次太空飞行中要进行哪些实验并因此而配置哪些仪器才能使太空飞行的净收益最大。这里净收益是指进行实验所获得的全部收入与配置仪器的全部费用的差额。

对于给定的实验和仪器配置情况，编程找出净收益最大的试验计划。

题解

讲一下最大权闭合子图。

闭合子图：对于一个有向图 GG，存在点集 SS，任取点 u∈Su\in S，uu 的出边的另一个点也属于 SS，则为闭合图。

最大权闭合子图：每个点有点权，点权之和最大的闭合图即为最大权闭合子图。

建模方法：源点向正权点连容量为点权的边，负权点向汇点连容量为点权相反数的边，原图中结点正常连容量为 infinf 的边。最小割即为答案。

ABC285G Tatami

题意

有一张 h×wh\times w 的网格，要求用 1×11\times 1 或 1×21\times 2 的小骨牌覆盖每个格子，每个格子被且仅被一块骨牌覆盖。格子有三种类型：

  • 1 只能被 1×11\times 1 骨牌覆盖
  • 2 只能被 1×21\times 2 骨牌覆盖
  • ? 可以被 1×11\times 1 或 1×21\times 2 骨牌覆盖。

判断是否存在一种覆盖方式。

题解

容易发现我们只需要用 1×21\times 2 的骨牌覆盖标有 2 的格子，剩下的都用 1×11\times 1 覆盖即可。将格子黑白染色后发现，一块 1×21\times2 的骨牌恰好覆盖一个白格和一个黑格，所以可以这样建图。若白格为 ?，从源点连一条下界为 00 上界为 11 的边，若为 2，连一条上下界均为 11 的边。然后向四周可以被覆盖的黑格连下界为 00 上界为 11 的边。若黑格为 ?，向汇点连一条下界为 00 上界为 11 的边，若为 2，连一条上下界均为 11 的边。然后跑有源汇上下界可行流就可以了。

代码

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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#include <bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=300*300+5;
const int maxm=300*300*4+5;
struct edge
{
    int to,nxt;
    int c;
}e[2*maxm];
int cnt=1,head[maxn];
int s,t;
int d[maxn],cur[maxn],diff[maxn];
char g[305][305];
void add(int u,int v,int c)
{
    e[++cnt]={v,head[u],c};head[u]=cnt;
    e[++cnt]={u,head[v],0};head[v]=cnt;
}
bool bfs()
{
    memset(d,0,sizeof(d));
    queue<int> q;
    d[s]=1;q.push(s);
    while(!q.empty())
    {
        int u=q.front();q.pop();
        for(int i=head[u];i;i=e[i].nxt)
        {
            int v=e[i].to;
            if(d[v]==0&&e[i].c)
            {
                d[v]=d[u]+1;q.push(v);
                if(v==t) return true;
            }
        }
    }
    return false;
}
int dfs(int u,int mf)
{
    if(u==t) return mf;
    int sum=0;
    for(int i=cur[u];i;i=e[i].nxt)
    {
        cur[u]=i;
        int v=e[i].to;
        if(d[v]==d[u]+1&&e[i].c)
        {
            int res=dfs(v,min(mf,e[i].c));
            e[i].c-=res;
            e[i^1].c+=res;
            sum+=res;
            mf-=res;
            if(mf==0) break;
        }
    }
    if(sum==0) d[u]=0;
    return sum;
}
int dinic()
{
    int flow=0;
    while(bfs())
    {
        memcpy(cur,head,sizeof(cur));
        flow+=dfs(s,inf);
    }
    return flow;
}
struct duedge
{
    int to,nxt;
    int l,r;
}e0[2*maxm];
int cnt0,head0[maxn];
void add0(int u,int v,int l,int r)
{
    e0[++cnt0]={v,head0[u],l,r};
    head0[u]=cnt0;
}
int in[maxn],out[maxn];
//flag=false 代表无源汇，flag=true 代表有源汇，默认源点为n+1,汇点为 n+2
bool UDflow(int n,bool flag)
{
    for(int u=1;u<=(flag?n+2:n);u++)
    {
        for(int i=head0[u];i;i=e0[i].nxt)
        {
            int v=e0[i].to,l=e0[i].l,r=e0[i].r;
            in[v]+=l,out[u]+=l;
            if(l!=r) add(u,v,r-l);
        }
    }
    for(int i=1;i<=(flag?n+2:n);i++)
    {
        if(in[i]>out[i]) add(s,i,in[i]-out[i]);
        if(out[i]>in[i]) add(i,t,out[i]-in[i]);
    }
    add(n+2,n+1,inf);
    dinic();
    for(int i=head[s];i;i=e[i].nxt)
        if(e[i].c) return 0;
    return 1;
}
int h,w,dir[4][2]={-1,0,0,-1,1,0,0,1};
bool inside(int x,int y) {return x>=1&&x<=h&&y>=1&&y<=w;}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>h>>w;
    int ss=h*w+1,tt=h*w+2;
    s=0,t=h*w+3;
    for(int i=1;i<=h;i++)
        for(int j=1;j<=w;j++) cin>>g[i][j];
    for(int i=1;i<=h;i++)
        for(int j=1;j<=w;j++)
            if((i+j)&1) 
            {
                if(g[i][j]=='2') add0(ss,(i-1)*w+j,1,1);
                if(g[i][j]=='?') add0(ss,(i-1)*w+j,0,1);
                for(int k=0;k<4;k++)
                {
                    int x=i+dir[k][0],y=j+dir[k][1];
                    if(inside(x,y)) add0((i-1)*w+j,(x-1)*w+y,0,1);
                }
            }
            else
            {
                if(g[i][j]=='2') add0((i-1)*w+j,tt,1,1);
                if(g[i][j]=='?') add0((i-1)*w+j,tt,0,1);
            }
    cout<<(UDflow(h*w,1)?"Yes":"No")<<'\n';
    return 0;
}
ACM
#网络流
网络流2.0
https://je3ter.github.io/2023/08/06/ACM/网络流2.0/
作者
Je3ter
发布于
2023年8月6日
许可协议