2017-7-29 大佬讲课笔记

发表于 | 分类于

网络流

虽然dalao声音不大，但是很好听呢。不过dalao很快的进入正经主题了呢。

基本定义

  1. 有n个点，m条有向边，其中源点 s 只有出边，没有入边。汇点 t 只有入边，没有出边。
  2. 每条边都有一个容量和流量，通常用c(u,v)表示从u到v的容量，f(u,v)代表流量。

我们可以把这些有向边想象成运输管道，有一定数量的物品，从源点 s 出发，经过这些管道，最终流入汇点t，而每条管道的运输单个物品的次数是有限的。

可行流

  • 源点s的总流出量等于汇点t的总流入量
  • 其它点的总流入量等于总流出量
  • 每条边的流量不超过容量上限

增广路

基本概念

假设有这样一条路径，从源点s一直到汇点t每条边的已用流量都小于容量，那我们便能找到在这条路径上能够增加的流量的最大值 val = min{c(u,v)-f(u,v)}。加上这个值后，这个流依然是可行流，而这条路径就是增广路。

残余网络：每条边减去已用的流量，再在反向边上加上相同的流量。

思路

从零流开始不断寻找增广路

依据

增广路定理：
假如当前残余网络中仍能找到一条增广路，那么当前的可行流仍可以增大，不是最大流。反之，如果到了“无路可增”的地步，当前流就是最大流。

实现过程

  • 为什么要加反向边？
    首先，假如没有反向边的话，那么找增广路其实是需要按照一定的组合，才能找到最大流。
    也就是说，我们无法在找到一条增广路时，确保这样可能是一种可行的最大流的方案。
    因此，我们需要对前面的方案进行调整，比如有的边流量不需要使用，需要“退”回去，反向边就起到这样的作用。
  • 在实际运行过程中反向边与原来的边是没有区分的，这样一步步找增广路就可以确保最终为最大流。

EdmondsKarp

