图论中的二分

发表于 | 分类于 | 阅读次数:

图论中最基础的算法是最短路，然而近些年在竞赛中已很少考最短路问题，许多图论题目往往是要求一种十分诡异的东西，这时候我们想直接求是不现实的，二分答案就应运而生了。
##小奇回地球(earth)

题目背景

开学了，小奇在回地球的路上，遇到了一个棘手的问题。

问题描述

简单来说，它要从标号为 1 的星球到标号为 n 的星球，某一些星球之间有航线。由于超时空隧道的存在，从一个星球到另一个星球时间可能会倒流，而且，从星球 a 到 b 耗费的时间和星球 b 到 a 耗费的时间不一定相同。

宇宙法规定：“禁止在出发时间前到达目的地。”每艘飞船上都有速度调节装置，可以调节飞行的时间。其功能可以使得整次航程中所有两星球间的飞行时间增加或减少相同的整数值。你的任务是帮助它调整速度调节器，找出一条最短时间到达目的地的路径。

输入格式

输入文件包含多组数据，第 1 个数为 T，表示数据组数。

对于每组数据，输入第 1 行为两个正整数 n，m，为星球的个数和星球间的路线数。接下来 m 行，每行三个整数 i，j 和 t，表示由星球 i 到星球 j 飞行的时间为 t。由 i 到 j 最多只会有一条飞行线路。

输出格式

输出文件共 T 行，每组数据输出一行。

如果可以通过调节速度调节器完成任务，则输出一个非负整数，表示由星球 1 到星球 n 的最短时间。（注意最短时间要大于或者等于 0）。

如果不能由星球 1 到达星球 n，则输出-1。

样例输入

1
4 5
1 2 1
1 3 1
2 3 -3
3 1 1
3 4 1

样例输出

2

样例解释

把速度控制器的值设为 1,相当于每个时间值加 1,得到的最短路径为 1→2→3→4,所需时间为 2+(-2)+2=2。

数据范围

1，2 号测试点，保证所有星球出度不超过 1
3，4 号测试点， $n\leq10$
5，6 号测试点， $-100\leq t\leq 100$ 对于 $100%$ 的数据 $T\leq10，n\leq100，m\leq n*(n-1)，-100000\leq t\leq100000$
数据随机和构造结合生成

这道题的题意是关键，首先应该明确两个重要结论：

  • 若存在与起点终点都联通的负环，则不存在最短路
  • 若最短路权值为负数，则不符合宇宙法

易证：是否同时符合以上两个条件关于速度调节器的设定数值的函数具有单调性，故可以用二分法求出速度调节器的设定数值的最小值，且此时最短路即为所求

需要注意手写循环队列别开小了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int MAXN=100,MAXM=MAXN*(MAXN-1),INF=0x7fffffff;

int head[MAXN+1],ecnt;
struct node{int next,to,value;} e[MAXM+1];
void add(int x,int y,int z)
{
	ecnt++;
	e[ecnt].to=y;
	e[ecnt].next=head[x];
	head[x]=ecnt;
	e[ecnt].value=z;
}

