网络流专题

最大流

问题:给你一幅网络图,每条边上有最大流量限制,问从源点s到汇点t的最大流量.

  • 增广路: 从源点s到汇点t的一条变权都为正的路径.
  • 反向弧: 用于纠正错误的寻找增广路的一种机制,也就是给一个后悔的机会.其实这个东西,有种偷梁换柱的感觉.

FF算法

Ford_Fulkerson算法(FF算法)就是基于这两个做的,不停的利用反向弧寻找增广路,复杂度$O(F\times E)$,F为最大流的流量,因为最坏情况下每次最大流量增加1,每次dfs寻找增广路复杂度为$O(E)$.

Dinic算法

  • 层次图: 就是从源点bfs,到节点u,距离为d[u],我们把d[u]叫做u的层次.
  • 阻塞流:多次增广后,层次图中不存在由s->t的路径.

算法由bfs求层次图,dfs求增广路组成.

引入层次图是防止盲目搜索,只做一次dfs,就求出这次层次图的所有增广路.

复杂度为$O(V^2 \times E)$

dinic

参考:

江南的博客

codevs1288 埃及分数问题 迭代加深

题目

给你一个真分数,问它最少能拆成几个单位分数的和,如果有多组解,选择最小分数最大的那组.

19/45=1/3 + 1/12 + 1/180

19/45=1/3 + 1/15 + 1/45

19/45=1/3 + 1/18 + 1/30,

19/45=1/4 + 1/6 + 1/180

19/45=1/5 + 1/6 + 1/18

所以最后答案为5,6,18.

题解

早就听说了IDA*,一直没学.

这个算是第一道IDA*题.

IDA*给我的感觉就是每次限制了搜索层数的dfs,先搜索第i层,如果没有解,那么就继续搜索第i+1层,这样一直做下去.这个的感觉有点像bfs,但是它省空间啊.

随着深度增加,搜索空间的大小指数增加,IDA*在递归深度限制的过程中虽然重复搜索了很多状态,但总的访问状态数和最后一次所访问的状态数还是同一数量级的.

IDA*适用于搜索树很大,但答案所在深度不深的题目

大体框架就是:

1
2
3
int  res=0;
while(dfs(0,0,res)==INF)res++;
printf("%d\n",res);

我们让分母值单调增加,对于这个题的一个减枝就是,如果使用cnt个单位分数让他们的值$\ge \frac{a}{b}$,那么 $\frac{cnt}{x} \geq \frac{a}{b}$

那么$x \leq \frac{cnt\times b}{a}$

代码

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
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long LL;
const LL INF=1e9+7;
int a,b,tot;
bool hasAns;
LL gcd(LL a,LL b){
	return b?gcd(b,a%b):a;
}
LL ans[100],res[100];
LL minFenmu;
void  dfs(int now,int dep,LL fenzi,LL fenmu,LL prev){//prev单调递增
	if(now>=dep)return ;
	LL limit=max(fenmu/fenzi,prev+1);
	for(LL i=limit;i<=ceil((double)fenmu*(dep-now)/fenzi);++i){
		if(i>minFenmu)return ;
		if(fenmu>i*fenzi)continue;
		else if(fenmu==i*fenzi){
			hasAns=true;
			ans[tot++]=i;
			if(i<res[tot-1]){
				for(int k=0;k<tot;++k){
					res[k]=ans[k];
				}
			}
			minFenmu=min(minFenmu,i);//已经得到的解的最小分母的值,用于剪枝
			--tot;
			return ;
		}else{
			LL aa=fenzi*i-fenmu;
			LL bb=fenmu*i;
			LL GCD=gcd(aa,bb);
			ans[tot++]=i;
			dfs(now+1,dep,aa/GCD,bb/GCD,i);
			tot--;//回溯
		}
	}
	return ;
}
int main(){
	scanf("%d%d",&a,&b);
	int k=1;
	hasAns=false;
	tot=0;
	minFenmu=INF;
	for(int i=0;i<100;++i)res[i]=INF;
	for(;;){
		dfs(0,k,a,b,0);
		if(hasAns){
			break;
		}
		k++;
	}
	for(int i=0;i<k;++i){
		printf("%lld ",res[i]);
	}
	printf("\n");
	return 0;
}

连通分量专题

在连通分量这一节中,主要包括:

无向图的割点和点双连通分量,桥和边双连通分量,有向图的强连通分量

其中,主要利用到的是两个数组:

low[u]:u以及他的后代所能回到的最小的dfn值.

dfn[u]:u点的访问时间.

无向图的割点和点双连通分量

割点定义: 如果删除一个点后,连通块数量增加,该点为割点.

判定条件: 如果一个点为割点,需要满足low[u]$\geq$dfn[v],而如果u为根节点需要满足他的儿子需要$child\geq$2.

代码: 割点

点双连通分量定义: 子图中任意两个点之间至少存在两条”点不重复“的路径.

判定条件:没写过

代码:没写过

