15.10.11【最小生成树+lca、差分约束、bfs】

OI&ACM, OI训练
  1. 1 星际导航 (nav)
  2. 2 银河(gin)
  3. 3 选举预测(ele)

100+20+40

1 星际导航 (nav)

【题目描述】
sideman做好了回到Gliese 星球的硬件准备，但是sideman的导航系统还没有完全设计好。为了方便起见，我们可以认为宇宙是一张有N 个顶点和M 条边的带权无向图，顶点表示各个星系，两个星系之间有边就表示两个星系之间可以直航，而边权则是航行的危险程度。
sideman 现在想把危险程度降到最小，具体地来说，就是对于若干个询问(A, B)，sideman 想知道从顶点A 航行到顶点B 所经过的最危险的边的危险程度值最小可能是多少。作为sideman 的同学，你们要帮助sideman 返回家园，兼享受安全美妙的宇宙航行。所以这个任务就交给你了。
【输入格式】
第一行包含两个正整数N 和M，表示点数和边数。
之后 M 行，每行三个整数A，B 和L，表示顶点A 和B 之间有一条边长为L 的边。顶点从1 开始标号。
下面一行包含一个正整数 Q，表示询问的数目。
之后 Q 行，每行两个整数A 和B，表示询问A 和B 之间最危险的边危险程度的可能最小值。
【输出格式】
对于每个询问， 在单独的一行内输出结果。如果两个顶点之间不可达， 输出impossible。

写了第三遍了 O__O"…
先求最小生成树
然后lca+倍增
如果只求lca然后暴力的话好像80

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
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<vector>
#include<cmath>
using namespace std;
int n,m,x,y,z,v,f1,f2,k,Q,ans;
int fat[100001],dep[100001],g[100001][20],fa[100001][20];
vector<int> to[100001],cost[100001];
struct node{
	int x,y,v;
}a[300001];
int mycomp(const node &a,const node &b)
{
	return a.v<b.v;
}
int father(int x)
{
	if(fat[x]==x) return x;
	return fat[x]=father(fat[x]);
}
void dfs(int x)
{
	for(int i=0;i<to[x].size();i++)
	{
		int y=to[x][i];
		if(fa[x][0]==y) continue;
		fa[y][0]=x; dep[y]=dep[x]+1; g[y][0]=cost[x][i];
		dfs(y);
	}
}
int lca(int x,int y)
{
	int ans=0;
	if(dep[x]<dep[y]) z=x,x=y,y=z;
	for(int i=log(n)/log(2);i>=0;i--)
	  if(dep[fa[x][i]]>=dep[y]) 
	    ans=max(ans,g[x][i]),x=fa[x][i];
	if(x==y) return ans;
	for(int i=log(n)/log(2);i>=0;i--)
	  if(fa[x][i]!=fa[y][i])
		ans=max(ans,g[x][i]),ans=max(ans,g[y][i]),
		x=fa[x][i],y=fa[y][i];
	ans=max(ans,g[x][0]);ans=max(ans,g[y][0]);
	return ans;
}
int main()
{
	freopen("nav.in","r",stdin);
	freopen("nav.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) fat[i]=i;
	for(int i=1;i<=m;i++)
		scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].v);
	sort(a+1,a+m+1,mycomp);
	for(int i=1;i<=m;i++)
	{
		x=a[i].x;y=a[i].y;v=a[i].v;
		f1=father(x);f2=father(y);
		if(f1==f2) continue;
		fat[f1]=f2;
		to[x].push_back(y);cost[x].push_back(v);
		to[y].push_back(x);cost[y].push_back(v);
		if(++k==n-1) break;
	}
	for(int i=1;i<=n;i++)
	  if(!fa[i][0]) 
	    dep[i]=1,dfs(i);
	for(int i=1;i<=log(n)/log(2)+1;i++)
	  for(int j=1;j<=n;j++)
	  fa[j][i]=fa[fa[j][i-1]][i-1],
	  g[j][i]=max(g[j][i-1],g[fa[j][i-1]][i-1]);
	scanf("%d",&Q);
	for(int i=1;i<=Q;i++)
	{
		scanf("%d%d",&x,&y);
		if(father(x)!=father(y)) printf("impossible\n");
		else printf("%d\n",lca(x,y));
	}
	fclose(stdin);fclose(stdout);
}

2 银河(gin)

【题目描述】
银河中的恒星浩如烟海，但是我们只关注那些最亮的恒星。我们用一个正整数来表示恒星的亮度，数值越大则恒星就越亮，恒星的亮度最暗是1。现在对于N 颗我们关注的恒星，有M 对亮度之间的相对关系已经判明。你的任务就是求出这N 颗恒星的亮度值总和至少有多大。
【输入格式】
第一行给出两个整数N 和M。
之后 M 行，每行三个整数T, A, B，表示一对恒星(A, B)之间的亮度关系。恒星的编号从1 开始。
如果 T = 1，说明A 和B 亮度相等。
如果 T = 2，说明A 的亮度小于B 的亮度。
如果 T = 3，说明A 的亮度不小于B 的亮度。
如果 T = 4，说明A 的亮度大于B 的亮度。
如果 T = 5，说明A 的亮度不大于B 的亮度。
【输出格式】
输出一个整数表示答案。若题目有矛盾则输出-1。

