网络流,网络流24题

搭配飞行员

二分图匹配的模板

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
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int maxn=200;
vector<int > g[maxn];
void addedge(int from,int to)
{
g[from].push_back(to);
g[to].push_back(from);
}
int match[maxn];
bool book[maxn];
bool dfs(int v)
{
book[v]=true;
for(unsigned i=0;i<g[v].size();i++)
{
int u=g[v][i];
if(book[u]==false)
{
book[u]=true;
if(match[u]==0 || dfs(match[u]))
{
match[u]=v;
match[v]=u;
return true;
}
}
}
return false;
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
int from;
int to;
while(scanf("%d%d",&from,&to)==2)
{
addedge(from,to);
}
int ans=0;
for(int i=1;i<=n;i++)
{
if(match[i]==0)
{
memset(book,0,sizeof(book));
if(dfs(i)) ans++;
}
}
printf("%d\n",ans);
return 0;
}

太空飞行计划

题意

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 教授的任务是找出一个有效算法,确定在一次太空飞行中要进行哪些实验并因此而配置哪些仪器才能使太空飞行的净收益最大。这里净收益是指进行实验所获得的全部收入与配置仪器的全部费用的差额。

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

题解

这个题的建模依赖于最大权闭合子图,闭合子图指的就是一个图的一个子图,其中所有点的出边对应的点都在这个子图中,最大权闭合子图顾名思义,即这个图每个点都拥有权值,某个闭合子图内的点权值之和最大,就是最大权闭合子图。这个题显然可以转化为一个带点权的图的形式,即象征实验的点有实验的报酬作为点权,仪器有仪器的花费(为负)作为点权。那么显然这个题可以转化为这个图上的最大权闭合子图。

而最大权闭合子图的权值等于所有正点权值减去最小割,证明如下:

  1. 最小割一定是简单割

简单割指得是:割(S,T)中每一条割边都与s或者t关联,这样的割叫做简单割。

因为在图中将所有与s相连的点放入割集就可以得到一个割,且这个割不为正无穷。而最小割一定小于等于这个割,所以最小割一定不包含无穷大的边。因此最小割一定一个简单割。

  1. 简单割一定和一个闭合子图对应

闭合子图V和源点s构成S集,其余点和汇点t构成T集。

首先证明闭合子图是简单割:若闭合子图对应的割(S,T)不是简单割,则存在一条边(u,v),$u\in S​$,$v\in T​$,且c(u,v)=∞。说明u的后续节点v不在S中,产生矛盾。

接着证明简单割是闭合子图:对于V中任意一个点u,$u\in S$。u的任意一条出边c(u,v)=∞,不会在简单割的割边集中,因此v不属于T,$v \in S$。所以V的所有点均在S中,因此S-s是闭合子图。

由上面两个引理可以知道,最小割也对应了一个闭合子图,接下来证明最小割就是最大权的闭合子图。

首先有割的容量C(S,T)=T中所有正权点的权值之和+S中所有负权点的权值绝对值之和

闭合子图的权值W=S中所有正权点的权值之和-S中所有负权点的权值绝对值之和

则有C(S,T)+W=T中所有正权点的权值之和+S中所有正权点的权值之和=所有正权点的权值之和

