题面
有\(n\)个人,编号分别为\(1,2,...,n\)。这\(n\)个人中每个人不是诚实者就是说谎者,并且每个人都知
道下一个人的身份(即第\(k\)个人知道第\(k+1\)个人的身份,\(1\leq k<n\),且第\(n\)个人知道第\(1\)个人的 身份)。现在已知每个人对他下一个人的身份的判断,并且说谎者的人数不超过\(t\),问哪些人一定是说谎者。注意,诚实者给出的判断一定是正确的,但说谎者给出的判断是不确定的,可能正确也可能错误。- \(30pts\ n\leq1000\)
\(100pts\ n\leq10^5\)
解析
好像不是第一次看见用图论知识表示各种关系的题目了。
然而我考场上写了个二分\(30pts\)算法
题目要我们找各种说谎者方案的交集。即这个人无论在何种情形下，都是说谎者。
我们可以枚举每一个人，强制他为诚实者，然后看该条件下是否有合法（说谎者不超过\(t\)）的方案。 如果没有，就说明这个人一定是说谎者，统计进答案。
具体怎么实现？怎样最小化说谎者数？
为每个人建两个点，一个代表他诚实，另一个代表他说谎。 若该人判断下一个人诚实，则诚实点连向下一个人的诚实点;否则连向说谎点。 说谎点同时连向下一个人的诚实点和说谎点。（实质代表可能的诚实、说谎方案）连向说谎点的边设边权为\(1\),就可以统计说谎者个数。
于是破环为链，求一个点到另一个自己的最短路（为了保证合法，起点终点必须同一性质，同为诚实点或说谎点）就是答案。复杂度\(O(n^2)\)
\(100pts\)算法
每一个人都跑一次最短路是不是有点浪费？
注意到每次求的最短路都经过了所有的人。实际上，我们可以把起点终点都转化为\(1\)（新建一个代表\(1\)号人的点）。然后求的是经过当前点的最短路径。 于是\(O(nlogn)\)预处理从起点的两个点、终点的两个点分别出发的最短路，若起点诚实点到终点诚实点、起点说谎点到终点说谎点的距离均\(>t\)，就可把该人统计进答案。 复杂度\(O(nlogn+n)\)。注意到建边有一些细节，不能建双向边（要不然走回去是什么鬼），要一次建正边、一次建反边来分别预处理；建反边注意一下方向和权值。
#include#include #include #include #include #include #include #define re register#define il inline#define ll long long#define max(a,b) ((a)>(b)?(a):(b))#define min(a,b) ((a)<(b)?(a):(b))#define fp(i,a,b) for(re int i=a;i<=b;i++)#define fq(i,a,b) for(re int i=a;i>=b;i--)using namespace std;const int mod=1e9+7,N=5e5+100;struct Edge{int to,nxt,w;}e[N<<2];struct node{int dis,u;bool operator < (const node &o) const {return dis>o.dis;}};priority_queue Q;int n,t,a[N],tot,ans,h[N],cnt,dis[4][N];bool vis[N];il void add(re int u,re int v,re int w){e[++cnt]=(Edge){v,h[u],w};h[u]=cnt;}il ll gi(){ re ll x=0,t=1; re char ch=getchar(); while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar(); if(ch=='-') t=-1,ch=getchar(); while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar(); return x*t;}il void SPFA(re int id,re int st){ memset(dis[id],63,sizeof(dis[id]));Q.push((node){0,st});vis[st]=1;dis[id][st]=0; while(!Q.empty()) { re int u=Q.top().u;Q.pop(); for(re int i=h[u];i+1;i=e[i].nxt) { re int v=e[i].to; if(dis[id][v]>dis[id][u]+e[i].w) { dis[id][v]=dis[id][u]+e[i].w; if(!vis[v]) vis[v]=1,Q.push((node){dis[id][v],v}); } } vis[u]=0; }}int main(){ freopen("liars.in","r",stdin); freopen("liars.out","w",stdout); re int T=gi(); while(T--) { memset(h,-1,sizeof(h));cnt=0; n=gi();t=gi(); fp(i,1,n) a[i]=gi(); fp(i,1,n) { if(a[i]) add(i<<1,(i+1)<<1|1,1);else add(i<<1,(i+1)<<1,0); add(i<<1|1,(i+1)<<1,0);add(i<<1|1,(i+1)<<1|1,1); } SPFA(0,1<<1);SPFA(1,1<<1|1); memset(h,-1,sizeof(h));cnt=0; fq(i,n+1,2) { if(a[i-1]) add(i<<1|1,(i-1)<<1,1);else add(i<<1,(i-1)<<1,0); add(i<<1,(i-1)<<1|1,0);add(i<<1|1,(i-1)<<1|1,1); } SPFA(2,(n+1)<<1);SPFA(3,(n+1)<<1|1);//n<<1??? re int flag=0,tag=0; fp(i,1,n) { i<<=1; if(min(dis[0][i]+dis[2][i],dis[1][i]+dis[3][i])>t) { flag++;if(!tag) tag=i>>1; } //printf("%d %d %d %d %d\n",i,dis[0][i],dis[2][i],dis[1][i],dis[3][i]); i>>=1; } if(!flag) puts("0 0"); else printf("%d %d\n",flag,tag); } fclose(stdin); fclose(stdout); return 0;}