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

  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

#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,求最大路也行

#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多秒。。。

#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);
}