Post 75

Veröffentlicht am | Edited on

https://www.cnblogs.com/victorique/p/8560656.html

强烈推荐

昨天看到这种建模方法懵逼，事实上只不过是我做的网络流的题太少了而已（一共就做了3道题吧。。。）

事实上最大权闭合子图对应一个最小割因此就对应着最大流。最大权闭合子图的权值等于所有正权点之和减去最小割。

. 最小割一定是简单割

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

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

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

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

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

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

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

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

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

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

所以W=所有正权点的权值之和-C(S,T)

由于所有正权点的权值之和是一个定值，那么割的容量越小，W也就越大。因此当C(S,T)取最小割时，W也就达到了最大权。

小Ho：我懂了，因为最小割也对应了一个闭合子图，因此它是可以被取得的，W也才能够到达最大权值。

小Hi：没错，这就是前面两条引理的作用。

小Ho：那么最小割的求解就还是用最大流来完成好了！

小Hi：嗯，那就交给你了。

看上去挺对的（网络流除非水平很高否则算法基本上都是感性理解吧）。

然后补充一道sb题。

[NOI2006]最大获利

题目描述

新的技术正冲击着手机通讯市场，对于各大运营商来说，这既是机遇，更是挑战。THU 集团旗下的 CS&T 通讯公司在新一代通讯技术血战的前夜，需要做太多的准备工作，仅就站址选择一项，就需要完成前期市场研究、站址勘测、最优化等项目。

在前期市场调查和站址勘测之后，公司得到了一共 N 个可以作为通讯信号中转站的地址，而由于这些地址的地理位置差异，在不同的地方建造通讯中转站需要投入的成本也是不一样的，所幸在前期调查之后这些都是已知数据：建立第 i个通讯中转站需要的成本为 P_iP**i （1≤i≤N）。

另外公司调查得出了所有期望中的用户群，一共 M 个。关于第 i 个用户群的信息概括为 A_iA**i , B_iB**i 和 C_iC**i ：这些用户会使用中转站 A i 和中转站 B i 进行通讯，公司可以获益 C_iC**i 。（1≤i≤M, 1≤A_iA**i , B_iB**i ≤N）

THU 集团的 CS&T 公司可以有选择的建立一些中转站（投入成本），为一些用户提供服务并获得收益（获益之和）。那么如何选择最终建立的中转站才能让公司的净获利最大呢？（净获利 = 获益之和 – 投入成本之和）

输入输出格式

输入格式：

输入文件中第一行有两个正整数 N 和 M 。

第二行中有 N 个整数描述每一个通讯中转站的建立成本，依次为 P_1 , P_2 , …,P_NP1,P2,…,P**N 。

以下 M 行，第(i + 2)行的三个数 A_i , B_iA**i,B**i 和 C_iC**i 描述第 i 个用户群的信息。

所有变量的含义可以参见题目描述。

输出格式：

你的程序只要向输出文件输出一个整数，表示公司可以得到的最大净获利。

输入输出样例

输入样例#1：

1
2
3
4
5
6
7
5 5
1 2 3 4 5
1 2 3
2 3 4
1 3 3
1 4 2
4 5 3

输出样例#1：

1
4

说明

样例：选择建立 1、2、3 号中转站，则需要投入成本 6，获利为 10，因此得到最大收益 4。

100%的数据中：$N≤5 000，M≤50 000，0≤C_i≤100，0≤P_i ≤100。$

题解

我们把每个人看成是一张图一条边（废话），每个站看成一张图的点。

然后求这张图的最大闭合子图即最小割即最大流。

答案就是总收益（这道题就是所有的用户收益）-最小割。

具体方法前面讲了。

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
// luogu-judger-enable-o2
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <queue>
#include <cstring>
#define maxn 100005
#define maxm 400005
#define INF 0x7ffffff
int hd[maxn] , ct = 1 , MaxFlow , n , m , dep[maxn] ,  s , t;
bool vs[maxn];
struct edge{
	int nxt , to , dis;
}e[maxm<<1];

