—— Summon, Light!
0%

HHUACM 专题训练 最短最长路

发表于 更新于 Valine：

A HDOJ-2544
模板题。不解释了。
顺便学习了一下dij+优先队列的姿势。
【感觉代码量跟普通dij很接近啊。。。
每个点入队一次，复杂度 O(NlogN)

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

typedef pair<int,int> pii;

const int N=101;
const int M=10001*2;
const int INF=1<<29;
struct edge
{
	int go,next,val;
};
edge eg[M];
int last[N],done[N],d[N],pre[N];
int tot;

void add(int x,int y,int z)
{
	eg[++tot].go=y;
	eg[tot].val=z;
	eg[tot].next=last[x];
	last[x]=tot;
}

int main()
{
	int n,m,i,x,y,z;
	while (scanf("%d%d",&n,&m),n)
	{
		tot=0;
		memset(last,0,sizeof(last));
		for (i=1;i<=m;i++)
		{
			scanf("%d%d%d",&x,&y,&z);
			add(x,y,z);
			add(y,x,z);
		}
		priority_queue<pii,vector<pii>,greater<pii> > q;
		for (i=1;i<=n;i++) d[i]=INF;
		memset(done,0,sizeof(done));
		memset(pre,0,sizeof(pre));
		d[1]=0;pre[1]=1;
		q.push(make_pair(0,1));
		while (!q.empty())
		{
			pii u=q.top();
			q.pop();
			int v=u.second;
			if (done[v]) continue;
			done[v]=1;
			for (i=last[v];i;i=eg[i].next)
			{
				int x=eg[i].go;
				if (d[x]>d[v]+eg[i].val)
				{
					d[x]=d[v]+eg[i].val;
					pre[x]=v;
					q.push(make_pair(d[x],x));
				}
			}
		}
		printf("%d\n",d[n]);
	}
	return 0;
}

B POJ-1860
我放的时候以为是个大水题
其实也就是个类似判正环的。。。
（赋初值为0的话就保证了每次操作不出现负数）
主要是没想到 Bellman-Ford 然后其他的又写不太清楚。。。
后来查了一下还是写 Bellman-Ford 比较简洁：O(NM)

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

const int N=101;
const int M=101*2;
const int INF=1<<29;
struct edge
{
	int st,ed;
	double c,r;
};
edge eg[M];
double d[N];
int n,m,tot;

void add(int x,int y,double r,double c)
{
	eg[++tot].st=x;
	eg[tot].ed=y;
	eg[tot].r=r;
	eg[tot].c=c;
}

bool Bellman_Ford(int s,double val)
{
	int i,j;
	for (i=1;i<=n;i++) d[i]=0;
	d[s]=val;
	for (i=1;i<n;i++)
	{
		int f=0;
		for (j=1;j<=tot;j++)
		{
			int u=eg[j].st,v=eg[j].ed;
			if (d[v]<(d[u]-eg[j].c)*eg[j].r)
			{
				f=1;
				d[v]=(d[u]-eg[j].c)*eg[j].r;
			}
		}
		if (f==0) break;
	}
	if (d[s]>val) return true;
	for (j=1;j<=tot;j++)
	{
		int u=eg[j].st,v=eg[j].ed;
		if (d[v]<(d[u]-eg[j].c)*eg[j].r)
			return true;
	}
	return false;
}

int main()
{
	int i,x,y,s;
	double val,r,c;
	scanf("%d%d%d%lf",&n,&m,&s,&val);
	tot=0;
	for (i=1;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		scanf("%lf%lf",&r,&c);
		add(x,y,r,c);
		scanf("%lf%lf",&r,&c);
		add(y,x,r,c);
	}
	if (Bellman_Ford(s,val)) puts("YES");
	else puts("NO");
	return 0;
}

C HDOJ-4514
我竟然会有一天因为读入忘记加 !=EOF TLE七次