不断bfs，每一次遍历O(n²)，最多遍历m次，O(m*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
int bfs() {
	memset(pre,-1,sizeof(pre));
	for(int i=1;i<=n;++i)
		flow[i]=INF;
	queue<int>q;
	pre[S]=0,q.push(S);
	while(!q.empty()){
		int op(q.front());
		q.pop();
		for(int i=1;i<=n;++i){
			if(i==S||pre[i]!=-1||c[op][i]==0)
				continue;
			pre[i]=op; //找到未遍历过的点
			flow[i]=min(flow[op],c[op][i]); // 更行路径上的最小值 
			q.push(i);
		}
	}
	if(flow[T]==INF)
		return -1;
	return flow[T];
}
int solve() {
	int ans(0);
	while(1){
		int k(bfs());
		if(k==-1)
			break;
		ans+=k;
		int nw(T);
		while(nw!=S){//更新残余网络 
			c[pre[nw]][nw]-=k,c[nw][pre[nw]]+=k;
			nw=pre[nw];
		}
	}
	return ans;
}

Dinic

  1. bfs建立层次图
  2. 在层次图中dfs直到找不到增广路
  3. 重复以上过程直到找不到增广路
    每次重新分层，汇点所在层次严格递增。n个点的层次图最多n层，所以最多重新分层n次。
    在同一个层次图中，每条增广路都有一个瓶颈，即最小值的限制所在边，而两次增广的瓶颈不可能相同，所以增广路最多m条。
    搜索每一条增广路时，前进和回溯都最多n次（最多n个点），所以一次dfs是O(nm)的复杂度。
    综上，是O(m*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
    bool bfs(){//bfs建立层次图
    	memset(dep,0,sizeof(dep));
    	hd=tl=0;
    	q[++tl]=s;
    	dep[s]=1;
    	while(hd<tl){
    		int op(q[++hd]);
    		for(int i=headlist[op];i!=-1;i=edge[i].next){
    			if(edge[i].val&&(!dep[edge[i].v])){
    				dep[edge[i].v]=dep[op]+1;
    				q[++tl]=edge[i].v;
    				if(edge[i].v==t)//遍历到t就返回，此时该层次图已建好
    					return true;//再访问其它的点没有必要
    			}
    		}
    	}
    	return false;
    }
    int dfs(int op,int fw){
    	if(op==t)
    		return fw;
    	int tmp(fw),k;
    	for(int i=headlist[op];i!=-1;i=edge[i].next){
    		if(edge[i].val&&tmp&&dep[edge[i].v]==dep[op]+1){
    			k=dfs(edge[i].v,min(edge[i].val,tmp));
    			if(!k){//该点后面没有路径，所以要从层次图中删去
    				dep[edge[i].v]=0;//因为和当前点op层次相同的点
    				continue;//还可能会访问到它
    			}
    			edge[i].val-=k;
    			edge[i^1].val+=k;
    			tmp=k;
    		}
    	}
    	return fw-tmp;
    }

最大流

网络流中大部分可以分为两种类型的点：与S相连的点和与T相连的点。所以建模的时候也可以向这方面考虑，将点分成两个集合。

搭配飞行员

传送门
题目大意：
有n(n ≤ 100)个驾驶员（其中包括a个正驾驶员和b个副驾驶员）驾驶一种飞机，每架需要一个正驾驶员和一个副驾驶员。有些驾驶员不能在同一架飞机上，问如何搭配驾驶员才能使出航的飞机最多。
题解：
题意很明了，将正驾驶员与S相连，容量为1，将副驾驶员与T相连，边容量为1，将可以在一辆飞机上的正驾驶员和副驾驶员相连，边容量>0即可。与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
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
int n,n1,n2;
struct edge{
	int s,e,n,w;
}a[2001];
int pre[101],tot;
inline void insert(int s,int e,int w){
	a[tot].s=s;
	a[tot].e=e;
	a[tot].w=w;
	a[tot].n=pre[s];
	pre[s]=tot++;
}
int x,y;
int sup;
int inf(0x7fffffff);
int adj[101];
int dis[101];
inline bool bfs(int s,int t){
	memset(dis,0,sizeof(dis));
	queue<int>q;
	q.push(s);
	dis[s]=1;
	while(!q.empty()){
		int k(q.front());
		q.pop();
	 	for(int i=pre[k];i!=-1;i=a[i].n){
			if(!a[i].w||dis[a[i].e])
				continue;
			dis[a[i].e]=dis[k]+1;
			if(a[i].e==t)
				return true;
			q.push(a[i].e);
        }
    }
    return false;
}
inline int my_min(int a,int b){
	return a<b?a:b;
}
inline int dfs(int now,int flow){
	if(now==sup)
		return flow;
	int tmp(flow),f;
	for(int i=pre[now];i!=-1;i=a[i].n){
		if(!a[i].w||!tmp||dis[a[i].e]!=dis[now]+1)
			continue;
		f=dfs(a[i].e,my_min(a[i].w,tmp));
		if(!f){
			dis[a[i].e]=0;
			continue;
		}
		a[i].w-=f;
		a[i^1].w+=f;
		tmp-=f;
	}
	return flow-tmp;
}
inline void dinic(int s,int t){
	int ans(0);
	//bfs(s,t);cout<<"j";
	while(bfs(s,t))
		ans+=dfs(s,inf);
	printf("%d",ans);
}
inline int gg(){
	freopen("flyer.in","r",stdin);
	freopen("flyer.out","w",stdout);
	memset(pre,-1,sizeof(pre));
	scanf("%d%d",&n,&n1);
	sup=n+1;
	n2=n-n1;
	while(scanf("%d%d",&x,&y)==2)
		insert(x,y,1),insert(y,x,0);
	for(int i=1;i<=n1;i++)
		insert(0,i,1),insert(i,0,0);
	for(int i=n1+1,j=1;j<=n2;j++,i++)
		insert(i,sup,1),insert(sup,i,0);
	dinic(0,sup);
}
int K(gg());
int main(){;}

士兵占领

传送门
题面：
有一个n*m的棋盘，有的格子是障碍。现在你要选择一些格子来放置一些士兵，一个格子里最多可以放置一个士兵，障碍格里不能放置士兵。要求第i行至少放置了ri个士兵，第j列至少放置了cj个士兵。求士兵最少是多少。
假设我们不考虑一个位置对它所在行，列两者的贡献。那么答案就是sum=∑(i 1~n)ri+∑(j 1~m)cj。但实际上，有的点对两者都有贡献，结果为sum减去的点的数量，士兵数量最少即这样的点数量最多。
之后，建图和上一道题类似。将每行作为一个点与S相连，容量为ri，每列作为一个点与T相连，容量为cj。可以放士兵的点行与列相连，容量为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
114
115
116
117
118
119
120
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
inline int read(){
    int sum(0);
    char ch(getchar());
    for(;ch<'0'||ch>'9';ch=getchar());
    for(;ch>='0'&&ch<='9';sum=sum*10+ch-'0',ch=getchar());
    return sum;
}
struct edge{
    int s,e,w,n;
}a[50001];
int pre[250],tot;
inline void insert(int s,int e,int w){
    a[tot].s=s;
    a[tot].e=e;
    a[tot].w=w;
    a[tot].n=pre[s];
    pre[s]=tot++;
}
int n,m,k;
int sup;
int l[101],c[101];
bool g[101][101];
int sum(0);
int dis[301];
inline bool bfs(int s,int t){
	memset(dis,0,sizeof(dis));
	queue<int>q;
	q.push(s);
	dis[s]=1;
	while(!q.empty()){
		int k(q.front());
		q.pop();
	 	for(int i=pre[k];i!=-1;i=a[i].n){
			if(!a[i].w||dis[a[i].e])
				continue;
			dis[a[i].e]=dis[k]+1;
			if(a[i].e==t)
				return true;
			q.push(a[i].e);
        }
    }
    return false;
}
inline int my_min(int a,int b){
    return a<b?a:b;
}
inline int dfs(int now,int flow){
	if(now==sup)
		return flow;
	int tmp(flow),f;
	for(int i=pre[now];i!=-1;i=a[i].n){
		if(!a[i].w||!tmp||dis[a[i].e]!=dis[now]+1)
			continue;
		f=dfs(a[i].e,my_min(a[i].w,tmp));
		if(!f){
			dis[a[i].e]=0;
			continue;
		}
		a[i].w-=f;
		a[i^1].w+=f;
		tmp-=f;
	}
	return flow-tmp;
}
inline bool judge(){
    int tmp;
    for(int i=1;i<=m;i++){
        tmp=0;
        for(int j=1;j<=n;j++)
            if(g[i][j])
                tmp++;
        if(tmp<l[i])
            return true;
    }
    for(int j=1;j<=n;j++){
        tmp=0;
        for(int i=1;i<=m;i++)
            if(g[i][j])
                tmp++;
        if(tmp<c[j])
            return true;
    }
    return false;
}
int ans(0),inf(0x7fffffff);
int main(){
    memset(pre,-1,sizeof(pre));
    memset(g,true,sizeof(g));
    m=read(),n=read(),k=read();
    sup=n+m+1;
    for(int i=1;i<=m;i++)
        l[i]=read(),sum+=l[i];
    for(int i=1;i<=n;i++)
        c[i]=read(),sum+=c[i];
    for(int i=1;i<=k;i++){
        int x(read()),y(read());
        g[x][y]=0;
    }
    if(judge()){
        puts("JIONG!");
        return 0;
    }
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            if(g[i][j])
                insert(i,j+m,1),insert(j+m,i,0);
    for(int i=1;i<=m;i++)
        insert(0,i,l[i]),insert(i,0,0);
    for(int i=1;i<=n;i++)
        insert(i+m,sup,c[i]),insert(sup,i+m,0);
    while(bfs(0,sup))
        ans+=dfs(0,inf);
    printf("%d",sum-ans);
    return 0;
}

分子切割

题目描述：
有一个由n*m个单位放个组成的矩形区域。有两种原子，用A和B表示。有的单位方格中没有原子，有的单位方格中只有一个原子。若两个单位方格有公共边，那么他们是相邻的。如果一个A原子与两个B原子相邻，并且这两个B原子与A原子形成直角，A原子在直角的定点处，那么就可以把这三个原子整体切割下来，得到一个“L”形分子。
求最多切割出多少个“L”形分子。（n，m ≤ 500）
题解：
要黑白染色
我们可以想到肯定是由S-B-A-B-T这样一条路径代表一个“L”形分子。之后便是建模限制每个点的使用次数以及B-A-B是直角。由此可以看出如果所有的B是一类点肯定是行不通的。但我们注意到一个“L”形分子的两个B原子必在相邻的两列（行）上，就可以按列（行）染色了。
S向奇数列的B点建边容量为1，奇数列的B点只能流向周围的A点。
偶数列的B点向T建边容量为1，且只能由周围的A点流向偶数列的B点
这样就可以保证流过的B-A-B一定是直角。
但这样并不能保证A的使用次数，如上图所示，A会重复使用。为了限制A的使用次数，我们可以拆点，将A拆成两个点A1和A2，同时在A1A2间连一条容量为1的边，流入A的连A1，流出A的连A2。

紧急疏散

传送门
题解：
显然肯定有一个时间，在此之前不能完全逃离，在此之后可以完全逃离。这样我们就可以二分了。
每个位置上人数不限，所以除去到门上时，每个人可以单独考虑。
对一扇门来说，每个人到门前的时间可能不同，即每个人可以利用门逃离的时间段不同，我们要限制每个人可使用的时间，可以每扇门每个时间单独一个点。

具体建模：
S向每个人连边，容量为1。每个人向每扇门可以使用的时间的一系列点连边，容量为1，每扇门的每个时间点向T连边，容量为1。
每个人每扇门可以使用的时间即这个人到这扇门最短时间及以后，所以要先跑一遍最短路。
这样，当最大流等于人的数量时，就可以完全逃离。

Collector’s Problem

题目描述：
Bob和他的朋友从糖果包装里收集贴纸。Bob和他的朋友总共n人。共有m种不同的贴纸。
每人手里都有一些（可能有重复的）贴纸，并且只跟别人交换他所没有的贴纸。贴纸总是一对一交换。
Bob比这些朋友更聪明，因为他意识到只跟别人交换自己没有的贴纸并不总是最优的。在某些情况下，换来一张重复的贴纸更划算。
假设Bob的朋友只跟Bob交换（他们之间不交换），并且这些朋友只会出让手里的重复贴纸来交换他们没有的不同贴纸。你的任务是帮助Bob算出他最终可以得到的不同贴纸的最大数量。
2≤n≤10,5≤m≤25
题解：
对于Bob的每个朋友，Bob最多只能与他交换x次（这个朋友没有的贴纸的种数与他拥有的重复贴纸数量的较小值）。Bob朋友的作用就是将Bob手中的一种贴纸X换成另一种贴纸Y。
所以将每种贴纸作为一个结点，由S向其连边，容量为Bob拥有的没中贴纸的数量，并且向T连边，容量为1。
对于每个朋友，其没有的贴纸的点向其连边，容量为1（最多换一次）。并且他向拥有的重复贴纸的点连边，容量为num-1。
这样从一种贴纸的结点流经一个朋友再流向另一种贴纸，就等于完成了一次交换，而由于又流回了贴纸结点仍然可以用该贴只去做交换。
这样最大流便是能够拥有的贴纸的最大种数。

最小割

定义

把所有的结点分为两个集合S和T，其中s在S中，t在T中。把所有起点在S中，终点在T中的边删除，就无法从s到达t了，这样的一个划分称为s-t割，它的容量为删除的所有边的容量的总值，最小割即为所有s-t割中的最小值。

求解最小割基于一个事实：最小割等于最大流

证明：
对于一个割来说，所有从s到t的流量必定经过删除的边，那么最大流一定<=割的值，同理可以推出最大流<=任意割的值。
下面来看一个已经跑完最大流的残余网络，此时图中已没有从s到t的路径。
将s和s能到达的所有点划分为S集，剩余点为T集。中间的所有边为一个割，
且均满载（剩余容量为0），那么当前流也就是最大流等于割的值，又因割
的值大于等于最大流，所以此时的割即为最小割，且与最大流相等。

王者之剑

传送门
取值时一定在偶数时刻，取走一个格子的值后，就不能取走与其相邻格子的值，也就是相邻格子之间是不相容的。
证明：
假设取值时在奇数时刻，那么取值前的上一个时刻，必定在这个格子的相邻格子中，而那时又是偶数时刻，所以这个格子的值会消失，无法取到。

题解：
这道题可以从怎样走的思维模式中跳出来，转化到怎样去取上。因为只要取的格子相容，是一定有合法路径的。
有不容的点就可以转化到最小割上，用总值减去割掉最小的值，就是最优解。

具体建模：
此时是若两者都取不相容，所以需要翻转源汇。将矩阵按黑白棋盘染色，S与白点相连，容量为权值，黑点与T相连，容量为权值。不相容的点之间连边，容量为INF。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
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
inline int read(){
	int sum(0);
	char ch(getchar());
	for(;ch<'0'||ch>'9';ch=getchar());
	for(;ch>='0'&&ch<='9';sum=sum*10+(ch^48),ch=getchar());
	return sum;
}
struct edge{
	int e,n,w;
}a[2000001];
int pre[100001],tot;
inline void insert(int s,int e,int w){
	a[tot].e=e;
	a[tot].w=w;
	a[tot].n=pre[s];
	pre[s]=tot++;
}
int n,m;
int w[105][105],col[105][105];
inline void paint(){
	int now(1);
	for(int i=1;i<=n;i++){
		now^=1;
		for(int j=1;j<=m;j++){
			if(j&1)
				col[i][j]=now;
			else
				col[i][j]=now^1;
		}
	}
}
int S(0),T;
int ans(0),inf(0x7fffffff),sum(0);
inline void build(){
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			if(col[i][j])
				insert(S,(i-1)*m+j,w[i][j]),insert((i-1)*m+j,S,0);
			else
				insert((i-1)*m+j,T,w[i][j]),insert(T,(i-1)*m+j,0);
		}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			if(col[i][j]){
				if(i!=1)
					insert((i-2)*m+j,(i-1)*m+j,0),insert((i-1)*m+j,(i-2)*m+j,inf);
				if(i!=n)
					insert(i*m+j,(i-1)*m+j,0),insert((i-1)*m+j,i*m+j,inf);
				if(j!=1)
					insert((i-1)*m+j-1,(i-1)*m+j,0),insert((i-1)*m+j,(i-1)*m+j-1,inf);
				if(j!=m)
					insert((i-1)*m+j+1,(i-1)*m+j,0),insert((i-1)*m+j,(i-1)*m+j+1,inf);
			}
		}
}
int dis[10010];
inline bool bfs(int s,int t){
	memset(dis,0,sizeof(dis));
	dis[s]=1;
	queue<int>q;
	q.push(s);
	while(!q.empty()){
		int k(q.front());
		q.pop();
		for(int i=pre[k];i!=-1;i=a[i].n){
			int e(a[i].e);
			if(!dis[e]&&a[i].w){
				dis[e]=dis[k]+1;
				q.push(e);
				if(e==t)
					return true;
			}
		}
	}
	return false;
}
inline int my_min(int a,int b){
	return a<b?a:b;
}
inline int dfs(int now,int flow){
	if(now==T)
		return flow;
	int tmp(flow),f;
	for(int i=pre[now];i!=-1;i=a[i].n){
		int e(a[i].e);
		if(dis[e]==dis[now]+1&&tmp&&a[i].w){
			f=dfs(e,my_min(tmp,a[i].w));
			if(!f){
				dis[e]=0;
				continue;
			}
			a[i].w-=f;
			a[i^1].w+=f;
			tmp-=f;
		}
	}
	return flow-tmp;
} 
inline int gg(){
	freopen("Excalibur.in","r",stdin);
	freopen("Excalibur.out","w",stdout);
	memset(pre,-1,sizeof(pre));
	n=read(),m=read();
	T=n*m+1;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			w[i][j]=read(),sum+=w[i][j];
	paint();
	build();
	while(bfs(S,T))
		ans+=dfs(S,inf);
	printf("%d",sum-ans);
	return 0;
}
int K(gg());
int main(){;}