bool vis[MAXN+1],lt[MAXN+1];
void dfs(int x)
{
	vis[x]=true;
	for(int tmp=head[x];tmp;tmp=e[tmp].next)
		if(!vis[e[tmp].to]) 
			dfs(e[tmp].to);
}
bool in[MAXN+1];
int dis[MAXN+1];
bool dfs_spfa(int x,int ad)
{
	in[x]=true;
	for(int tmp=head[x];tmp;tmp=e[tmp].next)
	{
		int y=e[tmp].to;
		if(dis[y]>dis[x]+e[tmp].value+ad && lt[y])
		{
			if(in[y]) return true;
			dis[y]=dis[x]+e[tmp].value+ad;
			if(dfs_spfa(y,ad)) return true;	
		}
	}
	in[x]=false;
	return false;
}
int queue[10*MAXN+5];
int n,m;
void bfs_spfa(int ad)
{
	memset(queue,0,sizeof(queue));
	memset(in,false,sizeof(in));
	memset(dis,63,sizeof(dis));
	dis[1]=0;
	in[1]=true;
	int h=0,t=1;
	queue[t]=1;
	while(h<t)
	{
		h=(h+1)%(10*MAXN+5);
		int x=queue[h];
		in[x]=false;
		for(int tmp=head[x];tmp;tmp=e[tmp].next)
		{
			int y=e[tmp].to;
			if(dis[y]>dis[x]+e[tmp].value+ad&&lt[y])
			{
				dis[y]=dis[x]+e[tmp].value+ad;
				if(!in[y])
				{
					in[y]=true;
					t=(t+1)%(10*MAXN+5);
					queue[t]=y;
				}
			}
		}
	}
}
int T;
bool check(int ad)
{
	int i;
	for(i=1;i<=n;i++)
		if(lt[i])
		{
			memset(dis,0,sizeof(dis));
			memset(in,0,sizeof(in));
			if(dfs_spfa(i,ad)) return 0;
		}
	bfs_spfa(ad);
	if(dis[n]>=0&&dis[n]<=(int)1e9) return 1;
	return 0;
}
int main()
{
	freopen("earth.in","r",stdin);
	freopen("earth.out","w",stdout);
	int i;
	scanf("%d",&T);
	while(T--)
	{
		ecnt=0;
		memset(head,0,sizeof(head)); 
		scanf("%d%d",&n,&m);
		for(i=1;i<=m;i++)
		{
			int u,v,w;
			scanf("%d%d%d",&u,&v,&w);
			add(u,v,w);
		}
		//读边
		bool selt;//起点终点是否连通
		memset(vis,false,sizeof(vis));
		dfs(1);
		memset(lt,false,sizeof(lt));
		for(i=1;i<=n;i++)
			if(vis[i]) lt[i]=true;
		if(lt[n]) selt=true;
		for(i=1;i<=n;i++)
			if(vis[i])
			{
				memset(vis,false,sizeof(vis));
				dfs(i);
				if(!vis[n]) lt[i]=false;
			}
		//前面两次循环遍历所有点，lt[i]表示点是否与起点终点都联通
		int l=-100000,r=100000,ans=-1;
		while(l<r)
		{
			int mid=(l+r)>>1;
			if(check(mid)) ans=dis[n],r=mid;
			else l=mid+1;
		}
		if(!selt) cout<<-1<<endl;
		else cout<<ans<<endl;
	}
	return 0;
}

##小澳的葫芦

题目描述

小澳最喜欢的歌曲就是《葫芦娃》。一日表演唱歌，他尽了洪荒之力，唱响心中圣歌。随之，小澳进入了葫芦世界。葫芦世界有 n 个葫芦，标号为 1~ n。n 个葫芦由 m 条藤连接，每条藤连接了两个葫芦，这些藤构成了一张有向无环图。小澳爬过每条藤都会消耗一定的能量。小澳站在 1 号葫芦上（你可以认为葫芦非常大，可以承受小澳的体重），他想沿着藤爬到 n 号葫芦上，其中每个葫芦只经过一次。

小澳找到一条路径，使得消耗的能量与经过的葫芦数的比值最小。

输入格式

输入文件名为 calabash.in。

输入文件第一行两个正整数 n,m，分别表示葫芦的个数和藤数。

接下来 m 行，每行三个正整数 u,v,w，描述一条藤，表示这条藤由 u 连向 v，小澳爬过这条藤需要消耗 w 点能量。

输出格式

输出文件名为 calabash.out。

一行一个实数，表示答案（误差不超过 10^-3）。

输入输出样例
calabash.in

4 6
1 2 1
2 4 6
1 3 2
3 4 4
2 3 3
1 4 8

calabash.out

2.000

输入输出样例说明

有 4 种爬法：