无向图的桥和边双连通分量

桥的定义: 如果删除一条边后,连通块数量增加,该边为割边.

判定条件: v的后代只能连回v自己,既 $low[v]>dfn[u]$. 桥特别要注意重边,为了去重边,我们传边的编号.

代码: 桥

边双连通分量定义: 子图中任意两点之间至少存在两条”边不重复“的路径.

求解方法: 一个图中,把所有的桥去掉,每个连通分量对应着原图中的一个边双连通分量.

代码: 加最少的边,让整个图变成边双连通

hint

  • 边双连通分量常伴随着缩点,然后得到一树,树上每个节点都是一个边双连通分量,树上的每条边都是桥.
有向图的强连通分量

强连通分量的定义: 一个强连通分量内,任意两个点之间互相可达.

判定条件: 如果$low[u]==dfn[u]$,那么u点为该强连通分量的”根”

代码: 加最少的边让有向图强连通 注意特判连通分量为1的情况

hint

  • 对于一个有向图,我们都可以考虑一下缩点,因为缩点后是一棵有向树,对有向树操作,我们就可以很方便的求DAG上的最长路等等,树具有非常优美的性质,无向图也是同理.

HDOJ6180 Schedule 前缀和+瞎搞+输入挂

题目

给出个加工任务的开始时间和结束时间，问最少要用多少台机器可以完成这些任务，同一台机器上的任务时间不能有重叠，但允许守尾相接。对于每组用例，输出两个整数，分别表示最少用的机器台数和所有机器用的总时间。一台机器的用时为它最后的结束时间减它最开始启动的时间，中间不会停机。

$ T (1 <= T <= 100) , N (0 < N <= 100000,0<=s_i<e_i<=1e9)$

Sample Input

1
2
3
4
5
1
3
1 3//记住是左闭右开
4 6
2 5

Sample Output

1
2 8

分析

这个题第一问是很简单,就是最大重叠数,用前缀和就可以解决了.对于第二个问,我们只需要考虑在哪些地方一定需要增加一台机器,把这个时间记录下来,一共记为$\sum first_i$,同理从后往前,可以算出$\sum last_i$,两个相减就可以了.

然后这个题的$s_i,t_i$都很大,所有我们需要离散化一下,采用 sort+unique+unordered_map的方法

最后但也是最重要的,数据规模很大,需要采用读入挂,T到怀疑人生,以后注意,如果超过1e6个数就采用读入挂

代码

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<iostream>
#include<cstring>
#include<unordered_map>
#include<algorithm>
using namespace std;
const int MAXN=5e5+7;
const int BUF_SIZE=409600;
int sum[MAXN];
unordered_map<int,int>mp;
int l[MAXN],r[MAXN],a[MAXN];
int fp[MAXN];
struct {
    int cur, eof;
    char buf[BUF_SIZE];
    char next_char() {
        if (cur == BUF_SIZE) {
            if (eof) return -1;
            int bytes = fread(buf, 1, BUF_SIZE, stdin);
            if (bytes < BUF_SIZE) {
                memset(buf + bytes, -1, BUF_SIZE - bytes);
                buf[bytes] = -1;
                eof = 1;
            }
            cur = 0;
        }
        return buf[cur++];
    }
    int next_int() {
        int x = 0;
        char ch = next_char();
        while (ch < '0' || ch > '9') {
            if (ch == -1) return 0;
            ch = next_char();
        }
        while (ch >= '0' && ch <= '9') {
            x = x*10 + ch - '0';
            ch = next_char();
        }
        return x;
    }
} IO = {BUF_SIZE,};
int main(){
	int T=IO.next_int();
	while(T--){
		mp.clear();
		memset(sum,0,sizeof(sum));
		memset(fp,0,sizeof(fp));
		int N=IO.next_int();
		for(int i=0;i<N;++i){
			l[i]=IO.next_int();
			r[i]=IO.next_int();
			--r[i];
			a[i]=l[i];a[N+i]=r[i];
		}

		sort(a,a+2*N);//离散化
		int cnt=unique(a,a+2*N)-a;
		int tot=1;
		for(int i=0;i<cnt;++i){
			mp[a[i]]=tot;
			fp[tot]=a[i];
			++tot;
		}

		for(int i=0;i<N;++i){
			int x=l[i],y=r[i];
			++sum[mp[l[i]]];--sum[mp[r[i]]+1];
		}

		int ans=0;
		long long first=0,last=0;
		for(int i=1;i<=tot;++i){
			sum[i]+=sum[i-1];
			if(sum[i]>ans){
				first+=fp[i]*(sum[i]-ans);
				ans=sum[i];
			}
		}
		printf("%d ",ans);
		ans=0;
		for(int i=tot;i>=0;--i){
			if(sum[i]>ans){
				last+=(fp[i]+1)*(sum[i]-ans);//sum[i]-ans为突变的个数
				ans=sum[i];
			}
		}
		printf("%lld\n",last-first);
	}
	return 0;
}
|