happiness

传送门
题解：
此题与上一题相似，不过这次是选择不同时不能得到额外的权值，无需翻转源汇，S对所有点来说都是文科，T对所有点来说都是理科。
对于单独两个点来说，只有两种情况。
若两个人都选文科，需要割掉第2，4条边，代价为两个人选理科分别的贡献，以及他们一起选理科的贡献，因为所有的点都是等价的，2，4边的权值除各自选理科贡献外再加上一半的额外贡献。
若两个人都选择理科同理。

若两个人选择不同，假设x选择文科，y选择理科，那么需要割掉2，3，5。
此时2，3权值和为分别选择科目的贡献和一半的同时选择理科和同时选择文科的贡献。还需再减去剩余的一半，即应是5的权值。(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
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
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
inline int read(){
	int sum(0);
	char ch(getchar());
	for(;ch<'0'||ch>'9';ch=getchar());
	for(;ch>='0'&&ch<='9';sum=sum*10+(ch^48),ch=getchar());
	return sum;
}
struct edge{
	int e,n,w;
}a[200001];
int pre[10010],tot;
inline void insert(int s,int e,int w){
	a[tot].e=e;
	a[tot].w=w;
	a[tot].n=pre[s];
	pre[s]=tot++;
}
int n,m;
int w[101][101],l[101][101];
int jz1[101][101],jz2[101][101],jz3[101][101],jz4[101][101];
int sum(0),ans(0),inf(0x7fffffff);
int S(0),T;
int id[101][101];
inline void init(){
	freopen("nt2011_happiness.in","r",stdin);
	freopen("nt2011_happiness.out","w",stdout);
	memset(pre,-1,sizeof(pre));
	n=read(),m=read();
	T=n*m+1;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			w[i][j]=read()<<1,sum+=w[i][j]>>1,id[i][j]=(i-1)*m+j;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			l[i][j]=read()<<1,sum+=l[i][j]>>1;
	for(int i=1;i<n;i++)
		for(int j=1;j<=m;j++)
			jz1[i][j]=read(),sum+=jz1[i][j];
	for(int i=1;i<n;i++)
		for(int j=1;j<=m;j++)
			jz2[i][j]=read(),sum+=jz2[i][j];
	for(int i=1;i<=n;i++)
		for(int j=1;j<m;j++)
			jz3[i][j]=read(),sum+=jz3[i][j];
	for(int i=1;i<=n;i++)
		for(int j=1;j<m;j++)
			jz4[i][j]=read(),sum+=jz4[i][j];
}
inline void build(){
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			insert(S,id[i][j],w[i][j]+jz1[i][j]+jz1[i-1][j]+jz3[i][j]+jz3[i][j-1]),insert(id[i][j],S,0);
			insert(id[i][j],T,l[i][j]+jz2[i][j]+jz2[i-1][j]+jz4[i][j]+jz4[i][j-1]),insert(T,id[i][j],0);
		}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			if(i!=n)
				insert(id[i][j],id[i][j]+m,jz1[i][j]+jz2[i][j]),insert(id[i][j]+m,id[i][j],jz1[i][j]+jz2[i][j]);
			if(j!=m)
				insert(id[i][j],id[i][j]+1,jz3[i][j]+jz4[i][j]),insert(id[i][j]+1,id[i][j],jz3[i][j]+jz4[i][j]);
		}
}
int dis[10020];
inline bool bfs(int s,int t){
	memset(dis,0,sizeof(dis));
	dis[s]=1;
	queue<int>q;
	q.push(s);
	while(!q.empty()){
		int k(q.front());
		q.pop();
		for(int i=pre[k];i!=-1;i=a[i].n){
			int e(a[i].e);
			if(!dis[e]&&a[i].w){
				dis[e]=dis[k]+1;
				q.push(e);
				if(e==t)
					return true;
			}
		}
	}
	return false;
}
inline int my_min(int a,int b){
	return a<b?a:b;
}
inline int dfs(int now,int flow){
	if(now==T)
		return flow;
	int tmp(flow),f;
	for(int i=pre[now];i!=-1;i=a[i].n){
		int e(a[i].e);
		if(dis[e]==dis[now]+1&&tmp&&a[i].w){
			f=dfs(e,my_min(tmp,a[i].w));
			if(!f){
				dis[e]=0;
				continue;
			}
			a[i].w-=f;
			a[i^1].w+=f;
			tmp-=f;
		}
	}
	return flow-tmp;
}
inline void dinic(){
	while(bfs(S,T))
		ans+=dfs(S,inf);
	printf("%d",sum-(ans>>1));
}
inline int gg(){
	init();
	build();
	dinic();
	return 0;
}
int K(gg());
int main(){;}