所以W=所有正权点的权值之和-C(S,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
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
#include <bits/stdc++.h>
using namespace std;
const int maxn=100+5;
const int maxd=200+10;
const int inf=0x3f3f3f3f;
struct edge{
int to,cap,rev;
edge(int to=0,int cap=0,int rev=0): to(to),cap(cap),rev(rev) {}
};
vector<edge > g[maxd];
void addedge(int u,int v,int cap)
{
g[u].push_back(edge(v,cap,g[v].size()));
g[v].push_back(edge(u,0,(int)g[u].size()-1));
}
int m,n,C[maxn],W[maxn],S,T,N;
vector<int > ops[maxn];
int dis[maxd+5],q[maxd+5];
bool bfs(int st,int ed)
{
memset(dis,-1,sizeof(dis));
dis[st]=0;
int head=0,tail=0;
q[head]=st;
while(head<=tail) {
int v=q[head%N];head++;
for(int i=0;i<(int)g[v].size();i++) {
edge &e=g[v][i];
if(e.cap>0 && dis[e.to]==-1) {
dis[e.to]=dis[v]+1;
tail++;q[tail%N]=e.to;
}
}
}
return ~dis[ed];
}
int las[maxd];
int dfs(int v,int ed,int F)
{
if(v==ed) return F;
else {
for(int& i=las[v];i<(int)g[v].size();i++) {
edge& e=g[v][i];
if(e.cap>0 && dis[e.to]==dis[v]+1) {
int d=dfs(e.to,ed,min(F,e.cap));
if(d>0) {
e.cap-=d;
g[e.to][e.rev].cap+=d;
return d;
}
}
}
return 0;
}
}
int Maxf(int st,int ed)
{
int ret=0,tmp=0;
while(bfs(st,ed)) {
memset(las,0,sizeof(las));
while((tmp=dfs(st,ed,inf))>0) ret+=tmp;
}
return ret;
}
int main()
{
scanf("%d%d",&m,&n);
int tot=0,x;
char c;
for(int i=1;i<=m;i++) {
scanf("%d",&C[i]);tot+=C[i];
while(1) {
c=getchar();
while(c==' ') c=getchar();
ungetc(c,stdin);
if(c=='\n' || c=='\r') break;
scanf("%d",&x);
ops[i].push_back(x);
}
}
for(int i=1;i<=n;i++) scanf("%d",&W[i]);
S=0,T=n+m+1;
N=n+m+5;
for(int i=1;i<=m;i++) addedge(S,i,C[i]);
for(int i=1;i<=n;i++) addedge(i+m,T,W[i]);
for(int i=1;i<=m;i++) {
for(int j=0;j<(int)ops[i].size();j++) {
addedge(i,ops[i][j]+m,inf);
}
}
tot-=Maxf(S,T);
for(int i=0;i<(int)g[S].size();i++) {
if(~dis[g[S][i].to]) {
printf("%d ",g[S][i].to);
}
}puts("");
for(int i=0;i<(int)g[T].size();i++) {
if(~dis[g[T][i].to]) printf("%d ",g[T][i].to-m);
}puts("");
printf("%d\n",tot);
return 0;
}

餐巾

题意

一个餐厅在相继的N天里,第i天需要Ri块餐巾(i=l,2,…,N)。餐厅可以从三种途径获得餐巾。

​ (1)购买新的餐巾,每块需p分;

​ (2)把用过的餐巾送到快洗部,洗一块需m天,费用需f分(f<p)。如m=l时,第一天送到快洗部的餐巾第二天就可以使用了,送慢洗的情况也如此。

​ (3)把餐巾送到慢洗部,洗一块需n天(n>m),费用需s分(s<f)。

​ 在每天结束时,餐厅必须决定多少块用过的餐巾送到快洗部,多少块送慢洗部。在每天开始时,餐厅必须决定是否购买新餐巾及多少,使洗好的和新购的餐巾之和满足当天的需求量Ri,并使N天总的费用最小。

题解

这个问题的主要约束条件是每天的餐巾够用,而餐巾的来源可能是最新购买,也可能是前几天送洗,今天刚刚洗好的餐巾。

每天用完的餐巾可以选择送到快洗部或慢洗部,或者留到下一天再处理。

经过分析可以把每天要用的和用完的分离开处理,建模后就是二分图。

二分图X集合中顶点$ X_i$表示第i天用完的餐巾,其数量为ri,所以从S向$X_i$连接容量为ri的边作为限制。

Y集合中每个点$Y_i$则是第i天需要的餐巾,数量为ri,与T连接的边容量作为限制。每天用完的餐巾可以选择留到下一天($X_i$->$ X_{i+1}$)

不需要花费,送到快洗部($ X_i$->$Y_{i+m}$),费用为f,送到慢洗部($X_i$->$Y_{i+n}$),费用为s。

每天需要的餐巾除了刚刚洗好的餐巾,还可能是新购买的(S->$Y_i$),费用为p。

在网络上求出的最小费用最大流,满足了问题的约束条件(因为在这个图上最大流一定可以使与T连接的边全部满流,其他边只要有可行流就满足条件),而且还可以保证总费用最小,就是我们的优化目标。

把每天分为二分图两个集合中的顶点$ X_i$,$Y_i$,建立附加源S汇T。

1、从S向每个$X_i$连一条容量为ri,费用为0的有向边。
2、从每个$Y_i$向T连一条容量为ri,费用为0的有向边。
3、从S向每个$Y_i$连一条容量为无穷大,费用为p的有向边。
4、从每个$X_i$向$ X_{i+1}$(i+1<=N)连一条容量为无穷大,费用为0的有向边。
5、从每个$X_i$向$Y_{i+m}$(i+m<=N)连一条容量为无穷大,费用为f的有向边。
6、从每个$X_i$向$Y_{i+n}$(i+n<=N)连一条容量为无穷大,费用为s的有向边。

求网络最小费用最大流,费用流值就是要求的最小总花费。

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=200+5;
const int dmax=400+15;
const int inf=0x3f3f3f3f;
int tot,S,T,N,R[maxn],p,m,f,n,s;
struct edge{
int to,cap,cost,rev;
edge(int to=0,int cap=0,int cost=0,int rev=0): to(to),cap(cap),cost(cost),rev(rev) {}
};
vector<edge > g[dmax];
void addedge(int u,int v,int cap,int cost)
{
g[u].push_back(edge(v,cap,cost,(int)g[v].size()));
g[v].push_back(edge(u,0,-cost,(int)g[u].size()-1));
}
typedef pair<int ,int > pii;
#define fir first
#define sec second
#define MP make_pair
bool inque[dmax];
int dis[dmax],q[dmax],prevv[dmax],preve[dmax];
pii spfa(int st,int ed)
{
int head=0,tail=0;
memset(dis,inf,sizeof(dis));
memset(inque,0,sizeof(inque));
dis[st]=0;inque[st]=true;
q[head]=st;
while(head<=tail) {
int v=q[head%N];head++;inque[v]=false;
for(int i=0;i<(int)g[v].size();i++) {
edge &e=g[v][i];
if(e.cap>0 && dis[e.to]>dis[v]+e.cost) {
dis[e.to]=dis[v]+e.cost;
if(!inque[e.to]) {
inque[e.to]=true;
tail++;q[tail%N]=e.to;
}
prevv[e.to]=v;
preve[e.to]=i;
}
}
}
if(dis[ed]==inf) return MP(0,-1);
int gap=inf;
for(int i=ed;i!=st;i=prevv[i]) {
gap=min(gap,g[prevv[i]][preve[i]].cap);
}
for(int i=ed;i!=st;i=prevv[i]) {
edge& e=g[prevv[i]][preve[i]];
e.cap-=gap;
g[e.to][e.rev].cap+=gap;
}
return MP(gap,dis[ed]*gap);
}
pii MaxF(int st,int ed)
{
pii ret=MP(0,0),tmp=MP(0,0);
while((tmp=spfa(st,ed)).fir>0) {
ret.fir+=tmp.fir;
ret.sec+=tmp.sec;
}
return ret;
}
int main()
{
scanf("%d",&tot);
for(int i=1;i<=tot;i++) scanf("%d",&R[i]);
scanf("%d%d%d%d%d",&p,&m,&f,&n,&s);
S=0,T=tot*2+1,N=tot*2+5;
for(int i=1;i<=tot;i++) {
addedge(S,i,R[i],0);
}
for(int i=1;i<=tot;i++) {
addedge(i+tot,T,R[i],0);
}
for(int i=1;i<=tot-1;i++) {
addedge(i,i+1,inf,0);
}
for(int i=1;i<=tot;i++) {
addedge(S,i+tot,inf,p);
}
for(int i=1;i<=tot;i++) {
if(i+m<=tot) addedge(i,i+m+tot,inf,f);
if(i+n<=tot) addedge(i,i+n+tot,inf,s);
}
printf("%d\n",MaxF(S,T).sec);
return 0;
}

魔术球

题意

假设有 $n$根柱子,现要按下述规则在这 $n$ 根柱子中依次放入编号为 $1,2,3,4 \cdots$ 的球。

  1. 每次只能在某根柱子的最上面放球。
  2. 在同一根柱子中,任何 $2$ 个相邻球的编号之和为完全平方数。

试设计一个算法,计算出在$n$ 根柱子上最多能放多少个球。

题解

如果两个球相加是完全平方数那么可以放在一起,以此为依据建边(枚举或者二分球有多少个),然后可以得出最大的匹配,这些匹配的实质是这些球可以放在一起。刚开始可以假定有$N$个球,并且每个球放在一个单独的柱子上,只要有一个匹配那么相当于我们可以节省一个柱子(相当于把一个球放到另一个上面),所以此时最小的柱子数就是$N-ans$($ans$为最大匹配)。当花费最少的柱子并且用的球最多,这时最少的柱子数等于题目所给的话就是答案。

如果枚举有多少个球,可以顺向建边,每次只需在原有的图上加边所以可以节省一些时间。

如果是二分,简单证明二分的单调性:如果存在一种这样的局面:我用了$k$个柱子和$x$个球,也可以用$l$个柱子放$y$个球,并且$k < l$ 并且$x >y $,那么证明$x$这个图的匹配比$y$要大,多的部分比$x-y$还要大(否则$k=l$,因为$x$的图是由$y$的图加边延伸而来。而$x-y$处最多产生$x-y$的匹配,矛盾,所以不可能出现这样的局面,并且反之亦然。

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
#include <bits/stdc++.h>
using namespace std;
const int maxn=65;
int head[5000+5],eg[100000+5],nxt[100000+5],tot=0,n;
void addedge(int u,int v)
{
eg[++tot]=v;nxt[tot]=head[u];head[u]=tot;
}
int vis[5000+5],mth[5000+5];
bool dfs(int u)
{
for(int i=head[u];i;i=nxt[i]) {
int v=eg[i];
if(!vis[v]) {
vis[v]=true;
if(!mth[v] || dfs(mth[v])) {
mth[v]=u;
return true;
}
}
}
return false;
}
bool jud(int x){return ((int)sqrt(x))*((int)sqrt(x))==x;}
int cal(int N)
{
memset(head,0,sizeof(head));tot=0;
for(int i=1;i<=N;i++)
for(int j=i+1;j<=N;j++) {
if(jud(i+j)) {
addedge(i,j);
}
}
int ans=0;
memset(mth,0,sizeof(mth));
for(int i=1;i<=N;i++) {
memset(vis,0,sizeof(vis));
assert(i<=1600);
if(dfs(i)) ans++;
}
return N-ans;
}
vector<int > ans[maxn];
int deg[1600+5];
int main()
{
scanf("%d",&n);
int L=1,R=1605;
while(L<=R) {
int mid=(L+R)>>1;
if(cal(mid)>n) R=mid-1;
else L=mid+1;
}
printf("%d\n",R);
for(int i=1;i<=R;i++) {
if(mth[i]) deg[mth[i]]++;
}
int tmp=0,sum=0;
for(int i=1;i<=R;i++) {
if(mth[i] && deg[i]==0) {
tmp=i;
ans[++sum].push_back(tmp);vis[tmp]=true;
while(mth[tmp]) {
ans[sum].push_back(mth[tmp]);
tmp=mth[tmp];
vis[tmp]=true;
}
}
}
for(int i=1;i<=R;i++) {
if(!vis[i]) {
ans[++sum].push_back(i);
}
}
for(int i=1;i<=sum;i++) {
for(int j=0;j<(int)ans[i].size();j++) {
printf("%d ",ans[i][j]);
}puts("");
}
return 0;
}

顺序枚举(大半年前写的,码风都和现在不一样)

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <queue>
#include <cmath>
using namespace std;
const int maxn=10000;
vector<int > g[maxn];
void addedge(int from,int to)
{
g[from].push_back(to);
g[to].push_back(from);
}
int match[maxn];
bool book[maxn];
int n;
bool judge(int n)
{
double nn=sqrt(n);
if((int)n/nn==nn)
{
return true;
}
return false;
}
bool dfs(int v)
{
for(unsigned i=0;i<g[v].size();i++)
{
int u=g[v][i];
if(!book[u])
{
book[u]=true;
if(match[u]==0 || dfs(match[u]))
{
match[u]=v;
match[v]=u;
return true;
}
}
}
return false;
}
bool cal(int res)
{
for(int i=1;i<=res-1;i++)
{
if(judge(i+res))
{
addedge(i,res+2000);
}
}
int ans=0;
for(int i=1;i<=res;i++)
{
if(match[i]==0)
{
memset(book,0,sizeof(book));
if(dfs(i))
{
ans++;
}
}
}
return (res-ans)<=n;
}
int main()
{
scanf("%d",&n);
int ans=1;
while(ans++)
{
memset(book,0,sizeof(book));
memset(match,0,sizeof(match));
if(!cal(ans))
{
break;
}
}
printf("%d\n",ans-1);
return 0;
}

最长递增子序列

题意

给定正整数序列$x_1 \sim x_n$,以下递增子序列均为非严格递增。

  1. 计算其最长递增子序列的长度 $s$。
  2. 计算从给定的序列中最多可取出多少个长度为$s$的递增子序列。
  3. 如果允许在取出的序列中多次使用$x_1$ 和 $x_n$,则从给定序列中最多可取出多少个长度为$s$ 的递增子序列。

题解

这个题就比较水了

首先最长递增子序列可以$dp$求得。

对于一个序列可以显而易见地转化为这样一张图:对于每个点,向它后面的所有大于等于它的数连边,那么最长递增子序列就是这个$DAG$上的最长链了。

然后对于第2,3个问题,容易想到费用流增广的时候,会用$spfa$先找到最短路然后增广,这样的话,我们可以人为的改为先找最长路然后增广。对于上述$DAG$将边权全部标为$1$,容量也为$1$,如果给每个点都加一个原点向他连得容量和费用都为$1$的边,每个点向终点加一条容量和费用都为$1$的边,那么最长路的条数就是可以从数列中拿出来的最长递增子序列的个数。而若$x_1$,$x_n$使用多次,那么可以对于$1,n$将它们与原点和终点的连边容量改为无穷大,然后再计算能增广多少次。复杂度最坏$O(n^3)$

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
#include <bits/stdc++.h>
using namespace std;
const int maxn=500+5;
const int dmax=1000+5;
const int inf=0x3f3f3f3f;
struct edge{
int to,cap,cost,rev;
edge(int to=0,int cap=0,int cost=0,int rev=0): to(to),cap(cap),cost(cost),rev(rev) {}
};
vector<edge > g[dmax];
void addedge(int u,int v,int cap,int cost)
{
g[u].push_back(edge(v,cap,cost,(int)g[v].size()));
g[v].push_back(edge(u,0,-cost,(int)g[u].size()-1));
}
typedef pair<int ,int > pii;
#define fir first
#define sec second
#define MP make_pair
bool inque[dmax];
int dis[dmax],q[dmax],prevv[dmax],preve[dmax],n,a[maxn],S,T,dp[maxn],ss,N;
pii spfa(int st,int ed)
{
int head=0,tail=0;
memset(dis,0,sizeof(dis));
memset(inque,0,sizeof(inque));
dis[st]=0;inque[st]=true;
q[head]=st;
while(head<=tail) {
int v=q[head%N];head++;inque[v]=false;
for(int i=0;i<(int)g[v].size();i++) {
edge &e=g[v][i];
if(e.cap>0 && dis[e.to]<dis[v]+e.cost) {
dis[e.to]=dis[v]+e.cost;
if(!inque[e.to]) {
inque[e.to]=true;
tail++;q[tail%N]=e.to;
}
prevv[e.to]=v;
preve[e.to]=i;
}
}
}
if(dis[ed]==inf) return MP(0,-1);
int gap=inf;
for(int i=ed;i!=st;i=prevv[i]) {
gap=min(gap,g[prevv[i]][preve[i]].cap);
}
for(int i=ed;i!=st;i=prevv[i]) {
edge& e=g[prevv[i]][preve[i]];
e.cap-=gap;
g[e.to][e.rev].cap+=gap;
}
return MP(dis[ed],gap);
}
int Count(int st,int ed)
{
pii tmp=MP(0,0);
int ret=0;
while((tmp=spfa(st,ed)).fir==ss+1) {
ret++;
}
return ret;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
memset(dp,inf,sizeof(dp));
dp[0]=0;
for(int i=1;i<=n;i++) {
dp[i]=1;
for(int j=1;j<=i-1;j++) {
if(a[j]<=a[i]) dp[i]=max(dp[i],dp[j]+1);
}
}
for(int i=1;i<=n;i++) ss=max(ss,dp[i]);
printf("%d\n",ss);
S=0,T=n+1,N=n+5;
for(int i=1;i<=n;i++) addedge(S,i,1,1),addedge(i,T,1,1);
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
if(a[i]<=a[j]) addedge(i,j,1,1);
printf("%d\n",Count(S,T));
for(int i=S;i<=T;i++) g[i].clear();
addedge(S,1,inf,1);addedge(1,T,inf,1);
addedge(S,n,inf,1);addedge(n,T,inf,1);
for(int i=2;i<=n-1;i++) addedge(S,i,1,1),addedge(i,T,1,1);
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
if(a[i]<=a[j]) addedge(i,j,1,1);
printf("%d\n",Count(S,T));
return 0;
}

方格取数问题

题意

在一个有 $m×n$ 个方格的棋盘中,每个方格中有一个正整数。

现要从方格中取数,使任意 $2$ 个数所在方格没有公共边,且取出的数的总和最大。试设计一个满足要求的取数算法。

题解

用黑白染色区分棋盘上的点,由于相邻两个是互斥的所以将相邻的点连边,求出的最大匹配即为互斥的二元组中较小权值的点之和,用所有点的和减去匹配即减去了所有有互斥关系的点对中较小权值(相当于保留了较大权值的一半,因为减掉的是最小流,即所有点对中权值较小的那个)。

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
#include <bits/stdc++.h>
using namespace std;
const int maxn=35;
const int inf=0x3f3f3f3f;
int a[maxn][maxn];
int n,m,S,T,tot=0;
struct edge{
int to,cap,rev;
edge(int to=0,int cap=0,int rev=0): to(to),cap(cap),rev(rev) {}
};
vector<edge > g[maxn*maxn+5];
inline int id(int x,int y){return (x-1)*m+y;}
void addedge(int u,int v,int cap)
{
g[u].push_back(edge(v,cap,g[v].size()));
g[v].push_back(edge(u,0,(int)g[u].size()-1));
}
int dis[maxn*maxn+5],q[maxn*maxn+5],N,cur[maxn*maxn+5];
bool bfs(int st,int ed)
{
memset(dis,-1,sizeof(dis));
dis[st]=0;
int head=0,tail=0;
q[head]=st;
while(head<=tail) {
int v=q[head%N];head++;
for(int i=0;i<(int)g[v].size();i++) {
edge& e=g[v][i];
if(e.cap>0 && dis[e.to]==-1) {
dis[e.to]=dis[v]+1;
tail++;q[tail%N]=e.to;
}
}
}
return (~dis[ed]);
}
int dfs(int v,int ed,int F)
{
if(v==ed) return F;
for(int &i=cur[v];i<(int)g[v].size();i++) {
edge& e=g[v][i];
if(e.cap>0 && dis[e.to]==dis[v]+1) {
int d=dfs(e.to,ed,min(F,e.cap));
if(d>0) {
e.cap-=d;
g[e.to][e.rev].cap+=d;
return d;
}
}
}
return 0;
}
int MaxF(int st,int ed)
{
int ret=0,tmp=0;
while(bfs(st,ed)) {
memset(cur,0,sizeof(cur));
while((tmp=dfs(st,ed,inf))>0) ret+=tmp;
}
return ret;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) {
for(int j=1;j<=m;j++) {scanf("%d",&a[i][j]);tot+=a[i][j];}
}
S=0,T=n*m+1;
for(int i=1;i<=n;i++) {
for(int j=1+(i%2==0);j<=m;j+=2) {
if(j+1<=m) addedge(id(i,j),id(i,j+1),inf);
if(j-1>=1) addedge(id(i,j),id(i,j-1),inf);
}
}
for(int i=1;i<=m;i++) {
for(int j=1+(i%2==0);j<=n;j+=2) {
if(j+1<=n) addedge(id(j,i),id(j+1,i),inf);
if(j-1>=1) addedge(id(j,i),id(j-1,i),inf);
}
}
for(int i=1;i<=n;i++) {
for(int j=1;j<=m;j++) {
if((i&1)==(j&1)) addedge(S,id(i,j),a[i][j]);
else addedge(id(i,j),T,a[i][j]);
}
}
N=n*m+5;
printf("%d\n",tot-MaxF(S,T));
return 0;
}

骑士共存问题

题意

在一个$\text{n} \times \text{n}$ 个方格的国际象棋棋盘上,马(骑士)可以攻击的棋盘方格如图所示。棋盘上某些方格设置了障碍,骑士不得进入。

233

对于给定的 $\text{n} \times \text{n}$个方格的国际象棋棋盘和障碍标志,计算棋盘上最多可以放置多少个骑士,使得它们彼此互不攻击。

题解

和方格取数一样,用黑白染色区分棋盘上的点,其中有攻击关系的连边,二分图匹配即可得出互斥的二元集最大的大小,用所有可用格子的个数减去匹配数即可。

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 maxn=200+5;
int a[maxn][maxn],n,m;
typedef pair<int ,int > pii;
#define fir first
#define sec second
#define MP make_pair
int dx[]={-1,-2,-2,-1,1,2,1,2};
int dy[]={-2,-1,1,2,-2,-1,2,1};
inline int id(int x,int y){return (x-1)*n+y;}
const int inf=0x3f3f3f3f;
struct edge{
int to,cap,rev;
edge(int to=0,int cap=0,int rev=0): to(to),cap(cap),rev(rev) {}
};
vector<edge> g[maxn*maxn+5];
void addedge(int u,int v,int cap)
{
g[u].push_back(edge(v,cap,(int)g[v].size()));
g[v].push_back(edge(u,0,(int)g[u].size()-1));
}
int S,T,ss,tt,N,q[maxn*maxn+5],dis[maxn*maxn+5];
bool bfs(int st,int ed)
{
int head=0,tail=0;
memset(dis,-1,sizeof(dis));
dis[st]=0;
q[head]=st;
while(head<=tail) {
int v=q[head%N];head++;
for(int i=0;i<(int)g[v].size();i++) {
edge &e=g[v][i];
if(e.cap>0 && dis[e.to]==-1) {
dis[e.to]=dis[v]+1;
tail++;q[tail%N]=e.to;
}
}
}
return ~dis[ed];
}
int las[maxn*maxn+5];
int dfs(int v,int ed,int F)
{
if(v==ed) return F;
for(int& i=las[v];i<(int)g[v].size();i++) {
edge &e=g[v][i];
if(e.cap>0 && dis[e.to]==dis[v]+1) {
int d=dfs(e.to,ed,min(F,e.cap));
if(d>0) {
e.cap-=d;
g[e.to][e.rev].cap+=d;
return d;
}
}
}
return 0;
}
int din(int st,int ed)
{
int tmp=0,ret=0;
while(bfs(st,ed)) {
memset(las,0,sizeof(las));
while((tmp=dfs(st,ed,inf))>0) ret+=tmp;
}
return ret;
}
int main()
{
scanf("%d%d",&n,&m);
int u,v;
for(int i=1;i<=m;i++) {
scanf("%d%d",&u,&v);
a[u][v]=1;
}
int nx=0,ny=0;
ss=n*n+2,tt=n*n+3,N=n*n+5;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++) {
if(a[i][j]) continue;
if((i&1)==(j&1)) {
addedge(ss,id(i,j),1);
for(int k=0;k<8;k++) {
nx=i+dx[k],ny=j+dy[k];
if(nx>=1 && nx<=n && ny>=1 && ny<=n) {
if(!a[nx][ny]) addedge(id(i,j),id(nx,ny),1);
}
}
}else addedge(id(i,j),tt,1);
}
printf("%d\n",n*n-m-din(ss,tt));
return 0;
}

