T1 消失的无向图(missing)

题目描述

从前有一张n个点的无向图，边权都是正整数。但现在所有的边都消失了，只留下任意两点之间的最短路。

你现在想知道，所有边的边权和至少是多少。

​

输入格式

从文件missing.in中读入数据。

第一行一个正整数n 。

接下来一个n×n的矩阵A ，其中\(Ai,j\)代表原来图中i到j的最短路。

保证\(Ai,i=0,Ai,j=Aj,i\)。

​

输出格式

输出到文件missing.out中。

一行一个整数，表示答案。

如果不存在任何连边方案满足所有的最短路限制，输出-1 。

​

样例

样例输入

30 1 31 0 23 2 0

样例输出

3

​

数据范围与提示

对于 30% 的数据，n≤7 。

对于另外 30% 的数据，保证存在一种最优解，满足原图是一条链。

对于 100% 的数据，满足 n≤300,1≤ Ai,j ≤10^9(i , j)

Solution

先判断无解的情况，如果存在 \(A_{i,k}+A_{k,j} \lt A_{i,j}\)，则直接输出-1.

要让边权和最小，所以不能添加不在任何最短路上的边。这也意味着如果点 \(u\) 和点 \(v\) 之间有边，那么边权一定是 \(A_{u,v}\) 。因为如果比这个小，那么 \(u\) 和 \(v\) 之间的最短路就不是 \(A_{u,v}\) ，如果比这个大，那么可以把经过这条边改成经过 \(u\) 和 \(v\) 之间的最短路，这样距离更短，于是这条边就不会出现在任何最短路中。

我们可以一开始把所有的点对连上边，这样问题变成了删掉一些边，使任意两点之间的最短路不变，并且要使删掉边的权值和尽量大。

用类似floyed的做法，枚举一个中间点，对于一条边 \((u,v)\) ,如果存在异于点 \(u,v\) 的点 \(w\) 使得 \(A_{u,w}+A_{w,v}=A_{u,v}\) ，就说明存在另一条长度和 \(A_{u,v}\) 相等的从 \(u\) 到 \(v\) 的路径，就可以删掉这条边。

时间复杂度 \(O(n^3)\) 。

#include
    
     using namespace std;inline int read(){    int x=0,f=1;char ch=getchar();    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}    return x*f;}#define MN 305long long ans,dis[MN][MN],n;bool usd[MN][MN];int main(){    freopen("missing.in","r",stdin);    freopen("missing.out","w",stdout);    n=read();    register int i,j,k;    for(i=1;i<=n;i++)for(j=1;j<=n;j++) dis[i][j]=read();    for(k=1;k<=n;k++)for(i=1;i<=n;i++)for(j=1;j<=n;j++){        if(dis[i][k]+dis[k][j]
     
      >1LL);}
     
    

T2 跳(jump)

题目描述

Steaunk 喜欢跳。

他想跳多远就能跳多远。

他要跳往目的地。目的地和他的距离是D 。

然而他很浪，他想每次随机生成一个距离，然后朝着目的地跳过去。

当然他有可能跳过头，也就是跳到了目的地的另一侧，当然，这时候他会转向，重新朝向目的地。

Steaunk 是聪明的，所以如果他发现跳过之后他到目的地的距离比原来还远的话，他会选择不跳。

E.Space 知道Steaunk 的随机数生成器接下来按顺序产生的n 个数。

他想知道，对于每个1≤i≤m，他能否通过强行改变这n个数中的第qi 个数，使得Steaunk 无法在n步之内到达目的地。

注意：可以改变成原来的数值。

输入格式

从文件jump.in中读入数据。

第一行两个正整数n ，D 。

第二行n个正整数aii，表示Steaunk 的随机数生成器接下来生成的第i个数是ai 。

第三行一个正整数m 。

第四行m个正整数，其中第iii个表示qi 。

输出格式

输出到文件jump.out中。

输出m行。

对于第iii行，如果E.Space 能通过强行改变这n个数中的第qi个数，使得Steaunk无法在n步之内到达目的地，那么输出YES ，否则输出NO。

样例

样例输入

4 103 4 3 324 3

样例输出

NOYES

数据范围与提示

对于 30% 的数据，保证 n≤100 ，D≤2500。

对于另外 20% 的数据，保证 ai 在 [1,D] 之间均匀随机。

对于 100% 的数据，保证 n≤5×105 ，m≤5×105 ，D≤109 ，ai ≤109 ，qi ≤n。

Solution

预处理出如果 E.Space 不做任何改变，那么每一步之后 Steaunk 会跳到哪里。记第 \(i\) 步之后 Steaunk 与目的地的距离是 \(d_i\) ( \(d_0=D\)) 。考虑对于每个时刻求出所有使得 Steaunk 能够到达目的地的位置集合。形式化地，定义集合 \(S_i(i=1,2,\ldots ,n+1)\) ，如果在第 \(i-1\) 步之后 Steaunk 与目的地的距离是 \(x\) 且之后 E.Space 不做任何改变，Steaunk 能到达目的地，那么 \(x\in S_i\) 。

对于 \(q=i\) 的询问，如果 \(d_{i-1} \ge \mathrm{mex}\ S_{i+1}\) ，即存在一个小于等于 \(d_{i-1}\) 的正整数不在 \(S_{i+1}\) 中，那么 E.Space 可以把 Steaunk 移到这个位置，使他不能到达目的地，所以答案是 YES ，否则答案是 NO 。

显然 $S_{n+1}={0},\mathrm{mex}  S_{n+1}= 1 $ 。