inline void add(int x, int y , int d)
{
	e[++ct] = (edge){hd[x],y,d};
	hd[x] = ct;
}

inline bool bfs()
{
	for(int i = 1 ; i <= n + m + 1; ++i)	dep[i] = INF;
	dep[s] = 0;
	std::queue<int> q;
	q.push(s);
	for( ; q.size() ; q.pop())
	{
		int k = q.front();
		for(int i = hd[k] ; i ; i = e[i].nxt)
			if(dep[e[i].to] == INF && e[i].dis)	dep[e[i].to] = dep[k] + 1 , q.push(e[i].to);
	}
	return dep[t] != INF;
}

int dfs(int u , int cfw)
{
	if(u == t || !cfw) return cfw;
	int flow = 0 , f;
	for(int i = hd[u] ; i ; i = e[i].nxt)
	{
		int v = e[i].to;
		if(dep[v] == dep[u] + 1 && (f = dfs(v , std::min(cfw , e[i].dis))))
		{
			flow += f;
			cfw -= f;
			e[i].dis -= f , e[i^1].dis += f;
			if(!cfw) break;
		}
	}
	return flow;
}

inline int Dinic()
{
	int f;
	for( ; bfs() ; MaxFlow += dfs(s,INF));
	return MaxFlow;
}
int v[maxn] , sum;
inline void build()
{
	scanf("%d%d",&n,&m);
	s = 0 , t = n + m + 1;
	for(int i = 1 ; i <= n ; ++i)
		scanf("%d",&v[i]);
	for(int i = 1 ; i <= m ; ++i)
	{
		int x , y , c;
		scanf("%d%d%d",&x,&y,&c);
		sum += c;
		add(s , i , c) , add(i , s , 0);
		add(i , m + x , INF) , add(m + x , i , 0) , add(i , m + y , INF) , add(m + y , i , 0);
	//	printf("%d %d %d\n%d %d %d\n%d %d %d\n%d %d %d\n",i,m+x,INF,m + x , i , 0 , i , m + y , INF , m + y , i , 0);
	}
	for(int i = 1 ; i <= n ; ++i)
		add(i + m , t , v[i]) , add(t , i + m , 0);

}
int main()
{
	build();
	printf("%d\n",sum - Dinic());
}

[AHOI2009]最小割

题目描述

$A,B$两个国家正在交战，其中A国的物资运输网中有$N$个中转站，$M$条单向道路。设其中第$i (1≤i≤M)$条道路连接了$v_i,u_i$两个中转站，那么中转站$v_i$可以通过该道路到达$u_i$中转站，如果切断这条道路，需要代价$c_i$

现在B国想找出一个路径切断方案，使中转站$s$不能到达中转站$t$,并且切断路径的代价之和最小。

小可可一眼就看出，这是一个求最小割的问题。但爱思考的小可可并不局限于此。现在他对每条单向道路提出两个问题：

  • 问题一：是否存在一个最小代价路径切断方案，其中该道路被切断？
  • 问题二：是否对任何一个最小代价路径切断方案，都有该道路被切断？

现在请你回答这两个问题。

输入输出格式

输入格式：

第一行有44个正整数，依次为$N,M,s,t$

第22行到第(M+1)(M+1)行每行33个正整数$v,u,c$，表示vv中转站到uu中转站之间有单向道路相连，单向道路的起点是vv， 终点是$u$,切断它的代价是$c(1≤c≤100000)$

注意:两个中转站之间可能有多条道路直接相连。 同一行相邻两数之间可能有一个或多个空格。

输出格式：

对每条单向边，按输入顺序，依次输出一行，包含两个非00即11的整数，分别表示对问题一和问题二的回答(其中输出11表示是，输出00表示否)。 同一行相邻两数之间用一个空格隔开，每行开头和末尾没有多余空格。

输入输出样例

输入样例#1：

1
2
3
4
5
6
7
8
6 7 1 6
1 2 3
1 3 2
2 4 4
2 5 1
3 5 5
4 6 2
5 6 3