星际转移

题意

由于人类对自然资源的消耗,人们意识到大约在 2300 年之后,地球就不能再居住了。于是在月球上建立了新的绿地,以便在需要时移民。令人意想不到的是,2177 年冬由于未知的原因,地球环境发生了连锁崩溃,人类必须在最短的时间内迁往月球。

现有 $ n$ 个太空站位于地球与月球之间,且有 $m$ 艘公共交通太空船在其间来回穿梭。每个太空站可容纳无限多的人,而每艘太空船$i$ 只可容纳 $H_i$ 个人。每艘太空船将周期性地停靠一系列的太空站,例如:$ {1, 3, 4 }$ 表示该太空船将周期性地停靠太空站 134134134 …

每一艘太空船从一个太空站驶往任一太空站耗时均为 1。人们只能在太空船停靠太空站(或月球、地球)时上、下船。

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

题解

因为结点不能滞留人(否则对于一个结点它的流量不守恒),所以把这个结点拆为各个时间里的状态(这样滞留就解决了,可以时间少的向时间大的连边就可以了。S向地球的第0天连大小为$k$的边(提供人流),同时每个点向自己的后一天连容量为$inf$的边(因为可以无限滞留下去),$[i,t]$表示$i$点的第$t$天,对于飞船里的路径$u-v$有$([u,tim-1],[v,tim])$容量为飞船容量的边,那么对于时间为$ans$的人流就是$MaxFlow([S,0],[T,ans])$,枚举时间上限,增加一点时间上限就多建一层图,然后从虚拟源点$S$向第上限天的月球跑,累计流使得流大于等于人数即可。

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
#include <bits/stdc++.h>
using namespace std;
const int maxn=15;
const int maxm=25;
const int inf=0x3f3f3f3f;
struct edge{
int to,cap,rev;
edge(int to=0,int cap=0,int rev=0): to(to),cap(cap),rev(rev) {}
};
vector<edge> g[maxn*50];
void addedge(int u,int v,int cap)
{
g[u].push_back(edge(v,cap,(int)g[v].size()));
g[v].push_back(edge(u,0,(int)g[u].size()-1));
}
int n,m,k;
int S,T,ss,tt,N,q[maxn*50+5],dis[maxn*50+5];
bool bfs(int st,int ed)
{
int head=0,tail=0;
memset(dis,-1,sizeof(dis));
dis[st]=0;
q[head]=st;
while(head<=tail) {
int v=q[head%N];head++;
for(int i=0;i<(int)g[v].size();i++) {
edge &e=g[v][i];
if(e.cap>0 && dis[e.to]==-1) {
dis[e.to]=dis[v]+1;
tail++;q[tail%N]=e.to;
}
}
}
return ~dis[ed];
}
int las[maxn*50+5];
int dfs(int v,int ed,int F)
{
if(v==ed) return F;
for(int& i=las[v];i<(int)g[v].size();i++) {
edge &e=g[v][i];
if(e.cap>0 && dis[e.to]==dis[v]+1) {
int d=dfs(e.to,ed,min(F,e.cap));
if(d>0) {
e.cap-=d;
g[e.to][e.rev].cap+=d;
return d;
}
}
}
return 0;
}
int din(int st,int ed)
{
int tmp=0,ret=0;
while(bfs(st,ed)) {
memset(las,0,sizeof(las));
while((tmp=dfs(st,ed,inf))>0) ret+=tmp;
}
return ret;
}
int H[maxm];
vector<int > sp[maxm];
int ref(int id,int tim){return id+tim*n;}
struct dsu{
int f[maxn*50+5];
void init(){for(int i=1;i<=maxn*50+5;i++) f[i]=i;}
int getf(int x){return x==f[x]?f[x]:f[x]=getf(f[x]);}
void merge(int u,int v) {
int fu=getf(u),fv=getf(v);
if(fu==fv) return;
else f[fv]=fu;
}
} D;
int main()
{
scanf("%d%d%d",&n,&m,&k);n+=2;
int tot=0,x;
N=50*n+5,S=0;
D.init();
for(int i=1;i<=m;i++) {
scanf("%d",&H[i]);
scanf("%d",&tot);
for(int j=0;j<tot;j++) {
scanf("%d",&x);x+=2;
sp[i].push_back(x);
if(j>0) D.merge(sp[i][j-1],sp[i][j]);
}
}
if(D.getf(2)!=D.getf(1)) {printf("0\n");exit(0);}
addedge(S,2,k);
int per=0,ans=0,siz=0,L=0;
while(per<k) {
ans++;
for(int i=1;i<=n;i++) addedge(ref(i,ans-1),ref(i,ans),inf);
for(int i=1;i<=m;i++) {
siz=(int)sp[i].size();
L=(ans-1)%siz;
if(L<siz-1) addedge(ref(sp[i][L],ans-1),ref(sp[i][L+1],ans),H[i]);
else addedge(ref(sp[i].back(),ans-1),ref(sp[i][0],ans),H[i]);
}
per+=din(S,1+n*ans);
}
printf("%d\n",ans);
return 0;
}

火星探险问题

题意

火星探险队的登陆舱将在火星表面着陆,登陆舱内有多部障碍物探测车。

登陆舱着陆后,探测车将离开登陆舱向先期到达的传送器方向移动。

探测车在移动中还必须采集岩石标本。

每一块岩石标本由最先遇到它的探测车完成采集。

每块岩石标本只能被采集一次。

岩石标本被采集后,其他探测车可以从原来岩石标本所在处通过。

探测车不能通过有障碍的地面。

本题限定探测车只能从登陆处沿着向南或向东的方向朝传送器移动,而且多个探测车可以在同一时间占据同一位置。

如果某个探测车在到达传送器以前不能继续前进,则该车所采集的岩石标本将全部损失。

用一个 $\text{P}\times \text{Q}$网格表示登陆舱与传送器之间的位置。登陆舱的位置在 $(X_1,Y_1)$ 处,传送器 的位置在 $(X_P,Y_Q)$处。 给定每个位置的状态,计算探测车的最优移动方案,使到达传送器的探测车的数量最多, 而且探测车采集到的岩石标本的数量最多。

pic

题解

比较简单的建模,因为每个点有贡献之分所以每个点拆为两点$[x,y,1]$和$[x,y,2]$

能走的:$[x,y,1]-[x,y,2] (inf,0)$

有石头的:$[x,y,1]-[x,y,2],(1,1),(inf,0)$

不能走的:不连边

然后就建一个虚拟源点提供大小为$car​$的流,跑出最大费用流即可。

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
137
#include <bits/stdc++.h>
using namespace std;
const int maxn=40+5;
const int dmax=maxn*maxn*2+5;
const int inf=0x3f3f3f3f;
int S,T,N,C,P,Q;
struct edge{
int to,cap,cost,rev;
edge(int to=0,int cap=0,int cost=0,int rev=0): to(to),cap(cap),cost(cost),rev(rev) {}
};
vector<edge > g[dmax];
void addedge(int u,int v,int cap,int cost)
{
cost=-cost;
g[u].push_back(edge(v,cap,cost,(int)g[v].size()));
g[v].push_back(edge(u,0,-cost,(int)g[u].size()-1));
}
typedef pair<int ,int > pii;
#define fir first
#define sec second
#define MP make_pair
bool inque[dmax];
int dis[dmax],q[dmax],prevv[dmax],preve[dmax];
pii spfa(int st,int ed)
{
int head=0,tail=0;
fill(dis,dis+dmax,inf);
memset(inque,0,sizeof(inque));
dis[st]=0;inque[st]=true;
q[head]=st;
while(head<=tail) {
int v=q[head%N];head++;inque[v]=false;
for(int i=0;i<(int)g[v].size();i++) {
edge &e=g[v][i];
if(e.cap>0 && dis[e.to]>dis[v]+e.cost) {
dis[e.to]=dis[v]+e.cost;
if(!inque[e.to]) {
inque[e.to]=true;
tail++;q[tail%N]=e.to;
}
prevv[e.to]=v;
preve[e.to]=i;
}
}
}
if(dis[ed]==inf) return MP(0,-1);
int gap=inf;
for(int i=ed;i!=st;i=prevv[i]) {
gap=min(gap,g[prevv[i]][preve[i]].cap);
}
for(int i=ed;i!=st;i=prevv[i]) {
edge& e=g[prevv[i]][preve[i]];
e.cap-=gap;
g[e.to][e.rev].cap+=gap;
}
return MP(gap,dis[ed]*gap);
}
pii MaxF(int st,int ed)
{
pii ret=MP(0,0),tmp=MP(0,0);
while((tmp=spfa(st,ed)).fir>0) {
ret.fir+=tmp.fir;
ret.sec+=tmp.sec;
}
return ret;
}
int dx[]={1,0};
int dy[]={0,1};
int a[maxn][maxn];
inline int id(int x,int y){return (x-1)*Q+y;}
pii enc(int id){return MP((id-1)/Q+1,id%Q==0?Q:id%Q);}
inline int dir(pii p1,pii p2)
{
int dlx=p2.fir-p1.fir,dly=p2.sec-p1.sec;
for(int i=0;i<2;i++) if(dlx==dx[i] && dly==dy[i]) return i;
return -1;
}
vector<pii > rt;
int offset=0;
void dfs2(int sx,int sy)
{
if(sx==P && sy==Q) {rt.push_back(MP(sx,sy));return;}
else {
rt.push_back(MP(sx,sy));
int tmp=id(sx,sy)+offset;pii tem;
for(int i=0;i<(int)g[tmp].size();i++) {
edge & e=g[tmp][i];
tem=enc(e.to);
if(dir(MP(sx,sy),tem)==-1) continue;
else if(e.cap<inf) {
e.cap+=1;
g[e.to][e.rev].cap-=1;
dfs2(tem.fir,tem.sec);
break;
}
}
}
}
int main()
{
scanf("%d%d%d",&C,&Q,&P);
for(int i=1;i<=P;i++) {
for(int j=1;j<=Q;j++) scanf("%d",&a[i][j]);
}
offset=P*Q;
S=0,T=(offset<<1)+1,N=(offset<<1)+5;
addedge(S,id(1,1),C,0);
for(int i=1;i<=P;i++) {
for(int j=1;j<=Q;j++) {
if(a[i][j]==2) {
addedge(id(i,j),id(i,j)+offset,1,1);
addedge(id(i,j),id(i,j)+offset,inf,0);
}else if(a[i][j]==0) addedge(id(i,j),id(i,j)+offset,inf,0);
else {}
}
}
int nx=0,ny=0;
for(int i=1;i<=P;i++) {
for(int j=1;j<=Q;j++) {
for(int k=0;k<2;k++) {
nx=i+dx[k],ny=j+dy[k];
if(nx>=1 && nx<=P && ny>=1 && ny<=Q && a[nx][ny]!=1) {
addedge(id(i,j)+offset,id(nx,ny),inf,0);
}
}
}
}
pii res=MaxF(S,id(P,Q)+offset),tmp;
for(int i=1;i<=res.fir;i++) {
rt.clear();
dfs2(1,1);
for(int j=1;j<(int)rt.size();j++) {
printf("%d %d\n",i,dir(rt[j-1],rt[j]));
}
}
return 0;
}

最长 k 可重区间集

题意

给定实直线 $L$ 上 $n$ 个开区间组成的集合 $ I$,和一个正整数 $k$,试设计一个算法,从开区间集合 $I$中选取出开区间集合 $S \subseteq I$,使得在实直线$L$的任何一点 $ x$,$ S$ 中包含点 $x$ 的开区间个数不超过$ k$。且 $\sum\limits{z \in S} |z| $ 达到最大。这样的集合 $S$ 称为开区间集合 $I$ 的最长 $k$ 可重区间集。$\sum\limits{z \in S} |z| $ 称为最长 $k$可重区间集的长度。

对于给定的开区间集合$I$和正整数 $k$,计算开区间集合$I$的最长 $ k$可重区间集的长度。

题解

一个错解:

$S-l[i], (1,len)$

$r[i]-T,(1,0)$

前一个数向后一个数,$(k,0)$

样例一过就直接交了,结果是$wa$的,因为反例:(答案应该是较长的线段,但这样因为要优先满足流最大,于是变成了三个小线段)

1

正解:

每个点:$ ,,(1,len)$

$S-l[1],(k,0)$

$r[n]-T,(k,0)$

前一个数向后一个数,$(inf,0)$

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;
const int maxn=600+5;
const int dmax=1200+5;
const int inf=1<<30;
int S,T,N;
struct edge{
int to,cap,cost,rev;
edge(int to=0,int cap=0,int cost=0,int rev=0): to(to),cap(cap),cost(cost),rev(rev) {}
};
vector<edge > g[dmax];
void addedge(int u,int v,int cap,int cost)
{
g[u].push_back(edge(v,cap,cost,(int)g[v].size()));
g[v].push_back(edge(u,0,-cost,(int)g[u].size()-1));
}
typedef pair<int ,int > pii;
#define fir first
#define sec second
#define MP make_pair
bool inque[dmax];
int dis[dmax],q[dmax],prevv[dmax],preve[dmax];
pii spfa(int st,int ed)
{
int head=0,tail=0;
fill(dis,dis+dmax,inf);
memset(inque,0,sizeof(inque));
dis[st]=0;inque[st]=true;
q[head]=st;
while(head<=tail) {
int v=q[head%N];head++;inque[v]=false;
for(int i=0;i<(int)g[v].size();i++) {
edge &e=g[v][i];
if(e.cap>0 && dis[e.to]>dis[v]+e.cost) {
dis[e.to]=dis[v]+e.cost;
if(!inque[e.to]) {
inque[e.to]=true;
tail++;q[tail%N]=e.to;
}
prevv[e.to]=v;
preve[e.to]=i;
}
}
}
if(dis[ed]==inf) return MP(0,-1);
int gap=inf;
for(int i=ed;i!=st;i=prevv[i]) {
gap=min(gap,g[prevv[i]][preve[i]].cap);
}
for(int i=ed;i!=st;i=prevv[i]) {
edge& e=g[prevv[i]][preve[i]];
e.cap-=gap;
g[e.to][e.rev].cap+=gap;
}
return MP(gap,dis[ed]*gap);
}
pii MaxF(int st,int ed)
{
pii ret=MP(0,0),tmp=MP(0,0);
while((tmp=spfa(st,ed)).fir>0) {
ret.fir+=tmp.fir;
ret.sec+=tmp.sec;
}
return ret;
}
typedef pair<int ,int > pii;
#define MP make_pair
#define fir first
#define sec second
int n,k,len[maxn];
pii seg[maxn];
vector<int > pt;
map<int ,int > rfl;
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++) {
scanf("%d%d",&seg[i].fir,&seg[i].sec);
if(seg[i].fir>seg[i].sec) swap(seg[i].fir,seg[i].sec);
len[i]=seg[i].sec-seg[i].fir;
pt.push_back(seg[i].fir+1);
pt.push_back(seg[i].sec);
}
sort(pt.begin(),pt.end());
int sz=unique(pt.begin(),pt.end())-pt.begin();
for(int i=0;i<sz;i++) rfl[pt[i]]=i+1;
S=0,T=sz+1,N=sz+5;
addedge(S,1,k,0);addedge(sz,T,k,0);
for(int i=0;i<sz-1;i++) {
addedge(rfl[pt[i]],rfl[pt[i+1]],inf,0);
}
for(int i=1;i<=n;i++) addedge(rfl[seg[i].fir+1],rfl[seg[i].sec],1,-len[i]);
printf("%d\n",-MaxF(S,T).sec);
return 0;
}