差分约束
1.A = B ==》 A <= B && B <= A
2.A < B ==》 A <= B-1
3.A >= B =》 B <= A
4.A > B ==》 B <= A-1
5.A <= B =》 A <= B
由最短路中dis[b]<=dis[a]+u[a,b] 可将上面的式子转化成最短路
最短路可以判负环，所以把所有的都转化成负的
判负环就是如果一个点进队超过n次，就有负环
好像把-1改成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
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
int n,m,t,x,y,c,ds[100001],vis[100001];
long long ans;
bool b[100001];
vector<int> to[100001],cost[100001];
queue<int> q;
int main()
{
	freopen("gin.in","r",stdin);
	freopen("gin.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&t,&x,&y);
		if(x==y&&!(t%2)) {printf("-1");return 0;} //矛盾
		if(t==2)
		  to[x].push_back(y),cost[x].push_back(-1);
		else if(t==3)
		  to[y].push_back(x),cost[y].push_back(0);
		else if(t==4)
		  to[y].push_back(x),cost[y].push_back(-1);
		else if(t==5)
		  to[x].push_back(y),cost[x].push_back(0);
		else
		{
			to[x].push_back(y);cost[x].push_back(0);
			to[y].push_back(x);cost[y].push_back(0);
		}
	}
	for(int i=1;i<=n;i++)
	  to[0].push_back(i),cost[0].push_back(0);
	memset(ds,0x7f,sizeof(ds));
	ds[0]=-1;b[0]=1;q.push(0);vis[0]=1;
	while(!q.empty())
	{
		x=q.front();q.pop();b[x]=0;
		for(int i=0;i<to[x].size();i++)
		{
			y=to[x][i];c=cost[x][i];
			if(ds[x]+c<ds[y])
			{
				ds[y]=ds[x]+c;
				if(!b[y])
				{
					if(vis[y]==n) {printf("-1");return 0;}
					vis[y]++;
					b[y]=1;
					q.push(y);
				}
			}
		}
	}
	for(int i=1;i<=n;i++)
	  ans-=ds[i];
	printf("%lld",ans);
}

3 选举预测(ele)

【题目描述】
科学院的领袖Dunkelheit 的任期，随着局势的平复很快就要结束了。于是，这次具有非凡意义的科学院新领袖的选举很快就要开始了。
选举的第一步是辩论赛。它的规则是这样的：如果当前剩下的候选人多于2 人，那么就从中任选2 人进行辩论。输者退出比赛，胜利者继续留在比赛中，如此直到只剩下一个候选人，他就取得了辩论赛的胜利。辩论赛的胜者在后面的选举中将会更占优势，所以说人们都很关注这次比赛的结果，历史学家Geheimnis 也不例外。他收集了所有N 个候选人的资料，发现如果两个候选人以前曾经比赛过，那么这两个人再次比赛的时候比赛结果是很难改变的（可以认为是不可能）。按照Geheimnis 掌握的情报，你需要帮助他判断那些候选人有可能取得胜利。
【输入格式】
第一行包含一个正整数N，表示候选人的数目。
之后 N 行，候选人从1 开始编号，第(i + 1)行描述第 i 个候选人。第一个数为K，后面K 个编号，表示候选人 i 之前赢过的候选人。
【输出格式】
输出一行。第一个数为C，表示有C 个候选人有可能取得胜利；之后C 个数表示他们的编号。

题解：
显而易见，出度最大的人可以胜利。
（如果他不能胜利，必须存在一个人战胜他和他能战胜的人，这样出度就比他还大了。）
然后如果一个人可以赢一个可以胜利的人，那么他就可以获得最终胜利。
（如果A不能战胜B,则B就有可能战胜A。）
按照这个bfs就可以了。

我并没有想到题解，暴力写dfs，对了40
才开始改的时候没有把剩余的写到一个队列里面，直接一个一个搜，结果有一个点50多秒。。。

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
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
vector<int> to[1000001];
queue<int> q,sheng;
int n,m,x,y,ans=1,maxx=-1,maxi,s;
bool a[1000001],b[1000001];
int main()
{
	freopen("ele.in","r",stdin);
	freopen("ele.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&x);
		if(x>maxx) maxx=x,maxi=i;
		to[i].push_back(i);
		for(int j=1;j<=x;j++)
		  scanf("%d",&y),to[i].push_back(y);
	}
	q.push(maxi);b[maxi]=1;
	for(int i=1;i<maxi;i++) sheng.push(i);
	for(int i=maxi+1;i<=n;i++) sheng.push(i);
	while(!q.empty())
	{
		x=q.front();q.pop();
		for(int i=0;i<to[x].size();i++)  a[to[x][i]]=1;
		for(int i=1;i<=n-ans;i++)
		{
			y=sheng.front();sheng.pop();
			if(!a[y]) ans++,b[y]=1,q.push(y);
			else sheng.push(y);
		}
		for(int i=0;i<to[x].size();i++)  a[to[x][i]]=0;
	}
	printf("%d",ans);
	for(int i=1;i<=n;i++)
	  if(b[i]) printf(" %d",i);
}