输出样例#1：

1
2
3
4
5
6
7
1 0
1 0
0 0
1 0
0 0
1 0
1 0

说明

设第(i+1)(i+1)行输入的边为ii号边，那么\{1,2\},\{6,7\},\{2,4,6\}{1,2},{6,7},{2,4,6}是仅有的三个最小代价切割方案。它们的并是\{1,2,4,6,7\}{1,2,4,6,7}，交是 \{\varnothing \}{∅} 。

测试数据规模如下表所示

数据编号 N M 数据编号 N M
1 10 50 6 1000 20000
2 20 200 7 1000 40000
3 200 2000 8 2000 50000
4 200 2000 9 3000 60000
5 1000 20000 10 4000 60000

题解

让你求最小割的可行边与必经边的板子。。。

04年就有这个题的明确解决方法了吧。。。

最小割的必经边求出任意最小割后肯定是满流。并且S能到一端点，另一端点能到T。必须边的另一种理解是扩大容量后能增大最大流的边

证明暂时略，具体求法就是从S开始DFS，T开始反向DFS，标记到达的点，然后枚举满流边。可以直接Tarjan求出SCC后判断S与一端点，T与另一端点是否在一个SCC中，满足即可

这道题的第二问就解决了。

最小割的可行边$E​$也必须是满流（否则这条边不是瓶颈，最小割应该是那条满流的边） ， 同时残余网络中$u​$到$v​$不应该存在路径，否则由于这条边$E​$是瓶颈，那么源点到它的端点和它的端点到汇点构成增广路。

第一问也解决了。

然后半天调不出来，数组不知道为什么非得开三倍，Dinic慢的可怕，Tarjan直接卡死。。。

调了半天调出数组开小。

然而还有一个蜜汁错误：我网络流加了一个优化：

1
2
3
4
5
6
7
8
9
10
for(int k ; (int)q.size() ; q.pop())
{
	k = q.front();
	for(int i = hd[k] ; i ; i = e[i].nxt)
	{
		int v = e[i].to;
		if(e[i].dis && dep[v] == INF) dep[v] = dep[k] + 1 , q.push(v);
///		if(v == T) return true;
	}
}

在这个分层中注释掉的那句话，就是最后的bug

我确实不知道为什么，凭直觉定位了那个错误注释了就AC了。。。

LOJ+BZOJDATA是好东西，大大提高做题的效率。

Code：

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <stack>
#include <queue>
#define maxn 4005
#define maxm 152005
const int INF = 0x3fffffff;
int hd[maxn] , idx , n , m , ct = 1 , tot , dfn[maxn] , low[maxn] , S , T , ecc[maxn];
struct edge{
    int nxt , to , dis;
}e[maxm<<1];

inline void add(int x,  int y , int c)
{
    e[++ct] = (edge){hd[x] , y , c};
    hd[x] = ct;
}
int fr[maxm] , to[maxm] , c[maxm] , dep[maxn];
inline void build()
{
    scanf("%d%d%d%d",&n,&m,&S,&T);
    for(int i = 1 ; i <= m ; ++i)
    {
        scanf("%d%d%d",&fr[i],&to[i],&c[i]);
        add(fr[i] , to[i] , c[i]) , add(to[i] , fr[i] , 0);
    }

}

struct stack{
    int p[maxn] , tp;
    stack(){
        tp = 0;
    }
    inline int size(){
        return tp;
    }
    inline int top(){
        return p[tp];
    }
    inline void push(int x){
        p[++tp] = x;
    }
    inline void pop(){
        p[tp--] = 0;
    }
}st;	
bool ins[maxn];
void Tarjan(int x)
{
    dfn[x] = low[x] = ++idx;
//	printf("%d %d %d\n",x,dfn[x],low[x]);
    st.push(x);
    ins[x] = true;
    for(int i = hd[x] ; i ; i = e[i].nxt)
    {
        if(!e[i].dis) continue;
        int v = e[i].to;
        if(!dfn[v])
        {
            Tarjan(v);
            low[x] = std::min(low[x] , low[v]);
        }
        else if(ins[v]) low[x] = std::min(low[x] , dfn[v]);
    }
    if(dfn[x] == low[x])
    {
        ++tot;
        while(st.top() != x)
        {
            ecc[st.top()] = tot;
            ins[st.top()] = false;
            st.pop();
        }
        ecc[st.top()] = tot , ins[st.top()] = false , st.pop();
    }
}