最长k可重线段集

题意

给定平面 $\text{xoy}$上$n$ 个开线段组成的集合 $\text{I}$,和一个正整数 $k$,试设计一个算法。

从开线段集合$\text{I}$中选取出开线段集合$\text{S}\in \text{I}$ ,

使得在x轴上的任何一点 $\text{p}$ , $\text{S}$ 中与直线 $\text{x}=\text{p}$ 相交的开线段个数不超过 $\text{k}$ ,

且 $\sum_{\text{z} \in \text{S}}|z|$达到最大。

这样的集合 $\text{S}$ 称为开线段集合$\text{I}$的最长 $\text{k}$可重线段集的长度。

对于任何开线段$\text{z}$ ,设其断点坐标为(x0,y0)和 (x1,y1),

则开线段 $\text{z}$ 的长度 $|\text{z}|$定义为:$|z| = \lfloor \sqrt{ ( x_1 - x_0 ) ^ 2 + ( y_1 - y_0 )^2 } \rfloor$

对于给定的开线段集合 $\text{I}$ 和正整数 $\text{k}$,计算开线段集合 $\text{I}$ 的最长 $\text{k}$可重线段集的长度。

题解

建图方法同上一个。

然后有个需要注意的地方是,可能出现有垂直于$x$轴的情况,这时需要将横坐标都$\times 2$,$r$+1,而不是以前的将$l$+1。若是只将$l$+1,那么垂直的线段会扭转,这样如果这条线段比较长包含了其他线段的话会形成负环,会$tle$;若横坐标不$\times 2$,那么会有连在一起的情况:比如一条垂直的横坐标是$3$,有另一条的一个端点横坐标为$4$,那么这样会导致这两条线段在$x$轴上看头尾相接,覆盖了$4$,而实际上这两条线段是没有覆盖$4$的,会$wa$。

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;
const int maxn=600+5;
const int dmax=1200+5;
const int inf=1<<30;
int S,T,N;
struct edge{
int to,cap,cost,rev;
edge(int to=0,int cap=0,int cost=0,int rev=0): to(to),cap(cap),cost(cost),rev(rev) {}
};
vector<edge > g[dmax];
void addedge(int u,int v,int cap,int cost)
{
g[u].push_back(edge(v,cap,cost,(int)g[v].size()));
g[v].push_back(edge(u,0,-cost,(int)g[u].size()-1));
}
typedef pair<int ,int > pii;
#define fir first
#define sec second
#define MP make_pair
bool inque[dmax];
int dis[dmax],q[dmax],prevv[dmax],preve[dmax];
pii spfa(int st,int ed)
{
int head=0,tail=0;
fill(dis,dis+dmax,inf);
memset(inque,0,sizeof(inque));
dis[st]=0;inque[st]=true;
q[head]=st;
while(head<=tail) {
int v=q[head%N];head++;inque[v]=false;
for(int i=0;i<(int)g[v].size();i++) {
edge &e=g[v][i];
if(e.cap>0 && dis[e.to]>dis[v]+e.cost) {
dis[e.to]=dis[v]+e.cost;
if(!inque[e.to]) {
inque[e.to]=true;
tail++;q[tail%N]=e.to;
}
prevv[e.to]=v;
preve[e.to]=i;
}
}
}
if(dis[ed]==inf) return MP(0,-1);
int gap=inf;
for(int i=ed;i!=st;i=prevv[i]) {
gap=min(gap,g[prevv[i]][preve[i]].cap);
}
for(int i=ed;i!=st;i=prevv[i]) {
edge& e=g[prevv[i]][preve[i]];
e.cap-=gap;
g[e.to][e.rev].cap+=gap;
}
return MP(gap,dis[ed]*gap);
}
pii MaxF(int st,int ed)
{
pii ret=MP(0,0),tmp=MP(0,0);
while((tmp=spfa(st,ed)).fir>0) {
ret.fir+=tmp.fir;
ret.sec+=tmp.sec;
}
return ret;
}
typedef pair<int ,int > pii;
#define MP make_pair
#define fir first
#define sec second
int n,k,len[maxn];
pii seg[maxn];
vector<int > pt;
map<int ,int > rfl;
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++) {
scanf("%d%d",&seg[i].fir,&seg[i].sec);
if(seg[i].fir>seg[i].sec) swap(seg[i].fir,seg[i].sec);
len[i]=seg[i].sec-seg[i].fir;
pt.push_back(seg[i].fir+1);
pt.push_back(seg[i].sec);
}
sort(pt.begin(),pt.end());
int sz=unique(pt.begin(),pt.end())-pt.begin();
for(int i=0;i<sz;i++) rfl[pt[i]]=i+1;
S=0,T=sz+1,N=sz+5;
addedge(S,1,k,0);addedge(sz,T,k,0);
for(int i=0;i<sz-1;i++) {
addedge(rfl[pt[i]],rfl[pt[i+1]],inf,0);
}
for(int i=1;i<=n;i++) addedge(rfl[seg[i].fir+1],rfl[seg[i].sec],1,-len[i]);
printf("%d\n",-MaxF(S,T).sec);
return 0;
}

数字梯形

比较水

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=25;
const int dmax=25*25+5;
const int inf=0x3f3f3f3f;
int S,T,N;
struct edge{
int to,cap,cost,rev;
edge(int to=0,int cap=0,int cost=0,int rev=0): to(to),cap(cap),cost(cost),rev(rev) {}
};
vector<edge > g[dmax];
void addedge(int u,int v,int cap,int cost)
{
g[u].push_back(edge(v,cap,cost,(int)g[v].size()));
g[v].push_back(edge(u,0,-cost,(int)g[u].size()-1));
}
typedef pair<int ,int > pii;
#define fir first
#define sec second
#define MP make_pair
bool inque[dmax];
int dis[dmax],q[dmax],prevv[dmax],preve[dmax];
pii spfa(int st,int ed)
{
int head=0,tail=0;
memset(dis,inf,sizeof(dis));
memset(inque,0,sizeof(inque));
dis[st]=0;inque[st]=true;
q[head]=st;
while(head<=tail) {
int v=q[head%N];head++;inque[v]=false;
for(int i=0;i<(int)g[v].size();i++) {
edge &e=g[v][i];
if(e.cap>0 && dis[e.to]>dis[v]+e.cost) {
dis[e.to]=dis[v]+e.cost;
if(!inque[e.to]) {
inque[e.to]=true;
tail++;q[tail%N]=e.to;
}
prevv[e.to]=v;
preve[e.to]=i;
}
}
}
if(dis[ed]==inf) return MP(0,-1);
int gap=inf;
for(int i=ed;i!=st;i=prevv[i]) {
gap=min(gap,g[prevv[i]][preve[i]].cap);
}
for(int i=ed;i!=st;i=prevv[i]) {
edge& e=g[prevv[i]][preve[i]];
e.cap-=gap;
g[e.to][e.rev].cap+=gap;
}
return MP(gap,dis[ed]*gap);
}
pii MaxF(int st,int ed)
{
pii ret=MP(0,0),tmp=MP(0,0);
while((tmp=spfa(st,ed)).fir>0) {
ret.fir+=tmp.fir;
ret.sec+=tmp.sec;
}
return ret;
}
int n,m,a[maxn][maxn];
inline int id(int x,int y){return x*(x-1)/2+(m-1)*(x-1)+y;}
int main()
{
scanf("%d%d",&m,&n);
for(int i=1;i<=n;i++)
for(int j=1;j<=m+i-1;j++) scanf("%d",&a[i][j]);
int offset=id(n,m+n-1);
S=0,T=offset*2+1,N=T+5;
for(int i=1;i<=m;i++) addedge(S,id(1,i),1,0);
for(int i=1;i<=n;i++)
for(int j=1;j<=m+i-1;j++) addedge(id(i,j),id(i,j)+offset,1,-a[i][j]);
for(int i=1;i<=n-1;i++)
for(int j=1;j<=m+i-1;j++) addedge(id(i,j)+offset,id(i+1,j),1,0),addedge(id(i,j)+offset,id(i+1,j+1),1,0);
for(int i=1;i<=m+n-1;i++) addedge(id(n,i)+offset,T,1,0);
printf("%d\n",-MaxF(S,T).sec);
for(int i=S;i<=T;i++) g[i].clear();
for(int i=1;i<=m;i++) addedge(S,id(1,i),1,0);
for(int i=1;i<=n;i++)
for(int j=1;j<=m+i-1;j++) addedge(id(i,j),id(i,j)+offset,inf,-a[i][j]);
for(int i=1;i<=n-1;i++)
for(int j=1;j<=m+i-1;j++) addedge(id(i,j)+offset,id(i+1,j),1,0),addedge(id(i,j)+offset,id(i+1,j+1),1,0);
for(int i=1;i<=m+n-1;i++) addedge(id(n,i)+offset,T,inf,0);
printf("%d\n",-MaxF(S,T).sec);
for(int i=S;i<=T;i++) g[i].clear();
for(int i=1;i<=m;i++) addedge(S,id(1,i),1,0);
for(int i=1;i<=n;i++)
for(int j=1;j<=m+i-1;j++) addedge(id(i,j),id(i,j)+offset,inf,-a[i][j]);
for(int i=1;i<=n-1;i++)
for(int j=1;j<=m+i-1;j++) addedge(id(i,j)+offset,id(i+1,j),inf,0),addedge(id(i,j)+offset,id(i+1,j+1),inf,0);
for(int i=1;i<=m+n-1;i++) addedge(id(n,i)+offset,T,inf,0);
printf("%d\n",-MaxF(S,T).sec);
return 0;
}