设 \(\mathrm{mex} \ S_{i+1}=x\) 。

如果 \(a_i \ge 2x\) ，显然 \(x \notin S_i\) 且 \(\mathrm{mex}\ S_i \ge x\) ，所以 \(\mathrm{mex}\ S_i =x\) 。

如果 \(a_i \lt 2x\) ，则 \(\forall j \in \mathbb{n} \ j \in \left[0,x+a_i\right),j\in S_i\) 且 \(x+a_i \notin S_i\) ，所以 \(\mathrm{mex}\ S_i=x+a_i\) 。

我们发现，询问只和 \(\mathrm{mex} \ S_i\) 有关，而 \(\mathrm{mex} \ S_i\) 的计算也只和 \(\mathrm{mex} \ S_{i+1}\) 和 \(a_i\) 有关，于是我们可以直接计算 \(\mathrm{mex} \ S_i\) 而不用计算 \(S_i\) 。

时间复杂度 \(O(n+m)\) 。

#include
    
     using namespace std;inline int read(){    int x=0,f=1;char ch=getchar();    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}    return x*f;}#define MN 500005int n,m,D,a[MN],d[MN],q[MN],mex[MN];int main(){    freopen("jump.in","r",stdin);    freopen("jump.out","w",stdout);    register int i,j,k;    n=read(),D=read();mex[n+1]=1;d[0]=D;    for(i=1;i<=n;i++) a[i]=read();    m=read();    for(i=1;i<=m;i++) q[i]=read();    for(i=1;i<=n;i++) d[i]=min(d[i-1],abs(d[i-1]-a[i]));    for(i=n;i;--i) mex[i]=((mex[i+1]<<1)>a[i])?mex[i+1]+a[i]:mex[i+1];    for(i=1;i<=m;i++) puts(d[q[i]-1]>=mex[q[i]+1]?"YES":"NO");    return 0;}
    

T3 动态完全图(graph)

题目描述

你的目标是维护一个动态图。

开始图有n个顶点，边集为空。

你需要支持下列三种操作：

1. 加入一条连接顶点u 和v的无向边。
2. 对于所有x ,y ，如果x 和u 连通并且y 和u 连通，加入一条连接顶点x 和y 的无向边。
3. 询问图中是否存在一条连接顶点u 和v 的边。

输入格式

从文件graph.in 中读入数据。

第一行两个正整数n ，m ，其中m 表示操作次数。

接下来m 行，每行表示一个操作。

对于操作1 ，格式为1 u v 。

对于操作2 ，格式为2 u 。

对于操作3 ，格式为3 u v 。

其中对于操作1,3 ，满足u≠v。

输出格式

输出到文件graph.out 中。

对于每个操作3 ，输出一行，如果存在一条连接顶点u 和v 的边，则输出Yes ，否则输出No 。

样例

样例输入

3 61 1 21 2 33 1 23 1 32 13 1 3

样例输出

YesNoYes

数据范围与提示

对于 20% 的数据，满足 n,m≤100 。

对于 50% 的数据，满足 n≤1000,m≤10000 。

对于另外 10% 的数据，满足没有操作 2 。 对于 100% 的数据，满足 n≤105,m≤2×105 。

Solution

对每个询问考虑是否存在一条无向边被前两个操作加上。

对于第 \(1\) 种操作，用一个哈希表或者 map 存储信息即可。

对于第 \(2\) 种操作，第 \(2\) 种操作相当于把点 \(u\) 所在连通块连成完全图。我们可以用并查集维护每个完全图中点的集合，若遇到第 \(1\) 种操作，直接在集合中连边，遇到第 \(2\) 种操作，直接遍历 \(u\) 所在连通块，把经过的集合合并到一起并删掉原来访问过的边。由于每条边只会被访问 \(O(1)\) 次，所以复杂度是可以接受的。查询只需要查 \(u,v\) 是否在同一个集合中。

时间复杂度 \(O(m\log n)\) 。

#include
    
     using namespace std;inline int read(){    int x=0,f=1;char ch=getchar();    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}    return x*f;}#define MN 100005#define ME 200005 int n,m,fu,fv,opt,u,v,par[MN];int q[MN],l,r;bool vis[MN];map
     
       mp[MN];inline int getf(int x){return par[x]==x?x:par[x]=getf(par[x]);}struct edge{int to,nex;}e[ME<<1];int cnt=0,hr[MN];inline void ins(int f,int t){    e[++cnt]=(edge){t,hr[f]};hr[f]=cnt;    e[++cnt]=(edge){f,hr[t]};hr[t]=cnt; }int main(){    freopen("graph.in","r",stdin);    freopen("graph.out","w",stdout);    n=read(),m=read();    register int i,j,head,tail;    for(i=1;i<=n;++i) par[i]=i;    while(m--){        opt=read();u=read();        switch(opt){            case 1: v=read();mp[u][v]=mp[v][u]=true;                     fu=getf(u);fv=getf(v);ins(fu,fv);break;            case 2: fu=getf(u);memset(vis,0,sizeof vis);                     for(q[l=r=1]=fu,vis[fu]=true;l<=r;++l)                    for(j=hr[q[l]];j;j=e[j].nex)                        if(!vis[e[j].to]) vis[q[++r]=e[j].to]=true;                    for(j=1;j<=r;++j) hr[q[j]]=0,par[q[j]]=fu;                    break;            case 3: v=read();                    if(mp[u][v]||getf(u)==getf(v)) puts("Yes");                    else puts("No");break;        }    }    return 0;}
     
    

---

Blog来自PaperCloud，未经允许，请勿转载，TKS！