人员雇佣

传送门
题解：
这道题与上一道考虑角度相同，首先从两个人的角度考虑
若两个人都被雇佣，割掉的边为2，4，权值分别为雇佣二人的代价。
若两个人都不被雇佣，需要割掉1，3，权值均为两人共同的收益。因为共同收益，两人是两份。
若两人选择不同，假设x被雇佣，y不被雇佣，需要割掉2，3，5。而此时还应减去一份存在于1中的共同受益，再减去两人选择不同的减损。也就是要减去两份共同收益，即为5的权值。

切糕

传送门
题解：
由题意得知，显然为最小割模型，将点权转化为边权。由S向(x,y,1)连边，边权为v(x, y,1)。由(x, y, z)向(x, y, z+1)连边，边权为v(x, y, z+1)。
最后由(x, y, R)向T连边，边权为INF。此题关键为这个选择的距离限制。
我们可以这样解决：由每个点向它相邻的点的下方的第d个点连边。也就由(x, y, z)向(x, y, z-d)连边，边权为INF。
首先，假设每条纵轴只割一条边。若两条边的距离大于d，一定会有图中所示路径，此时仍需要再割一条边。
假设再割一条右侧的边，此边与左边割掉的那条边的距离要 ≤ d，否则还会出现这样的路径。
只有距离 ≤ d，才能截断。
但此时，右边第一次截断的边已经没有必要了。因为只要上面两条边就可以截断了。
因此，每个纵轴只截断一条边，且相邻截断的边距离一定 ≤ d。

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<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
inline int read(){
	int sum(0);
	char ch(getchar());
	for(;ch<'0'||ch>'9';ch=getchar());
	for(;ch>='0'&&ch<='9';sum=sum*10+(ch^48),ch=getchar());
	return sum;
}
struct edge{
	int e,n,w;
}a[1000001];
int pre[64500],tot;
inline void insert(int s,int e,int w){
	a[tot].e=e;
	a[tot].w=w;
	a[tot].n=pre[s];
	pre[s]=tot++;
}
int p,q,r,d;
int id[41][41][41],w[41][41][41];
int cnt(0);
int S(0),T;
int ans(0),inf(0x7fffffff);
int dis[64500];
inline bool bfs(int s,int t){
	memset(dis,0,sizeof(dis));
	dis[s]=1;
	queue<int>q;
	q.push(s);
	while(!q.empty()){
		int k(q.front());
		q.pop();
		for(int i=pre[k];i!=-1;i=a[i].n){
			int e(a[i].e);
			if(!dis[e]&&a[i].w){
				dis[e]=dis[k]+1;
				q.push(e);
				if(e==t)
					return true;
			}
		}
	}
	return false;
}
inline int my_min(int a,int b){
	return a<b?a:b;
}
inline int dfs(int now,int flow){
	if(now==T)
		return flow;
	int tmp(flow),f;
	for(int i=pre[now];i!=-1;i=a[i].n){
		int e(a[i].e);
		if(dis[e]==dis[now]+1&&tmp&&a[i].w){
			f=dfs(e,my_min(tmp,a[i].w));
			if(!f){
				dis[e]=0;
				continue;
			}
			a[i].w-=f;
			a[i^1].w+=f;
			tmp-=f;
		}
	}
	return flow-tmp;
}
inline int gg(){
	freopen("nutcake.in","r",stdin);
	freopen("nutcake.out","w",stdout);
	memset(pre,-1,sizeof(pre));
	p=read(),q=read(),r=read(),d=read();
	T=p*q*r+1;
	for(int i=1;i<=r;i++)
		for(int j=1;j<=p;j++)
			for(int k=1;k<=q;k++){
				w[i][j][k]=read();
				id[i][j][k]=++cnt;
				insert(id[i-1][j][k],id[i][j][k],w[i][j][k]),insert(id[i][j][k],id[i-1][j][k],0);
				if(i==r)
					insert(id[i][j][k],T,inf),insert(T,id[i][j][k],0);
				if(i>d){
					if(j!=1)
						insert(id[i][j][k],id[i-d][j-1][k],inf),insert(id[i-d][j-1][k],id[i][j][k],0);
					if(j!=p)
						insert(id[i][j][k],id[i-d][j+1][k],inf),insert(id[i-d][j+1][k],id[i][j][k],0);
					if(k!=1)
						insert(id[i][j][k],id[i-d][j][k-1],inf),insert(id[i-d][j][k-1],id[i][j][k],0);
					if(k!=q)
						insert(id[i][j][k],id[i-d][j][k+1],inf),insert(id[i-d][j][k+1],id[i][j][k],0);
				}
			}
	while(bfs(S,T))
		ans+=dfs(S,inf);
	printf("%d",ans);
	return 0;
}
int K(gg());
int main(){;}

