[关闭]
@ysner 2018-08-08T19:50:47.000000Z 字数 2695 阅读 1829

[bzoj3273]liars

脑洞 思维 最短路


题面

个人,编号分别为。这个人中每个人不是诚实者就是说谎者,并且每个人都知
道下一个人的身份(即第个人知道第个人的身份,,且第个人知道第个人的
身份)。现在已知每个人对他下一个人的身份的判断,并且说谎者的人数不超过,问哪些人一定是说谎者。注意,诚实者给出的判断一定是正确的,但说谎者给出的判断是不确定的,可能正确也可能错误。

解析

好像不是第一次看见用图论知识表示各种关系的题目了。
然而我考场上写了个二分

算法

题目要我们找各种说谎者方案的交集。即这个人无论在何种情形下,都是说谎者。
我们可以枚举每一个人,强制他为诚实者,然后看该条件下是否有合法(说谎者不超过)的方案。
如果没有,就说明这个人一定是说谎者,统计进答案。

具体怎么实现?怎样最小化说谎者数?
为每个人建两个点,一个代表他诚实,另一个代表他说谎。
若该人判断下一个人诚实,则诚实点连向下一个人的诚实点;否则连向说谎点。
说谎点同时连向下一个人的诚实点和说谎点。(实质代表可能的诚实、说谎方案)

连向说谎点的边设边权为,就可以统计说谎者个数。
于是破环为链,求一个点到另一个自己的最短路(为了保证合法,起点终点必须同一性质,同为诚实点或说谎点)就是答案。

复杂度

算法

每一个人都跑一次最短路是不是有点浪费?
注意到每次求的最短路都经过了所有的人。
实际上,我们可以把起点终点都转化为(新建一个代表号人的点)。然后求的是经过当前点的最短路径。
于是预处理从起点的两个点、终点的两个点分别出发的最短路,若起点诚实点到终点诚实点、起点说谎点到终点说谎点的距离均,就可把该人统计进答案。
复杂度

注意到建边有一些细节,不能建双向边(要不然走回去是什么鬼),要一次建正边、一次建反边来分别预处理;建反边注意一下方向和权值。

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstdlib>
  4. #include<cstring>
  5. #include<cmath>
  6. #include<algorithm>
  7. #include<queue>
  8. #define re register
  9. #define il inline
  10. #define ll long long
  11. #define max(a,b) ((a)>(b)?(a):(b))
  12. #define min(a,b) ((a)<(b)?(a):(b))
  13. #define fp(i,a,b) for(re int i=a;i<=b;i++)
  14. #define fq(i,a,b) for(re int i=a;i>=b;i--)
  15. using namespace std;
  16. const int mod=1e9+7,N=5e5+100;
  17. struct Edge{int to,nxt,w;}e[N<<2];
  18. struct node{int dis,u;bool operator < (const node &o) const {return dis>o.dis;}};
  19. priority_queue<node>Q;
  20. int n,t,a[N],tot,ans,h[N],cnt,dis[4][N];
  21. bool vis[N];
  22. il void add(re int u,re int v,re int w){e[++cnt]=(Edge){v,h[u],w};h[u]=cnt;}
  23. il ll gi()
  24. {
  25. re ll x=0,t=1;
  26. re char ch=getchar();
  27. while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  28. if(ch=='-') t=-1,ch=getchar();
  29. while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  30. return x*t;
  31. }
  32. il void SPFA(re int id,re int st)
  33. {
  34. memset(dis[id],63,sizeof(dis[id]));Q.push((node){0,st});vis[st]=1;dis[id][st]=0;
  35. while(!Q.empty())
  36. {
  37. re int u=Q.top().u;Q.pop();
  38. for(re int i=h[u];i+1;i=e[i].nxt)
  39. {
  40. re int v=e[i].to;
  41. if(dis[id][v]>dis[id][u]+e[i].w)
  42. {
  43. dis[id][v]=dis[id][u]+e[i].w;
  44. if(!vis[v]) vis[v]=1,Q.push((node){dis[id][v],v});
  45. }
  46. }
  47. vis[u]=0;
  48. }
  49. }
  50. int main()
  51. {
  52. freopen("liars.in","r",stdin);
  53. freopen("liars.out","w",stdout);
  54. re int T=gi();
  55. while(T--)
  56. {
  57. memset(h,-1,sizeof(h));cnt=0;
  58. n=gi();t=gi();
  59. fp(i,1,n) a[i]=gi();
  60. fp(i,1,n)
  61. {
  62. if(a[i]) add(i<<1,(i+1)<<1|1,1);else add(i<<1,(i+1)<<1,0);
  63. add(i<<1|1,(i+1)<<1,0);add(i<<1|1,(i+1)<<1|1,1);
  64. }
  65. SPFA(0,1<<1);SPFA(1,1<<1|1);
  66. memset(h,-1,sizeof(h));cnt=0;
  67. fq(i,n+1,2)
  68. {
  69. if(a[i-1]) add(i<<1|1,(i-1)<<1,1);else add(i<<1,(i-1)<<1,0);
  70. add(i<<1,(i-1)<<1|1,0);add(i<<1|1,(i-1)<<1|1,1);
  71. }
  72. SPFA(2,(n+1)<<1);SPFA(3,(n+1)<<1|1);//n<<1???
  73. re int flag=0,tag=0;
  74. fp(i,1,n)
  75. {
  76. i<<=1;
  77. if(min(dis[0][i]+dis[2][i],dis[1][i]+dis[3][i])>t)
  78. {
  79. flag++;if(!tag) tag=i>>1;
  80. }
  81. //printf("%d %d %d %d %d\n",i,dis[0][i],dis[2][i],dis[1][i],dis[3][i]);
  82. i>>=1;
  83. }
  84. if(!flag) puts("0 0");
  85. else printf("%d %d\n",flag,tag);
  86. }
  87. fclose(stdin);
  88. fclose(stdout);
  89. return 0;
  90. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注