1->4，消耗能量 8，经过 2 个葫芦，比值为 8/2=4。
1->2->4，消耗能量 1+6=7，经过 3 个葫芦，比值为 7/3≈2.33。
1->3->4，消耗能量 2+4=6，经过 3 个葫芦，比值为 6/3=2。
1->2->3->4，消耗能量 1+3+4=8，经过 4 个葫芦，比值为 8/4=2。

所以选第三种或第四种方案，答案为 2。

数据规模与约定

测试点编号 n m 特殊说明
1 2 1
2 100 99 除 1 外，所有葫芦的入度均为 1
3 100 105 所有从 1 到 n 的路径经过的葫芦数相等
4 100 1000
5 100 1000
6 199 198 除 1 外，所有葫芦的入度均为 1
7 200 231 所有从 1 到 n 的路径经过的葫芦数相等
8 200 2000
9 200 2000
10 200 2000

对于所有数据，小澳爬过每条藤消耗的能量不会超过 10^3，且一定存在一条从 1到 n 的路径。

本题是最小比例生成树的经典例题，其实所谓的最小比例生成树与上一道题很像。

那道题是给一个图求给每一条边加上一个权值x使其最短路>=0且最小，方法就是二分x，每次求一次最短路，不过需要判负环和起点终点不连通的情况。

可是这道题如何用那道题的思路呢？

可以假设答案为x，则对于任意一条由k条边组成的路径：
$(w_1+w_2+…+w_k)/k>=x$
化简：$(w_1+w_2+…+w_k)>=kx$
再化简：$(w_1-x)+(w_2-x)+…+(w_k-x)>=0$

这样就很明显了，只需要二分x，求出满足上式的最小x值即可

代码与 那道题相似，不贴了

##W的火星工程 wproject

其实是比较简单的一道题，只是忘记了 Dijkstra 不能处理负边权图，暴力 60。
本题暴力搜索加上剪枝后还是比较有效的，若要写出正解的话，我们应该考虑到本题中要求的是所走路径中 $\frac{\sum a}{\sum b}$ 的值，对于这么诡异的一个东西，我们考虑二分答案。
二分答案的灵魂在于判断一个确定答案的可行性。
设要判断的答案为 k ，那么当满足 $\frac{\sum a}{\sum b}\leq k$ 时， k 为可行答案。
我们将原式进行简单的变换，可得： $\sum a-k\sum b\leq0$ ，这样，我们可以将每条边的边权赋为 $a-kb$ ，之后再用 SPFA 求最短路，若最短路满足 $dis[n+1]\leq0$ 则说明答案可行。
由此我们可以求解出答案。

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
#include <cstdio>
#include <queue>
using namespace std;

const int MAXE=100005,MAXV=10005;
const double eps=1e-9,INF=1e7;
int n,m;
double dis[MAXV];

queue<int> que;

struct E{int next,to;double a,b;} e[MAXE];int ecnt,G[MAXV]; 

inline void add(int u,int v,double a,double b)
{e[++ecnt]=(E){G[u],v,a,b};G[u]=ecnt;}

bool spfa(double k)
{
	for(int i=1;i<=n+1;++i)
		dis[i]=INF;
	que.push(0);
	while(!que.empty())
	{
		int u=que.front();que.pop();
		for(int i=G[u];i;i=e[i].next)
		{
			int v=e[i].to;
			double w=e[i].a-k*e[i].b;
			if(dis[v]>dis[u]+w)
			{
				dis[v]=dis[u]+w;
				que.push(v);
			}
		}
	}
	return dis[n+1]<eps;
}

int main()
{
	freopen("wproject.in","r",stdin);
	freopen("wproject.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i)
	{
		int x,y;double a,b;
		scanf("%d%d%lf%lf",&x,&y,&a,&b);
		add(x,y,a,b);
	}
	double l=0,r=INF;
	while(r-l>eps)
	{
		double mid=(l+r)/2;
		if(spfa(mid))
			r=mid;
		else l=mid;
	}
	printf("%.6lf",l);
	return 0;
}
1
2