汽车加油行驶

最短路

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
#include <bits/stdc++.h>
using namespace std;
const int maxn=100+5;
const int maxk=10+5;
const int inf=0x3f3f3f3f;
int a[maxn][maxn];
int n,k,A,B,C,N;
inline int id(int x,int y){return (x-1)*n+y;}
struct info{
int x,y,lev;
info(int x=0,int y=0,int lev=0): x(x),y(y),lev(lev) {}
};
info q[maxn*maxn*(1+maxk)+5];
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
int dis[maxn][maxn][maxk];
bool inque[maxn][maxn][maxk];
void spfa()
{
memset(dis,inf,sizeof(dis));
memset(inque,0,sizeof(inque));
int head=0,tail=0;
q[head]=info(1,1,k);inque[1][1][k]=true;
dis[1][1][k]=0;
int nx,ny,sx,sy,co=0;
while(head<=tail) {
info nw=q[head%N];head++;sx=nw.x,sy=nw.y;
inque[sx][sy][nw.lev]=false;
if(!nw.lev) continue;
for(int i=0;i<4;i++) {
nx=sx+dx[i],ny=sy+dy[i];
if(nx<=0 || nx>n || ny<=0 || ny>n) continue;
co=(nx<sx || ny<sy)*B;
if(a[nx][ny]==1) {
if(dis[nx][ny][k]>dis[sx][sy][nw.lev]+co+A) {
dis[nx][ny][k]=dis[sx][sy][nw.lev]+co+A;
if(!inque[nx][ny][k]) tail++,q[tail%N]=info(nx,ny,k),inque[nx][ny][k]=true;
}
}else {
if(dis[nx][ny][nw.lev-1]>dis[sx][sy][nw.lev]+co) {
dis[nx][ny][nw.lev-1]=dis[sx][sy][nw.lev]+co;
if(!inque[nx][ny][nw.lev-1]) tail++,q[tail%N]=info(nx,ny,nw.lev-1),inque[nx][ny][nw.lev-1]=true;
}
if(dis[nx][ny][k]>dis[sx][sy][nw.lev]+co+C+A) {
dis[nx][ny][k]=dis[sx][sy][nw.lev]+co+C+A;
if(!inque[nx][ny][k]) tail++,q[tail%N]=info(nx,ny,k),inque[nx][ny][k]=true;
}
}
}
}
}
int main()
{
scanf("%d%d%d%d%d",&n,&k,&A,&B,&C);
N=n*n*(k+1)+5;
for(int i=1;i<=n;i++) {
for(int j=1;j<=n;j++) scanf("%d",&a[i][j]);
}
spfa();
int res=INT_MAX;
for(int i=0;i<=k;i++) res=min(res,dis[n][n][i]);
printf("%d\n",res);
return 0;
}

孤岛营救

分层图的最短路

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
#include <bits/stdc++.h>
using namespace std;
const int maxn=15;
const int maxp=11;
int a[1<<maxp][maxn][maxn][4];
vector<int > b[maxn][maxn];
int dx[]={0,1,-1,0};
int dy[]={1,0,0,-1};
int n,m,k,p,s,N;
inline int pan(int sx,int sy,int tx,int ty)
{
int dlx=tx-sx,dly=ty-sy;
for(int i=0;i<4;i++) {
if(dlx==dx[i] && dly==dy[i]) return i;
}
assert(0);
}
bool vis[1<<maxp][maxn][maxn];
int ans=INT_MAX;
inline int perf(int tar,int x,int y)
{
for(int i=0;i<(int)b[x][y].size();i++) {
tar|=(1<<b[x][y][i]);
}
return tar;
}
struct info {
int x,y,sts,stp;
info(int x=0,int y=0,int sts=0,int stp=0): x(x),y(y),sts(sts),stp(stp) {}
};
info q[maxn*maxn*(1<<maxp)+10];
void bfs()
{
int sx=0,sy=0,nx=0,ny=0,sts=0,stp=0;
int head=0,tail=0;
q[head]=info(1,1,0,0);
while(head<=tail) {
info v=q[head%N];head++;
sx=v.x,sy=v.y,sts=v.sts,stp=v.stp;
vis[sts][sx][sy]=1;
if(sx==n && sy==m) {ans=min(ans,v.stp);}
for(int i=0;i<4;i++) {
nx=sx+dx[i],ny=sy+dy[i];
if(nx>=1 && nx<=n && ny>=1 && ny<=m && !vis[sts][nx][ny]) {
if(a[sts][sx][sy][i]==-1) continue;
if(a[sts][sx][sy][i]==0) {
tail++;q[tail%N]=info(nx,ny,perf(sts,nx,ny),stp+1);
}else {
if((sts>>(a[sts][sx][sy][i]-1))&1) {
tail++;q[tail%N]=info(nx,ny,perf(sts,nx,ny),stp+1);
}else continue;
}
}
}
}
}
int main()
{
scanf("%d%d%d",&n,&m,&p);
scanf("%d",&k);
N=n*m*(1<<p)+10;
int x1,x2,y1,y2,g;p=0;
for(int i=1;i<=k;i++) {
scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&g);
if(!g) g=-1;
a[0][x1][y1][pan(x1,y1,x2,y2)]=g;
a[0][x2][y2][pan(x2,y2,x1,y1)]=g;
p=max(p,g);
}
scanf("%d",&s);
for(int i=1;i<=s;i++) {
scanf("%d%d%d",&x1,&y1,&g);
b[x1][y1].push_back(g-1);
}
for(int S=1;S<(1<<p);S++) {
memcpy(a[S],a[0],sizeof(a[0]));
for(int j=1;j<=n;j++) {
for(int k=1;k<=m;k++) {
for(int l=0;l<4;l++) {
if(a[S][j][k][l]>0 && ((S>>(a[S][j][k][l]-1))&1))
a[S][j][k][l]=0;
}
}
}
}
bfs();
printf("%d\n",ans==INT_MAX?-1:ans);
return 0;
}

最小路径覆盖

每匹配一个点相当于合并了两条路径(刚开始每个点视为单独的路径),所以总数减掉匹配值即为答案。

依旧是早期写的清奇码风

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 <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <queue>
using namespace std;
const int maxn=5000;
vector<int > g[maxn];
bool used[maxn];
int match[maxn];
int ingree[maxn];
int togree[maxn];
void addedge(int from,int to)
{
g[from].push_back(to);
g[to].push_back(from);
}
bool dfs(int v)
{
for(unsigned i=0;i<g[v].size();i++)
{
int u=g[v][i];
if(!used[u])
{
used[u]=true;
if(match[u]==0 || dfs(match[u]))
{
match[u]=v;
match[v]=u;
return true;
}
}
}
return false;
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
memset(ingree,0,sizeof(ingree));
memset(togree,0,sizeof(togree));
for(int i=0;i<m;i++)
{
int from,to;
scanf("%d%d",&from,&to);
addedge(from,to+n);
ingree[to+n]++;
togree[from]++;
}
int ans=0;
for(int i=1;i<=2*n;i++)
{
if(match[i]==0)
{
memset(used,0,sizeof(used));
if(dfs(i))
{
ans++;
}
}
}
ans=n-ans;
bool book[maxn];
memset(book,false,sizeof(book));
for(int i=1;i<=n;i++)
{
if(!book[i])
{
int v=i;
printf("%d ",v);
book[v]=true;
while(match[v]>0)
{
printf("%d ",match[v]-n);
v=match[v]-n;
book[v]=true;
}
printf("\n");
}
}
printf("%d\n",ans);
return 0;
}

试题库

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
#include <bits/stdc++.h>
using namespace std;
const int maxk=20+5;
const int maxn=1000+5;
const int maxsiz=maxn+maxk;
const int inf=0x3f3f3f3f;
namespace io{
const int L=(1<<19)+1;
int f;
char ibuf[L],*iS,*iT,c;
inline char Gc(){
if(iS==iT){
iT=(iS=ibuf)+fread(ibuf,1,L,stdin);
return iS==iT?EOF:*iS++;
}
return*iS++;
}
template<class I>void Gi(I&x){
for(f=1,c=Gc();c<'0'||c>'9';c=Gc())if(c=='-')f=-1;
for(x=0;c<='9'&&c>='0';c=Gc())x=x*10+(c&15);x*=f;
}
};
using io::Gi;
inline int readInt()
{
char c;int tmp=0,x=1;c=getchar();
while(c>'9' || c<'0') {if(c=='-') x=-1;c=getchar();}
while(c>='0' && c<='9') {tmp=tmp*10+c-'0';c=getchar();}
return tmp*x;
}
int n,k,m,S,T,siz[maxk];
vector<int > typ[maxn];
struct edge{
int to,cap,rev;
edge(int to=0,int cap=0,int rev=0): to(to),cap(cap),rev(rev) {}
};
vector<edge> g[maxsiz];
void addedge(int u,int v,int C)
{
g[u].push_back(edge(v,C,(int)g[v].size()));
g[v].push_back(edge(u,0,(int)g[u].size()-1));
}
int dis[maxsiz],cur[maxsiz],q[maxsiz+5],N;
bool bfs(int st,int ed)
{
memset(dis,-1,sizeof(dis));
dis[st]=0;
int head=0,tail=0;
q[head]=st;
while(head<=tail) {
int u=q[head%N];head++;
for(int i=0;i<(int)g[u].size();i++) {
edge& e=g[u][i];
if(e.cap>0 && dis[e.to]==-1) {
dis[e.to]=dis[u]+1;
tail++;q[tail%N]=e.to;
}
}
}
return dis[ed]!=-1;
}
int dfs(int v,int ed,int mf)
{
if(v==ed) return mf;
for(int &i=cur[v];i<(int)g[v].size();i++) {
int u=g[v][i].to;
edge& e=g[v][i];
if(e.cap>0 && dis[u]==dis[v]+1) {
int F=dfs(u,ed,min(mf,e.cap));
if(F>0) {
g[v][i].cap-=F;
g[u][g[v][i].rev].cap+=F;
return F;
}
}
}
return 0;
}
int maxF(int st,int ed)
{
int ret=0,tmp=0;
while(bfs(st,ed)) {
memset(cur,0,sizeof(cur));
while((tmp=dfs(st,ed,inf))>0) ret+=tmp;
}
return ret;
}
int main()
{
Gi(k),Gi(n);
S=0,T=k+n+1,N=T+2;
for(int i=1;i<=k;i++) {
Gi(siz[i]),m+=siz[i];
addedge(S,i,siz[i]);
}
int p,x;
for(int i=1;i<=n;i++) {
Gi(p);
for(int j=1;j<=p;j++) Gi(x),typ[i].push_back(x);
}
for(int i=1;i<=n;i++) {
for(int j=0;j<(int)typ[i].size();j++) {
int t=typ[i][j];
addedge(t,k+i,1);
}
}
for(int i=1;i<=n;i++) addedge(k+i,T,1);
int res=maxF(S,T);
if(res<m) printf("No Solution!\n");
else {
for(int i=1;i<=k;i++) {
printf("%d:",i);
for(int j=0;j<(int)g[i].size();j++) {
if(g[i][j].cap==0 && g[i][j].to>k) printf(" %d",g[i][j].to-k);
}printf("\n");
}
}
return 0;
}