费用流

最小费用最大流

在保证最大流的基础上，使总费用最小
这类问题中每条边除了容量还有花费，建边时圆边为原本花费，反向边为花费的负数。每条边的花费为使用流量乘以单位流量的花费,所有边的花费就是总花费。
通过前面的最大流定理，我们知道只要不断地寻找增广路，就可以找到最大流。那么为了最小费用，我们只需在找增广路时，贪心找到单位流量费用最小的那条增广路即可。
证明：

  • 每次寻找的增广路的单位最小费用一定是不下降的。
  • 寻找增广路的过程中不会出现负环。
  • 局部最优一定是整体最优 
    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
    bool FIND(int st,int ed,int &fw,int &Cost){
    	memset(dis,0x3f,sizeof(dis));
    	memset(ins,false,sizeof(ins));
    	memset(pr,0,sizeof(pr));
    	inf = dis[0];
    	queue <int> q;
    	q.push(st), dis[st] = 0, a[st] = inf;
    	while(!q.empty()) {
    		int op = q.front(); q.pop();
    		ins[q] = false;
    		for(int i = headlist[q] ; i != -1 ; i = Edge[i].next) {
    			if(Edge[i].val&&dis[Edge[i].v]>dis[op]+Edge[i].cost) {
    				dis[sg[i].v] = dis[op]+Edge[i].cost;
    				pr[Edge[i].v] = i;
    				a[Edge[i].v] = MIN(a[op],Edge[i].val);
    				if(!ins[Edge[i].v]) {
    					ins[Edge[i].v] = true;
    					q.push(Edge[i].v);
    				}
    			}
    		}
    	}
    	if(dis[ed]==inf) return false;
    	fw += a[ed];
    	Cost += dis[ed]*a[ed];
    	int w = ed;
    	while(w!=st) {
    		Edge[pr[w]].val -= a[ed];
    		Edge[pr[w]^1].val += a[ed];
    		w = Edge[pr[w]].u;
    	}
    	return true;
    }