int s[2][maxm];
inline void solve()
{
    for(int i = 1; i <= n ; ++i) 
        if(!dfn[i]) Tarjan(i);
//	puts("OK");
//	puts("FINISH TARJNA");
//	puts("DEBUG");
//	for(int i = 1 ; i <= n ; ++i)
//		printf("%d ",ecc[i]);
//	return;
    for(int i = 2 ; i <= ct ; i += 2)
    {
        if(i & 1) continue;
        if(!e[i].dis && ecc[fr[i >> 1]] != ecc[to[i >> 1]])
            s[0][i >> 1] = 1;
    }	
    for(int i = 2 ; i <= ct ; i += 2)
    {
        if(i & 1) continue;
        if(!e[i].dis && ecc[fr[i >> 1]] == ecc[S] && ecc[to[i >> 1]] == ecc[T])
            s[1][i >> 1] = 1;
    }
    for(int i = 1 ; i <= m ; ++i)
        printf("%d %d\n",s[0][i] , s[1][i]);
}

inline bool bfs()
{
    for(int i = 0 ; i <= n ; ++i) dep[i] = INF;
    std::queue<int> q;
    q.push(S);
    dep[S] = 0;
    for(int k ; (int)q.size() ; q.pop())
    {
        k = q.front();
        for(int i = hd[k] ; i ; i = e[i].nxt)
        {
            int v = e[i].to;
            if(e[i].dis && dep[v] == INF) dep[v] = dep[k] + 1 , q.push(v);
        //	if(v == T) break;
        }
    }
 	if(dep[T] == INF) return false;
    else return true;

}

int dfs(int u , int cfw)
{
    if(u == T || !cfw) return cfw;
    int flow = 0 , f;
    for(int i = hd[u] ; i ; i = e[i].nxt)
    {
        int v = e[i].to;
        if(e[i].dis && dep[v] == dep[u] + 1 && (f = dfs(v , std::min(cfw , e[i].dis))))
        {
            e[i].dis -= f , e[i ^ 1].dis += f;
            flow += f , cfw -= f;
            if(!cfw) break;
        }
    }
//	if(!flow) dep[u] = -1;
    return flow;
}

void dinic(){
    for( ; bfs() ; dfs(S , INF));
}
int main()
{
//	freopen("2.in","r",stdin);
//	freopen("my.out","w",stdout);
    build();
    dinic();
    solve();
}

最长不下降子序列

1
2
for(1...n)
f[std::upper_bound(f+1,f+ans+1,a[i])-f]=a[i];

最长不上升子序列

1
2
3
f[1]=a[1],ans=1;
for(2...n)
f[std::upper_bound(f+1,f+ans+1,a[i],std::greater<int>())-f]=a[i];

最长上升子序列

1
2
for(1...n)
f[std::lower_bound(f+1,f+ans+1,a[i])-f]=a[i];

最长下降子序列

1
2
3
f[1]=a[1],ans=1;
for(2...n)
f[std::lower_bound(f+1,f+ans+1,a[i],std::greater<int>())-f]=a[i];

只有这点东西是因为我去补多项式笔记和做了个睿智的校内测试。

说是关于推荐名额的考试。

然后发了一个两道题的文档，3个小时？第一道傻逼模拟全场切，第二道是暴力AC玄学题。

然后我发现我为了优化搜无序点对然后乘$2^{k-1}$错了。

所以那些有爆搜分的就比我高了。

所以可以安心滚粗了嘻嘻嘻。

睿智测试。