圆桌

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
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <queue>
#include <map>
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=275;
const int maxm=155;
int co[maxm];
int des[maxn];
int m,n;
struct edge
{
int to,cap,rev;
};
vector<edge> g[maxn+maxm];
void addedge(int from,int to,int cap)
{
g[from].push_back((edge){to,cap,g[to].size()});
g[to].push_back((edge){from,0,g[from].size()-1});
}
int dis[maxn+maxm+2];
bool bfs(int st,int ed)
{
memset(dis,inf,sizeof(dis));
int head=0;
int tail=0;
int q[maxn+maxm+2];
memset(q,0,sizeof(q));
q[head]=st;
dis[st]=0;
while(head<=tail)
{
int top=q[head];
head++;
for(unsigned i=0;i<g[top].size();i++)
{
edge & e=g[top][i];
if(dis[e.to]==inf && e.cap>0)
{
dis[e.to]=dis[top]+1;
tail++;
q[tail]=e.to;
}
}
}
return dis[ed]!=inf;
}
int dfs(int v,int ed,int leftflow)
{
if(v==ed || leftflow==0)
{
return leftflow;
}
for(unsigned i=0;i<g[v].size();i++)
{
edge &e=g[v][i];
if(e.cap>0 && dis[e.to]==dis[v]+1)
{
int f;
f=dfs(e.to,ed,min(e.cap,leftflow));
if(f>0)
{
e.cap-=f;
g[e.to][e.rev].cap+=f;
return f;
}
}
}
return 0;
}
int dinic(int st,int ed)
{
int ans=0;
while(bfs(st,ed))
{
int f;
while((f=dfs(st,ed,inf))>0)
{
ans+=f;
}
}
return ans;
}
int main()
{
bool flag=true;
int per=0;
int tabp=0;
scanf("%d%d",&m,&n);
for(int i=1;i<=m;i++)
{
scanf("%d",&co[i]);
per+=co[i];
}
for(int i=1;i<=n;i++)
{
scanf("%d",&des[i]);
tabp+=des[i];
}
if(tabp<per)
{
flag=false;
}
else
{
int s=0;
int t=m+n+1;
for(int i=1;i<=m;i++)
{
addedge(s,i,co[i]);
}
for(int i=1;i<=n;i++)
{
addedge(i+m,t,des[i]);
}
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
addedge(i,j+m,1);
}
}
int ans=dinic(s,t);
if(ans<per)
{
flag=false;
}
if(flag==false)
{
printf("0\n");
}
else
{
printf("1\n");
vector<int > ans[maxm+1];
for(int i=1;i<=m;i++)
{
for(unsigned j=0;j<g[i].size();j++)
{
edge & e=g[i][j];
if(e.cap==0)
{
ans[i].push_back(e.to);
}
}
}
for(int i=1;i<=m;i++)
{
for(unsigned j=0;j<ans[i].size();j++)
{
printf("%d ",ans[i][j]-m);
}
printf("\n");
}
}
}
return 0;
}

软件补丁

以状态为点的最短路…

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=21;
const int maxm=120;
int n,m;
struct point
{
int f1,f2;
int b1,b2;
int cost;
}p[maxm];
int dis[1<<21];
bool inque[1<<21];
bool judge(int u,int i)
{
bool flag=true;
if((u|(p[i].b1))!=u)
{
flag=false;
}
if(p[i].b2&u)
{
flag=false;
}
return flag;
}
void spfa()
{
queue<int > q;
q.push((1<<n)-1);
inque[(1<<(n))-1]=true;
memset(dis,inf,sizeof(dis));
dis[(1<<(n))-1]=0;
while(!q.empty())
{
int now=q.front();
q.pop();
inque[now]=false;
for(int i=0;i<m;i++)
{
if(judge(now,i))
{
int u=(now&(~p[i].f2))|(p[i].f1);
if(dis[u]>dis[now]+p[i].cost)
{
dis[u]=dis[now]+p[i].cost;
if(!inque[u])
{
q.push(u);
inque[u]=true;
}
}
}
}
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++)
{
int cost;
char buff1[maxn],buff2[maxn];
memset(buff1,0,sizeof(buff1));
memset(buff2,0,sizeof(buff2));
scanf("%d%s%s",&cost,buff1,buff2);
p[i].cost=cost;
int len=strlen(buff1);
len--;
for(int j=0;j<(int)strlen(buff1);j++)
{
if(buff1[j]=='+')
{
p[i].b1+=1<<(len-j);
}
if(buff1[j]=='-')
{
p[i].b2+=1<<(len-j);
}
if(buff2[j]=='+')
{
p[i].f1+=1<<(len-j);
}
if(buff2[j]=='-')
{
p[i].f2+=1<<(len-j);
}
}
}
spfa();
if(dis[0]!=inf)
{
printf("%d\n",dis[0]);
}
else
{
printf("0\n");
}
return 0;
}

运输问题

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
137
138
139
140
141
142
143
144
145
146
147
148
149
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int maxn=200;
const int maxm=200;
const int inf=0x3f3f3f3f;
int n,m;
struct edge
{
int to,cap,cost,rev;
};
vector<edge> g[maxn];
int a[maxn];
int b[maxn];
int p[maxm][maxn];
int dis[maxn+maxm+2];
int q[maxn+maxm+2];
bool inque[maxn+maxm+2];
int prevv[maxn+maxm+2];
int preve[maxn+maxm+2];
int aj[maxn+maxm+2];
int ans=0;
void addedge(int from,int to,int cap,int cost)
{
g[from].push_back((edge){to,cap,cost,g[to].size()});
g[to].push_back((edge){from,0,-cost,g[from].size()-1});
}
bool spfa(int st,int ed)
{
memset(prevv,0,sizeof(prevv));
memset(preve,0,sizeof(preve));
memset(inque,false,sizeof(inque));
memset(dis,inf,sizeof(dis));
dis[st]=0;
memset(q,0,sizeof(q));
int head=0;
int tail=0;
q[head]=st;
aj[st]=inf;
inque[st]=true;
while(head<=tail)
{
int top=q[head];
inque[top]=false;
head++;
for(unsigned i=0;i<g[top].size();i++)
{
edge &e=g[top][i];
if(dis[e.to]>dis[top]+e.cost && e.cap>0)
{
aj[e.to]=min(e.cap,aj[top]);
dis[e.to]=dis[top]+e.cost;
prevv[e.to]=top;
preve[e.to]=i;
if(!inque[e.to])
{
tail++;
q[tail]=e.to;
inque[e.to]=true;
}
}
}
}
if(dis[ed]==inf)
{
return false;
}
ans+=aj[ed]*dis[ed];
for(int i=ed;i!=st;i=prevv[i])
{
edge &e=g[prevv[i]][preve[i]];
e.cap-=aj[ed];
g[e.to][e.rev].cap+=aj[ed];
}
return true;
}
int main()
{
scanf("%d%d",&m,&n);
for(int i=1;i<=m;i++)
{
scanf("%d",&a[i]);
}
for(int i=1;i<=n;i++)
{
scanf("%d",&b[i]);
}
int s=0;
int t=n+m+1;
for(int i=1;i<=m;i++)
{
addedge(s,i,a[i],0);
}
for(int i=1;i<=n;i++)
{
addedge(i+m,t,b[i],0);
}
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
int cost;
scanf("%d",&cost);
p[i][j]=cost;
}
}
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
addedge(i,j+m,inf,p[i][j]);
}
}
while(spfa(s,t));
printf("%d\n",ans);
ans=0;
for(int i=0;i<maxn;i++)
{
g[i].clear();
}
for(int i=1;i<=m;i++)
{
addedge(s,i,a[i],0);
}
for(int i=1;i<=n;i++)
{
addedge(i+m,t,b[i],0);
}
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
addedge(i,j+m,inf,-p[i][j]);
}
}
while(spfa(s,t));
printf("%d\n",-ans);
return 0;
}

分配问题

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
137
138
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
#define mem(x) memset(x,0,sizeof(x))
const int inf=0x3f3f3f3f;
const int maxn=305;
int love[maxn][maxn];
int ex_girl[maxn];
int ex_boy[maxn];
int slack[maxn];
int match[maxn];
int res=0;
bool vis_girl[maxn];
bool vis_boy[maxn];
int n;
void ini()
{
mem(love),mem(ex_girl),mem(ex_boy);
mem(slack);
memset(match,-1,sizeof(match));
mem(vis_girl);
mem(vis_boy);
res=0;
}
bool dfs(int v)
{
vis_girl[v]=true;
for(int u=0;u<n;u++)
{
if(vis_boy[u])
{
continue;
}
int gap=ex_girl[v]+ex_boy[u]-love[v][u];
if(gap==0)
{
vis_boy[u]=true;
if(match[u]==-1 || dfs(match[u]))
{
match[u]=v;
return true;
}
}
else
{
slack[u]=min(slack[u],gap);
}
}
return false;
}
int km()
{
memset(match,-1,sizeof(match));
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
ex_girl[i]=max(ex_girl[i],love[i][j]);
}
}
for(int i=0;i<n;i++)
{
memset(slack,inf,sizeof(slack));
while(1)
{
mem(vis_girl);
mem(vis_boy);
if(dfs(i))
{
break;
}
int d=inf;
for(int i=0;i<n;i++)
{
d=min(d,slack[i]);
}
for(int i=0;i<n;i++)
{
if(vis_girl[i])
{
ex_girl[i]-=d;
}
if(vis_boy[i])
{
ex_boy[i]+=d;
}
}
}
}
for(int i=0;i<n;i++)
{
res+=love[match[i]][i];
}
return res;
}
int main()
{
pair<int ,int > ans;
scanf("%d",&n);
ini();
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
scanf("%d",&love[i][j]);
}
}
res=km();
ans.first=res;
mem(ex_girl),mem(ex_boy);
mem(slack);
memset(match,-1,sizeof(match));
mem(vis_girl);
mem(vis_boy);
res=0;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
love[i][j]*=-1;
}
}
res=km();
res=-res;
ans.second=res;
printf("%d\n%d\n",ans.second,ans.first);
return 0;
}

负载平衡

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <queue>
#include <cmath>
using namespace std;
const int maxn=120;
int n;
int a[maxn];
int c[maxn];
int main()
{
scanf("%d",&n);
int tot=0;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
tot+=a[i];
}
c[0]=0;
int m=tot/n;
for(int i=1;i<n;i++)
{
c[i]=c[i-1]+a[i]-m;
}
sort(c,c+n);
int x1=c[n/2];
int ans=0;
for(int i=0;i<n;i++)
{
ans+=abs(c[i]-x1);
}
printf("%d\n",ans);
return 0;
}

航空路线

题意

给定一张航空图,图中顶点代表城市,边代表两个城市间的直通航线。现要求找出一条满足下述限制条件的且途经城市最多的旅行路线。

  1. 从最西端城市出发,单向从西向东途经若干城市到达最东端城市,然后再单向从东向西飞回起点(可途经若干城市)。
  2. 除起点城市外,任何城市只能访问一次。

对于给定的航空图,试设计一个算法找出一条满足要求的最佳航空旅行路线。

题解

每个点只能经过一次(除了起点)所以每个点要拆为两个点限制容量;