看了看网上的题解 基本都是并查集+DP。
其实没有必要。。。
无向图判环最基本的方法就是DFS。。。
其次 不成环的话就是森林
每棵树用两次BFS求直径的方法
也就是说这题是DFS+BFS。。。
这样就完全不会有空间的问题
不过我也不知道出题人的本意是哪个。。。
判环时每个点遍历一次，求长度时每个点遍历两次，复杂度 O(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
94
95
96
97
98
99
100
#include <iostream>
#include <cstdio>
#include <cstring>

const int N=100001;
const int M=1000001*2;
const int INF=1<<29;
struct edge
{
	int go,next,val;
};
edge eg[M];
int last[N],vis[N],d[N],q[N];
int tot;

void add(int x,int y,int z)
{
	eg[++tot].go=y;
	eg[tot].val=z;
	eg[tot].next=last[x];
	last[x]=tot;
}

bool circle(int u,int pre)
{
	int i,ans=0;
	vis[u]=1;
	for (i=last[u];i!=-1;i=eg[i].next)
	{
		if ((i^pre)!=1)
		{
			if (vis[eg[i].go]) return 1;
			ans|=circle(eg[i].go,i);
			if (ans==1) return 1;
		}
	}
	return ans;
}

void bfs(int s)
{
	int l=0,r=1,i;
	q[1]=s;	d[s]=0;
	while (l<r)
	{
		int u=q[++l];
		for (i=last[u];i!=-1;i=eg[i].next)
		{
			int v=eg[i].go;
			if (d[v]==-1)
			{
				q[++r]=v;
				d[v]=eg[i].val+d[u];
			}
		}
	}
}

int main()
{
	int n,m,i,j,x,y,z;
	while (scanf("%d%d",&n,&m)!=EOF)
	{
		tot=-1;
		for (i=1;i<=n;i++) last[i]=-1;
		for (i=1;i<=m;i++)
		{
			scanf("%d%d%d",&x,&y,&z);
			add(x,y,z);
			add(y,x,z);
		}
		memset(vis,0,sizeof(vis));
		for (i=1;i<=n;i++)
			if (!vis[i])
				if (circle(i,-1)) break;
		if (i<=n) puts("YES");
		else 
		{
			int ans=-1,p;
			memset(vis,0,sizeof(vis));
			for (j=1;j<=n;j++)
				if (!vis[j])
				{
					for (i=1;i<=n;i++) d[i]=-1;
					bfs(j); p=1;
					for (i=1;i<=n;i++)
						if (d[i]>d[p]) p=i;
					for (i=1;i<=n;i++) d[i]=-1;
					bfs(p); p=1;
					for (i=1;i<=n;i++)
						if (d[i]!=-1) vis[i]=1;
					for (i=1;i<=n;i++)
						if (d[i]>d[p]) p=i;
					if (d[p]>ans) ans=d[p];
				}
			printf("%d\n",ans);
		}
	}
	return 0;
}

D HDOJ-2196
【准确的说跟上一题知识点有重叠。。。
很明显题目里给的是一棵树
可以证明，到 u 最远距离的 v 一定是直径的一端。
假设有 v’ 使得 u-v’ 距离更长，
1、u 在直径上：记直径另一端为 s ，显然有 s->u->v’ 比 s->u->v 长，这与 v 为直径一端矛盾。
2、u 不在直径上：记直径另一端为 s ，
以 u 为根，v’ 不能在 u->s 和 u->v 上。
则 (u->v’) + (u->s) 大于 (u->v) + (u->s) 大于等于 (v->s) ，矛盾。

于是只需要求直径两端到各个点的距离。
每个点被遍历三次，复杂度 O(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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N=10001;
const int M=10001*2;
const int INF=1<<29;
struct edge
{
	int go,next,val;
};
edge eg[M];
int last[N],d[N],d2[N],q[N];
int tot;

void add(int x,int y,int z)
{
	eg[++tot].go=y;
	eg[tot].val=z;
	eg[tot].next=last[x];
	last[x]=tot;
}

void bfs(int s,int* d)
{
	int l=0,r=1,i;
	q[1]=s;	d[s]=0;
	while (l<r)
	{
		int u=q[++l];
		for (i=last[u];i!=-1;i=eg[i].next)
		{
			int v=eg[i].go;
			if (d[v]==-1)
			{
				q[++r]=v;
				d[v]=eg[i].val+d[u];
			}
		}
	}
}

int main()
{
	int n,i,p,y,z;
	while (scanf("%d",&n)!=EOF)
	{
		tot=-1;
		for (i=1;i<=n;i++) last[i]=-1;
		for (i=2;i<=n;i++)
		{
			scanf("%d%d",&y,&z);
			add(i,y,z);
			add(y,i,z);
		}
		for (i=1;i<=n;i++) d[i]=-1;
		bfs(1,d);
		for (p=1,i=1;i<=n;i++)
			if (d[i]>d[p]) p=i;
		for (i=1;i<=n;i++) d[i]=-1;
		bfs(p,d);
		for (p=1,i=1;i<=n;i++)
			if (d[i]>d[p]) p=i;
		for (i=1;i<=n;i++) d2[i]=-1;
		bfs(p,d2);
		for (i=1;i<=n;i++)
			printf("%d\n",max(d[i],d2[i]));
	}
	return 0;
}

E HDOJ-4885
题意就是平面上有好多加油站
一个人要从学校回家
这个人有一辆满油的摩托车
跑到 L 距离时会用完油
在加油站加油每次都要加满
而且每次加油之前走的都是直线

模型也不难。
就是距离小于等于 L 的可以连边，然后丢进第一题的模板里跑。
唯一蛋疼的就是必须走“直线”，也就是可能被强迫加油。。。
于是我就不会了。。。但是听说 N^3 能过。。。
然后我试了几种：
1、加边的时候数一下到底穿过几个点。。。
2、n-1 个点里面同向的点只加最近的。
3、先保存一下距离满足条件的，再在这里面同向只加最近的。
1 过不了。。。2 估计我写挂了。。。3 62MS。。。
最差情况复杂度 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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

typedef pair<int,int> pii;

const int N=1010;
const int M=1006100*2;
const int INF=1<<29;
struct edge
{
	int go,next,val;
};
edge eg[M];
struct point
{
	int x,y;
};
point sta[N];
int last[N],d[N],vp[N];
long long vali[N];
bool done[N];
int tot;

long long sqr(long long x)
{
	return x*x;
}

void add(int x,int y,int z)
{
	eg[++tot].go=y;
	eg[tot].val=z;
	eg[tot].next=last[x];
	last[x]=tot;
}

bool cmp(int i,int j)
{
	return vali[i]>vali[j];
}

int main()
{
	int T,n,l,i,j,k;
	scanf("%d",&T);
	while (T--)
	{
		scanf("%d%d",&n,&l); n+=2; tot=0;
		memset(last,0,sizeof(last));
		scanf("%d%d",&sta[1].x,&sta[1].y);
		scanf("%d%d",&sta[2].x,&sta[2].y);
		for (i=3;i<=n;i++)
			scanf("%d%d",&sta[i].x,&sta[i].y);
		for (i=1;i<=n;i++)
		{
			int tmp=0,z;
			for (j=i+1;j<=n;j++)
			{
				vali[j]=sqr(sta[j].x-sta[i].x)+sqr(sta[j].y-sta[i].y);
				if (vali[j]>sqr(l)) vali[j]=-1;
				else vp[++tmp]=j;
			}
			sort(vp+1,vp+1+tmp,cmp);
			for (j=1;j<=tmp;j++)
			{
				for (k=j+1;k<=tmp;k++)
					if (1LL*(sta[vp[k]].x-sta[i].x)*(sta[vp[j]].y-sta[i].y)
						==1LL*(sta[vp[j]].x-sta[i].x)*(sta[vp[k]].y-sta[i].y)
						&&((1LL*(sta[vp[k]].x-sta[i].x)*(sta[vp[j]].x-sta[i].x)>0)
						||(1LL*(sta[vp[k]].y-sta[i].y)*(sta[vp[j]].y-sta[i].y)>0)))
						{
							vali[vp[j]]=-1;
							break;
						}
				if (vali[vp[j]]!=-1) add(i,vp[j],1),add(vp[j],i,1);
			}
		}
		priority_queue<pii,vector<pii>,greater<pii> > q;
		for (i=1;i<=n;i++) d[i]=INF;
		memset(done,0,sizeof(done));
		d[1]=0;
		q.push(make_pair(0,1));
		while (!q.empty())
		{
			pii u=q.top();
			q.pop();
			int v=u.second;
			if (done[v]) continue;
			done[v]=1;
			for (i=last[v];i;i=eg[i].next)
			{
				int x=eg[i].go;
				if (d[x]>d[v]+eg[i].val)
				{
					d[x]=d[v]+eg[i].val;
					q.push(make_pair(d[x],x));
				}
			}
		}
		if (d[2]==INF) puts("impossible");
		else printf("%d\n",d[2]-1);
	}
}
咖啡，亦我所需也