餐巾

传送门
题解：
首先，每天的餐巾分为两种情况，新买的和原来的。
每天作为一个点，由S向其连边，容量为Ri，花费为0。
每天可以向T连边，容量为INF，花费为p，每天都可以购买餐巾无数次。
将每天用过的餐巾在新建一层点，由于分配去快洗和慢洗的餐巾总数有限制，并非分别有限制，所有这两种无需再分开，这层点分别向T建边，容量为Ri，花费为0，限制总容量。
使用快洗的餐巾，由i向(i+m+N)’建边，容量为INF，花费为f，慢洗同理，花费分别建边。
但第i-m天洗完后的餐巾也可以供第i天以后使用。所以再由i向i+1建边，容量为INF，花费为0。这样第i天就能使用到以前所有可以使用的洗完的餐巾了。

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
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
struct edge{
	int e,n,flow,cost;
}a[20010];
int pre[410],tot;
inline void insert(int s,int e,int flow,int cost){
	a[tot].e=e;
	a[tot].flow=flow;
	a[tot].cost=cost;
	a[tot].n=pre[s];
	pre[s]=tot++;
}
int S(0),T;
int N,p,m,f,n,s;
int r[201];
int flow(0),ans(0),inf(0x7fffffff);
inline void build(){
	for(int i=1;i<=N;i++){
		insert(S,i,r[i],0),insert(i,S,0,0);
		insert(S,i+N,inf,p),insert(i+N,S,0,-p);
		insert(i+N,T,r[i],0),insert(T,i+N,0,0);
		if(i+m<=N)
			insert(i,i+m+N,inf,f),insert(i+m+N,i,0,-f);
		if(i+n<=N)
			insert(i,i+n+N,inf,s),insert(i+n+N,i,0,-s);
		if(i!=N)
			insert(i,i+1,inf,0),insert(i+1,i,0,0);
	}
}
int dis[410],fa[410],path[410];
inline bool bfs(){
	memset(dis,30,sizeof(dis));
	memset(fa,-1,sizeof(fa));
	queue<int>q;
	q.push(S);
	dis[S]=0;
	while(!q.empty()){
		int k(q.front());
		q.pop();
		for(int i=pre[k];i!=-1;i=a[i].n){
			int e(a[i].e);
			if(a[i].flow&&dis[e]>dis[k]+a[i].cost){
				dis[e]=dis[k]+a[i].cost;
				fa[e]=k;
				path[e]=i;
				q.push(e);
			}
		}
	}
	if(fa[T]==-1)
		return false;
	return true;
}
inline void dinic(){
	while(bfs()){
		int f(inf);
		for(int i=T;i!=S;i=fa[i])
			if(a[path[i]].flow<f)
				f=a[path[i]].flow;
		flow+=f;
		ans+=dis[T]*f;
		for(int i=T;i!=S;i=fa[i]){
			a[path[i]].flow-=f;
			a[path[i]^1].flow+=f;
		}
	}
}
inline int gg(){
	freopen("napkin.in","r",stdin);
	freopen("napkin.out","w",stdout);
	memset(pre,-1,sizeof(pre));
	scanf("%d",&N);
	T=(N<<1)+1;
	for(int i=1;i<=N;i++)
		scanf("%d",&r[i]);
	scanf("%d%d%d%d%d",&p,&m,&f,&n,&s);
	build();
	dinic();
	printf("%d",ans);
	return 0;
}
int K(gg());
int main(){;}