然后一条去,一条回的路线其实可以看作是大小为$2$的从起点到终点的流,经过一个城市会对整个路线长度有$1$的贡献,所以每个点拆为的两个点有$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
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
#include <bits/stdc++.h>
using namespace std;
const int maxn=100+5;
const int dmax=200+10;
const int inf=0x3f3f3f3f;
struct edge{
int to,cap,cost,rev;
edge(int to=0,int cap=0,int cost=0,int rev=0): to(to),cap(cap),cost(cost),rev(rev) {}
};
vector<edge > g[dmax];
void addedge(int u,int v,int cap,int cost)
{
cost=-cost;
g[u].push_back(edge(v,cap,cost,(int)g[v].size()));
g[v].push_back(edge(u,0,-cost,(int)g[u].size()-1));
}
typedef pair<int ,int > pii;
#define fir first
#define sec second
#define MP make_pair
bool inque[dmax];
int dis[dmax],q[dmax],prevv[dmax],preve[dmax],n,m,S,T,N;
pii spfa(int st,int ed)
{
int head=0,tail=0;
fill(dis,dis+dmax,inf);
memset(inque,0,sizeof(inque));
dis[st]=0;inque[st]=true;
q[head]=st;
while(head<=tail) {
int v=q[head%N];head++;inque[v]=false;
for(int i=0;i<(int)g[v].size();i++) {
edge &e=g[v][i];
if(e.cap>0 && dis[e.to]>dis[v]+e.cost) {
dis[e.to]=dis[v]+e.cost;
if(!inque[e.to]) {
inque[e.to]=true;
tail++;q[tail%N]=e.to;
}
prevv[e.to]=v;
preve[e.to]=i;
}
}
}
if(dis[ed]==inf) return MP(0,-1);
int gap=inf;
for(int i=ed;i!=st;i=prevv[i]) {
gap=min(gap,g[prevv[i]][preve[i]].cap);
}
for(int i=ed;i!=st;i=prevv[i]) {
edge& e=g[prevv[i]][preve[i]];
e.cap-=gap;
g[e.to][e.rev].cap+=gap;
}
return MP(gap,dis[ed]*gap);
}
pii MaxF(int st,int ed)
{
pii ret=MP(0,0),tmp=MP(0,0);
while((tmp=spfa(st,ed)).fir>0) {
ret.fir+=tmp.fir;
ret.sec+=tmp.sec;
}
return ret;
}
string nam[maxn];
map<string ,int > rfl;
vector<int > rt[2];
bool vis[dmax];
bool can(int u,int v)
{
if(u>v) return u-n<v;
else return u<=v-n;
}
void dfs(int v,int id)
{
if(v!=n && v!=2*n) vis[v]=true;
if(v<=2*n && v>n) rt[id].push_back(v);
if(v==2*n) return;
for(int i=0;i<(int)g[v].size();i++) {
edge & e=g[v][i];
if(e.cap==0 && !vis[e.to] && can(v,e.to)) {dfs(e.to,id);break;}
}
}
int main()
{
scanf("%d%d",&n,&m);
N=n*2+5;
for(int i=1;i<=n;i++) {
cin>>nam[i];
rfl[nam[i]]=i;
if(i==1 || i==n) addedge(i,i+n,2,1);
else addedge(i,i+n,1,1);
}
string u,v;
for(int i=1;i<=m;i++) {
cin>>u>>v;
if(rfl[u]>rfl[v]) swap(u,v);
addedge(rfl[u]+n,rfl[v],1,0);
}
pii ans=MaxF(1,n*2);
if(ans.fir==2) {
printf("%d\n",-ans.sec-2);
dfs(1+n,0);
dfs(1+n,1);
for(int i=0;i<(int)rt[0].size();i++) cout<<nam[rt[0][i]-n]<<"\n";
for(int i=(int)rt[1].size()-1;i>=0;i--) if(rt[1][i]!=n*2) cout<<nam[rt[1][i]-n]<<"\n";
}else if(ans.fir==1 && ans.sec==-2) { //too few points
printf("2\n");
cout<<nam[1]<<"\n"<<nam[n]<<"\n"<<nam[1]<<"\n";
}else printf("No Solution!\n");
return 0;
}

深海机器人

多源汇的裸题,多个源点和虚拟源点连边,多个汇点和虚拟汇点连边。

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=25;
const int dmax=maxn*maxn+5;
const int inf=0x3f3f3f3f;
int A,B,n,m,N,S,T;
struct edge{
int to,cap,cost,rev;
edge(int to=0,int cap=0,int cost=0,int rev=0): to(to),cap(cap),cost(cost),rev(rev) {}
};
vector<edge > g[dmax];
void addedge(int u,int v,int cap,int cost)
{
cost=-cost;
g[u].push_back(edge(v,cap,cost,(int)g[v].size()));
g[v].push_back(edge(u,0,-cost,(int)g[u].size()-1));
}
typedef pair<int ,int > pii;
#define fir first
#define sec second
#define MP make_pair
bool inque[dmax];
int dis[dmax],q[dmax],prevv[dmax],preve[dmax];
pii spfa(int st,int ed)
{
int head=0,tail=0;
fill(dis,dis+dmax,inf);
memset(inque,0,sizeof(inque));
dis[st]=0;inque[st]=true;
q[head]=st;
while(head<=tail) {
int v=q[head%N];head++;inque[v]=false;
for(int i=0;i<(int)g[v].size();i++) {
edge &e=g[v][i];
if(e.cap>0 && dis[e.to]>dis[v]+e.cost) {
dis[e.to]=dis[v]+e.cost;
if(!inque[e.to]) {
inque[e.to]=true;
tail++;q[tail%N]=e.to;
}
prevv[e.to]=v;
preve[e.to]=i;
}
}
}
if(dis[ed]==inf) return MP(0,-1);
int gap=inf;
for(int i=ed;i!=st;i=prevv[i]) {
gap=min(gap,g[prevv[i]][preve[i]].cap);
}
for(int i=ed;i!=st;i=prevv[i]) {
edge& e=g[prevv[i]][preve[i]];
e.cap-=gap;
g[e.to][e.rev].cap+=gap;
}
return MP(gap,dis[ed]*gap);
}
pii MaxF(int st,int ed)
{
pii ret=MP(0,0),tmp=MP(0,0);
while((tmp=spfa(st,ed)).fir>0) {
ret.fir+=tmp.fir;
ret.sec+=tmp.sec;
}
return ret;
}
inline int id(int x,int y){return (x-1)*m+y;}
int main()
{
scanf("%d%d",&A,&B);
scanf("%d%d",&n,&m);n++,m++;
int x;
for(int i=1;i<=n;i++) {
for(int j=1;j<=m-1;j++) {
scanf("%d",&x);
addedge(id(i,j),id(i,j+1),1,x);
addedge(id(i,j),id(i,j+1),inf,0);
}
}
for(int i=1;i<=m;i++) {
for(int j=1;j<=n-1;j++) {
scanf("%d",&x);
addedge(id(j,i),id(j+1,i),1,x);
addedge(id(j,i),id(j+1,i),inf,0);
}
}
S=0,T=n*m+1,N=n*m+5;
int F,y;
for(int i=1;i<=A;i++) {
scanf("%d%d%d",&F,&x,&y);
x++,y++;
addedge(S,id(x,y),F,0);
}
for(int i=1;i<=B;i++) {
scanf("%d%d%d",&F,&x,&y);
x++,y++;
addedge(id(x,y),T,F,0);
}
printf("%d\n",-MaxF(S,T).sec);
return 0;
}

无源汇有上下界可行流

每条边建容量为R-L的边,同时统计每个点在每条边下界满足情况下的流入量-流出量的差
如果差大于0,那么证明流入量大于流出量,需要有结点提供这些流量,所以从$S$向这个点连差的大小为容量的边。
如果差小于0,那么多余的流量需要流走,于是建立这个点到虚拟汇点差的大小为容量的边。

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
#include <bits/stdc++.h>
using namespace std;
const int maxn=200+5;
const int maxm=(int)4e4+5;
const int inf=0x3f3f3f3f;
struct edge{
int id,to,cap,rev;
edge(int id=0,int to=0,int cap=0,int rev=0): id(id),to(to),cap(cap),rev(rev) {}
};
vector<edge> g[maxn];
void addedge(int id,int u,int v,int cap)
{
g[u].push_back(edge(id,v,cap,(int)g[v].size()));
g[v].push_back(edge(0,u,0,(int)g[u].size()-1));
}
int n,m,up[maxm],A[maxn],ans[maxm];
int S,T,N,q[maxn+5],dis[maxn+5];
bool bfs(int st,int ed)
{
int head=0,tail=0;
memset(dis,-1,sizeof(dis));
dis[st]=0;
q[head]=st;
while(head<=tail) {
int v=q[head%N];head++;
for(int i=0;i<(int)g[v].size();i++) {
edge &e=g[v][i];
if(e.cap>0 && dis[e.to]==-1) {
dis[e.to]=dis[v]+1;
tail++;q[tail%N]=e.to;
}
}
}
return ~dis[ed];
}
int las[maxn+5];
int dfs(int v,int ed,int F)
{
if(v==ed) return F;
for(int& i=las[v];i<(int)g[v].size();i++) {
edge &e=g[v][i];
if(e.cap>0 && dis[e.to]==dis[v]+1) {
int d=dfs(e.to,ed,min(F,e.cap));
if(d>0) {
e.cap-=d;
g[e.to][e.rev].cap+=d;
return d;
}
}
}
return 0;
}
int din(int st,int ed)
{
int tmp=0,ret=0;
while(bfs(st,ed)) {
memset(las,0,sizeof(las));
if((tmp=dfs(st,ed,inf))>0) ret+=tmp;
}
return ret;
}
int main()
{
scanf("%d%d",&n,&m);
int u,v,L,R,LOW=0;
for(int i=1;i<=m;i++) {
scanf("%d%d%d%d",&u,&v,&L,&R);
up[i]=R;
addedge(i,u,v,R-L);
A[u]-=L,A[v]+=L;
}
S=0,T=n+1,N=n+5;
for(int i=1;i<=n;i++) {
if(A[i]>0) addedge(0,S,i,A[i]),LOW+=A[i];
else if(A[i]<0) addedge(0,i,T,-A[i]);
}
int fl=din(S,T);
if(fl<LOW) {
printf("NO\n");
exit(0);
}else {
printf("YES\n");
for(int i=1;i<=n;i++) {
for(int j=0;j<(int)g[i].size();j++) {
edge& e=g[i][j];
if(e.id) {
ans[e.id]=up[e.id]-e.cap;
}
}
}
for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
}
return 0;
}

有源汇有上下界最大流

因为在原图中有源点和汇点,他们可以不满足流量守恒,但我们要至少先判断有没有可行流,所以先用虚拟源点和汇点跑一遍是否能满足那些流入量和流出量不同的边,这时原图中的原点和汇点是要满足流量守恒的,所以我们要建立一条原图中的汇点到源点容量无穷的边。判断过后我们要得到原图中的原点到汇点的最大流所以再跑一遍。

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
#include <bits/stdc++.h>
using namespace std;
const int maxn=205+5;
const int maxm=(int)1e4+5;
const int inf=0x3f3f3f3f;
struct edge{
int id,to,cap,rev;
edge(int id=0,int to=0,int cap=0,int rev=0): id(id),to(to),cap(cap),rev(rev) {}
};
vector<edge> g[maxn];
void addedge(int id,int u,int v,int cap)
{
g[u].push_back(edge(id,v,cap,(int)g[v].size()));
g[v].push_back(edge(0,u,0,(int)g[u].size()-1));
}
int n,m,up[maxm],A[maxn];
int S,T,ss,tt,N,q[maxn+5],dis[maxn+5];
bool bfs(int st,int ed)
{
int head=0,tail=0;
memset(dis,-1,sizeof(dis));
dis[st]=0;
q[head]=st;
while(head<=tail) {
int v=q[head%N];head++;
for(int i=0;i<(int)g[v].size();i++) {
edge &e=g[v][i];
if(e.cap>0 && dis[e.to]==-1) {
dis[e.to]=dis[v]+1;
tail++;q[tail%N]=e.to;
}
}
}
return ~dis[ed];
}
int las[maxn+5];
int dfs(int v,int ed,int F)
{
if(v==ed) return F;
for(int& i=las[v];i<(int)g[v].size();i++) {
edge &e=g[v][i];
if(e.cap>0 && dis[e.to]==dis[v]+1) {
int d=dfs(e.to,ed,min(F,e.cap));
if(d>0) {
e.cap-=d;
g[e.to][e.rev].cap+=d;
return d;
}
}
}
return 0;
}
int din(int st,int ed)
{
int tmp=0,ret=0;
while(bfs(st,ed)) {
memset(las,0,sizeof(las));
if((tmp=dfs(st,ed,inf))>0) ret+=tmp;
}
return ret;
}
int main()
{
scanf("%d%d%d%d",&n,&m,&ss,&tt);
int u,v,L,R,LOW=0;
S=0,T=n+1,N=n+5;
for(int i=1;i<=m;i++) {
scanf("%d%d%d%d",&u,&v,&L,&R);
addedge(i,u,v,R-L);
A[u]-=L;A[v]+=L;
up[i]=R;
}
for(int i=1;i<=n;i++) {
if(A[i]>0) addedge(0,S,i,A[i]),LOW+=A[i];
else addedge(0,i,T,-A[i]);
}
addedge(0,tt,ss,inf);
int fl=din(S,T);
if(fl>=LOW) printf("%d\n",din(ss,tt));
else printf("please go home to sleep\n");
return 0;
}

有源汇有上下界最小流

相对可行流而言,需要从原图中的汇点向源点退流,退流是不会影响哪些容量为下界的边的,因为$S$,$T$的所有边都割掉了(即$S$没有入度,$T$没有出度,那么即便是退流的时候退到了与$S$或者$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
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
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
namespace io{
const int L=30000020;
int f;
char ibuf[L],*iS,*iT,c;
inline char Gc(){
if(iS==iT){
iT=(iS=ibuf)+fread(ibuf,1,L,stdin);
return iS==iT?EOF:*iS++;
}
return*iS++;
}
template<class I>void Gi(I&x){
for(f=1,c=Gc();c<'0'||c>'9';c=Gc())if(c=='-')f=-1;
for(x=0;c<='9'&&c>='0';c=Gc())x=x*10+(c&15);x*=f;
}
};
using io::Gi;
namespace mfIO {
inline int readInt()
{
char c;int tmp=0,x=1;c=getchar();
while(c>'9' || c<'0') {if(c=='-') x=-1;c=getchar();}
while(c>='0' && c<='9') {tmp=tmp*10+c-'0';c=getchar();}
return tmp*x;
}
inline ll readLL()
{
char c;ll tmp=0,x=1;c=getchar();
while(c>'9' || c<'0') {if(c=='-') x=-1;c=getchar();}
while(c>='0' && c<='9') {tmp=tmp*10+c-'0';c=getchar();}
return tmp*x;
}
inline void writeInt(int x)
{
if(x==0) {putchar('0');return;}
if(x<0) x*=-1;
char s[21];int tp=0;
while(x>0) s[++tp]=x%10+'0',x/=10;
while(tp) putchar(s[tp--]);
}
inline void writeLL(ll x)
{
if(x==0) {putchar('0');return;}
if(x<0) x*=-1;
char s[21];int tp=0;
while(x>0) s[++tp]=x%10+'0',x/=10;
while(tp) putchar(s[tp--]);
}
}
using mfIO::readInt;
using mfIO::readLL;
using mfIO::writeInt;
using mfIO::writeLL;
const int maxn=50005+5;
const int maxm=125005+5;
const int inf=0x3f3f3f3f;
struct edge{
int id,to,cap,rev;
edge(int id=0,int to=0,int cap=0,int rev=0): id(id),to(to),cap(cap),rev(rev) {}
};
vector<edge> g[maxn];
int tag=-1;
void addedge(int id,int u,int v,int cap,bool lab=false)
{
g[u].push_back(edge(id,v,cap,(int)g[v].size()));
if(lab) tag=(int)g[u].size()-1;
g[v].push_back(edge(0,u,0,(int)g[u].size()-1));
}
int up[maxm],A[maxn];
int dis[maxn],cur[maxn],q[maxn+5],n,m,S,T,N,ss,tt;
bool bfs(int st,int ed)
{
memset(dis,-1,sizeof(dis));
dis[st]=0;
int head=0,tail=0;
q[head]=st;
while(head<=tail) {
int u=q[head%N];head++;
for(int i=0;i<(int)g[u].size();i++) {
edge& e=g[u][i];
if(e.cap>0 && dis[e.to]==-1) {
dis[e.to]=dis[u]+1;
tail++;q[tail%N]=e.to;
}
}
}
return dis[ed]!=-1;
}
int dfs(int v,int ed,int mf)
{
if(v==ed) return mf;
for(int &i=cur[v];i<(int)g[v].size();i++) {
int u=g[v][i].to;
edge& e=g[v][i];
if(e.cap>0 && dis[u]==dis[v]+1) {
int F=dfs(u,ed,min(mf,e.cap));
if(F>0) {
g[v][i].cap-=F;
g[u][g[v][i].rev].cap+=F;
return F;
}
}
}
return 0;
}
int din(int st,int ed)
{
int ret=0,tmp=0;
while(bfs(st,ed)) {
memset(cur,0,sizeof(cur));
while((tmp=dfs(st,ed,inf))>0) ret+=tmp;
}
return ret;
}
int LOW=0;
void AddEdge(int i,int u,int v,int L,int R)
{
addedge(i,u,v,R-L);
A[u]-=L;A[v]+=L;
up[i]=R;
}
void NewEdge(int st,int ed)
{
for(int i=1;i<=n;i++) {
if(A[i]>0) addedge(0,S,i,A[i]),LOW+=A[i];
else addedge(0,i,T,-A[i]);
}
addedge(0,ed,st,inf,1);
}
int pan(int st,int ed)
{
int fl=din(S,T);
if(fl>=LOW) {
int ril=inf-g[ed][tag].cap;
edge & e=g[ed][tag];
e.cap=g[e.to][e.rev].cap=0;
ril-=din(ed,st);
return ril;
}
else return -1;
}
int main()
{
Gi(n),Gi(m),Gi(ss),Gi(tt);
int u,v;
int L,R;
S=0,T=n+1,N=n+5;
for(int i=1;i<=m;i++) {
Gi(u),Gi(v),Gi(L),Gi(R);
AddEdge(i,u,v,L,R);
}
NewEdge(ss,tt);
int ans=pan(ss,tt);
if(ans==-1) puts("please go home to sleep");
else printf("%d\n",ans);
return 0;
}

最小割,最大流

为什么互为对偶问题?

  • 任意一个流不会超过最小割的值。
  • 可以找到一组解$p,q$使得最大流=最小割
  • 且这组解为各自问题的最优解

bzoj 1497 [NOI2006]最大获利

不难发现这样的限制条件:如果一个客户被满足,那么一定对应的两个基站要被建立;如果两个基站中有一个没有被建立,那就满足不了这个客户。
于是可以将客户群分为两个集合,一个是被满足的,一个是不被满足的。
这个可以对应图上的$S-T$割。即$S$对应不能满足的客户,$T$对应可以满足的客户。
然后考虑建图,为了满足条件:如果割掉了一个客户的点(这个客户不能被满足),则不能全割掉对应的两个基站。
则要保证割边全部是与$S$相邻的收益,或者与$T$相连的建立基站的费用。
建图:
$S\rightarrow$客户$i$容量为收客户的钱
基站$i$到$T$容量为建立基站的钱
客户$i$对于$A_i,B_i$建立容量为$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
#include <bits/stdc++.h>
using namespace std;
const int maxn=5000+5;
const int maxm=50000+5;
const int dmax=maxm*2;
const int inf=0x3f3f3f3f;
struct edge {
int to,cap,rev;
edge(int to=0,int cap=0,int rev=0): to(to),cap(cap),rev(rev) {}
};
vector<edge > g[dmax];
void addedge(int u,int v,int cap)
{
g[u].push_back(edge(v,cap,(int)g[v].size()));
g[v].push_back(edge(u,0,(int)g[u].size()-1));
}
int n,m,p[maxn],S,T,N,q[dmax+5],dis[dmax+5];
bool bfs(int st,int ed)
{
memset(dis,-1,sizeof(dis));
dis[st]=0;
int head=0,tail=0;
q[head]=st;
while(head<=tail) {
int v=q[head%N];head++;
for(int i=0;i<(int)g[v].size();i++) {
edge &e=g[v][i];
if(e.cap>0 && dis[e.to]==-1) {
dis[e.to]=dis[v]+1;
tail++;q[tail%N]=e.to;
}
}
}
return ~dis[ed];
}
int cur[dmax];
int dfs(int v,int ed,int F)
{
if(v==ed) return F;
for(int &i=cur[v];i<(int)g[v].size();i++) {
edge &e=g[v][i];
if(e.cap>0 && dis[e.to]==dis[v]+1) {
int d=dfs(e.to,ed,min(F,e.cap));
if(d>0) {
e.cap-=d;
g[e.to][e.rev].cap+=d;
return d;
}
}
}
return 0;
}
int din(int st,int ed)
{
int ret=0,tmp=0;
while(bfs(st,ed)) {
memset(cur,0,sizeof(cur));
while((tmp=dfs(st,ed,inf))>0) ret+=tmp;
}
return ret;
}
int main()
{
scanf("%d%d",&n,&m);
S=0,T=n+m+1,N=n+m+5;
for(int i=1;i<=n;i++) scanf("%d",&p[i]);
int a,b,c,ans=0;
for(int i=1;i<=m;i++) {
scanf("%d%d%d",&a,&b,&c);ans+=c;
addedge(S,i,c);addedge(i,a+m,inf),addedge(i,b+m,inf);
}
for(int i=1;i<=n;i++) addedge(i+m,T,p[i]);
printf("%d\n",ans-din(S,T));
return 0;
}

bzoj 1189 [HNOI2007]紧急疏散evacuate

因为求时间,并且每个点上的人都可以停留并且门每次只能通过一个人,所以要把门拆为个个时间上的状态。为了减少建边,需要预先处理出所有人到门的时间。门上可以停留(可以转化为一个人到这个门路径上任何的停留),所以每个门当前时间向下一个时间连边。然后就是一个多源汇的网络流了。

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
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
#include <bits/stdc++.h>
using namespace std;
const int maxn=25;
const int dmax=maxn*maxn+450*maxn*maxn+100;
const int inf=INT_MAX-1;
typedef pair<int ,int > pii;
#define fir first
#define sec second
#define MP make_pair
struct edge{
int to,cap,rev;
edge(int to=0,int cap=0,int rev=0): to(to),cap(cap),rev(rev) {}
};
vector<edge> g[dmax];
void addedge(int u,int v,int cap)
{
g[u].push_back(edge(v,cap,(int)g[v].size()));
g[v].push_back(edge(u,0,(int)g[u].size()-1));
}
int n,m,S,T,N,tot=0,q[dmax+5],dis[dmax+5];
bool bfs(int st,int ed)
{
int head=0,tail=0;
memset(dis,-1,sizeof(dis));
dis[st]=0;
q[head]=st;
while(head<=tail) {
int v=q[head%N];head++;
for(int i=0;i<(int)g[v].size();i++) {
edge &e=g[v][i];
if(e.cap>0 && dis[e.to]==-1) {
dis[e.to]=dis[v]+1;
tail++;q[tail%N]=e.to;
}
}
}
return ~dis[ed];
}
int las[dmax+5];
int dfs(int v,int ed,int F)
{
if(v==ed) return F;
for(int& i=las[v];i<(int)g[v].size();i++) {
edge &e=g[v][i];
if(e.cap>0 && dis[e.to]==dis[v]+1) {
int d=dfs(e.to,ed,min(F,e.cap));
if(d>0) {
e.cap-=d;
g[e.to][e.rev].cap+=d;
return d;
}
}
}
return 0;
}
int din(int st,int ed)
{
int tmp=0,ret=0;
while(bfs(st,ed)) {
memset(las,0,sizeof(las));
if((tmp=dfs(st,ed,inf))>0) ret+=tmp;
}
return ret;
}
int id(int x,int y){return (x-1)*m+y;}
int idt(int x,int y,int t){return (x-1)*m+y+t*n*m;}
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
char s[maxn][maxn];
int dist[maxn][maxn][maxn<<2];
vector<pii > dor;
struct info{
int x,y,stp;
info(int x=0,int y=0,int stp=0): x(x),y(y),stp(stp) {}
};
bool vis[maxn][maxn];
queue<info> Q;
void bfs2(int x,int y)
{
memset(vis,0,sizeof(vis));
Q.push(info(x,y,0));vis[x][y]=true;
info nw;
int sx=0,sy=0,nx=0,ny=0,ds=0;
while(!Q.empty()) {
nw=Q.front();Q.pop();
sx=nw.x,sy=nw.y,ds=nw.stp;
for(int j=0;j<(int)dor.size();j++) {
if(sx==dor[j].fir && sy==dor[j].sec) dist[x][y][j]=ds;
}
for(int i=0;i<4;i++) {
nx=sx+dx[i],ny=sy+dy[i];
if(nx>=1 && nx<=n && ny>=1 && ny<=m && s[nx][ny]!='X' && !vis[nx][ny]) {
vis[nx][ny]=true;
Q.push(info(nx,ny,ds+1));
}
}
}
}
bool cal(int tim)
{
for(int i=1;i<=n;i++) {
for(int j=1;j<=m;j++) {
if(s[i][j]=='.') {
addedge(S,id(i,j),1);
for(int k=0;k<(int)dor.size();k++) {
if(dist[i][j][k]<=tim)
addedge(id(i,j),idt(dor[k].fir,dor[k].sec,dist[i][j][k]),1);
}
}
else if(s[i][j]=='D') {
for(int k=1;k<=tim;k++) {
addedge(idt(i,j,k),T,1);
if(k>1) addedge(idt(i,j,k-1),idt(i,j,k),inf);
}
}
}
}
int tmp=din(S,T);
for(int i=1;i<=n*m+tim*n*m;i++) g[i].clear();
g[S].clear(),g[T].clear();
return tmp>=tot;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%s",s[i]+1);
S=0,T=n*m+400*n*m+1,N=n*m+400*n*m+5;
for(int i=1;i<=n;i++) {
for(int j=1;j<=m;j++) {
if(s[i][j]=='D') dor.push_back(MP(i,j));
}
}
for(int i=1;i<=n;i++) {
for(int j=1;j<=m;j++) {
if(s[i][j]=='.') {
tot++;
bfs2(i,j);
}
}
}
int L=0,R=n*m,ans=inf;
while(L<=R) {
int mid=(L+R)>>1;
if(cal(mid)) {ans=mid;R=mid-1;}
else L=mid+1;
}
if(ans==inf) printf("impossible\n");
else printf("%d\n",ans);
return 0;
}
/*
5 5
XXXXX
X...D
XX.XX
X..XX
XXDXX
*/