球队收益

传送门
题解：对于单独一支球队来说，假设其已经赢了n场，输了m场。当其再赢
一场时，增加的收益为Ci((n+1)^2-n^2)，即Ci(2n+1)，输了同理。且每
赢一场或输一场增加的收益都是递增的。所以我们可以直接统计每支球队接
下来要比赛的局数，并分别为赢了或输了第几场比赛建边，因为收益递增，
且求最小费用，所以，一定是按照赢或输的累积次数流的。
对于一场比赛来说，只有两种结果，所以要对其建一条容量为一的入边，并建两条容量为1的出边，分别指向两种结果。
但这样，对于其中一种结果，容量为一，不能分别流向两支球队去修改各自的收益。又不可增大原来决定结果的三条边的流量，因为这样会出现，流同时流向两种结果的情况，不合法。
所以，我们只修改获胜球队(或失败球队)的收益。最初，我们先将一个球队的总收益算成接下来都会输的结果，这样每赢一场增加的收益就是Ci×((n+1)^2-n^2)- Di×((m+1)^2-m^2)，问题就解决了。

剪刀石头布

传送门
题解：
此题和上一题的思路相同。
需要注意到的是，对于任意三个人来说只有两种情况。三个人形成一个环，题中所示。其中一个战胜了另外两个人，另两个人随便。
所以最后环的数目为，所有三个人的组合减去∑(i 1~n)c(f[i],2)，其中f[i]为第i个人战胜的人的数量。
这样对于i来说，赢第n个人，环总数就需要减去n-1.
所以仍需对赢第n个人建一条边。但输了的话不需要修改结果，所以无需将输赢结果合并，赢了直接修改。

总结？

其实上面这一圈全是Ctrl+c&Ctrl+v来的
如果我还能打出来这些题的话，我就粘代码= =
听得一脸茫然啊喂

彩蛋

据说dalao就是聪聪，那么聪聪是谁呢~
聪聪的世界
嘿嘿嘿~（话说这样会不会被打死QAQ）