省常中联测题选VII HGOI1025

图论专场!!!!

打到吐血也没打完。

看错第二题瞎

打的程序没过样例都骗了十五分。(弱鸡数据!)


T1 Line

题目描述

    有n 个士兵站在坐标轴的整点上,每个整点可以容纳任意多个士兵。我们记第i 号士兵的位置为Xi。
现在有m 个关于这些士兵的信息,一条信息被描述为(L,R,D)。表示第R名士兵在第L 名士兵的右边D 个单位。即XR-XL=D。注意D 可能是负数。
小D 想知道这些信息是否相互矛盾。如果不矛盾,他还想知道最右边的士兵与最左边的士兵最小的距离是多少。

解析

  • 差分约束的模板题。
  • 看到一堆二元一次不等式(等式)就可以想到差分约束。所谓差分约束就是将不等式中的x抽象成最短路中的dis数组
  • 本题为等式,所以对于每个式子建立两条边,权值绝对值为等式的值,一正一负。然后跑SPFA如果一个节点的最短路被更新了两次,那么方程无解,直接弹出

AC程序

#include <bits/stdc++.h>
using namespace std;
#define Rint register int
typedef long long ll;
ll hd[100010],nxt[400010],eds[400010],val[400010],et=0;
inline ll read(){
    ll x=0,w=1;char c=getchar();
    while(!isdigit(c)){
        if(c=='-')w=-1;
        c=getchar();
    }
    while(isdigit(c)){
        x=(x<<1)+(x<<3)+c-'0';
        c=getchar();
    }
    return x*w;
}
inline void ad(ll u,ll v,ll w){
    eds[++et]=v;
    val[et]=w;
    nxt[et]=hd[u];
    hd[u]=et;
}
ll n,m;
ll dis[100010];
bool vstd[100010];
bool inq[100010];
queue<ll> q;
ll spfa(ll u){
    memset(vstd,0,sizeof(vstd));
    ll minn=0,maxx=0;
    dis[u]=0;
    while(!q.empty())q.pop();
    q.push(u);
    inq[u]=true;
    while(!q.empty()){
        ll now=q.front();
        q.pop();
        inq[now]=false;
        for (Rint i=hd[now];i;i=nxt[i])
            if (dis[eds[i]]>dis[now]+val[i]){
                if(vstd[eds[i]])return -1;
                vstd[eds[i]]=true;
                dis[eds[i]]=dis[now]+val[i];
                maxx=max(maxx,dis[eds[i]]);
                minn=min(minn,dis[eds[i]]);
                if(!inq[eds[i]]){
                    inq[eds[i]]=true;
                    q.push(eds[i]);
                }
            }
    }
    return maxx-minn;
}
int main(){
    //freopen("line.in","r",stdin);
    //freopen("line.out","w",stdout);
    n=read(),m=read();
    ll t1,t2,t3;
    for (Rint i=1;i<=m;i++){
        t1=read(),t2=read(),t3=read();
        ad(t1,t2,t3);
        ad(t2,t1,-t3);
    }
    memset(dis,0x3f,sizeof(dis));
    ll maxx=0;
    for (Rint i=1;i<=n;i++)
        if (dis[i]==0x3f3f3f3f3f3f3f3f){
            ll tmp=spfa(i);
            if (tmp==-1){
                puts("impossible");
                return 0;
            }
            maxx=max(maxx,tmp);
        }
    printf("%lld",maxx);
    return 0;
} 

T2 Evade

题目描述

    有一天,他们结伴到一个城市中去玩,由于人很多他们不幸地失散了。这个城市可以看做有n 个节点,m 条边的无向图,第i 条边连接着第Ui个点与第Vi个点并且走过这条边要花费Ci的时间。小B 现在处于S 点而小Z 处在T 点。
为了尽快走到一起,小B 正沿着最短路自S 点向T 点走去,小Z 也沿着最短路自T 点向S 点走去(如果最短路有多条,那么他们会各自随机选择一条)。
但是他们发现了一个问题:他们可能并不会在途中(点上或者边上)相遇。
现在他们想知道,有多少种不同的情况他们不会在途中相遇。
由于情况可能很多,输出不同的情况数对109+7 取模后的结果。
两种情况是不同的,当且仅当在至少一个人的路径中,存在一条边在其中一种情况下被经过,在另一种情况下没有。
我们称两个人相遇了,仅当存在一个时间t,他们在同一个点上,或在同一条边上的同一个位置。

解析

  • 考虑容斥,我们用总方案数减去相遇的方案数。显然,总放案数为(S-T 最短路的条数)2
  • 接下来可以枚举他们在哪一个点或哪一条边相遇。首先可以通过一个简单的dp 求出S 通过
    最短路到其他点的方案数Fi 以及其他点到T 经过最短路的方案数Gi。由于是最短路,所以到
  • 达每个点的时间是确定的。如果一个点v 满足(S 到v 的距离)=(v 到T 的距离),那么他们可以在这个点相遇且方案数为(FvGv)2 。如果一条边(u,v,c)满足:S 到u 的距离∈(v 到T 的距离-c,v到T 的距离+c),那么他们可以在这个点相遇且方案数为(FvGu)2
  • 时间复杂度:O(NlogM)(最短路的复杂度)

AC程序

#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
int n,m,s,t,x,y,w,fa[100010],dist[100010],cnt[100010],cnt2[100010],vi[100010],ti,p[100010];
long long res;
vector<int> g[100010],l[100010],id[100010];
queue<int> q;

inline int read(){
    int u=0;char c=getchar();
    while(c<'0'||c>'9') c=getchar();
    while(c>='0'&&c<='9') u=(u<<1)+(u<<3)+c-'0',c=getchar();
    return u;
}

void spfa(int s){
    memset(dist,0x3f3f3f3f,sizeof(dist));
    q.push(s),dist[s]=0,vi[s]=1;
    while(!q.empty()){
        int u=q.front();q.pop();vi[u]=0;
        for(int i=0;i<g[u].size();i++){
            int v=g[u][i];
            if(dist[v]>dist[u]+l[u][i]){
                dist[v]=dist[u]+l[u][i];
                if(!vi[v]) vi[v]=1,q.push(v);
            }
        }
    }
    ti=dist[t];
}

bool cmp(int x,int y){
    return dist[x]<dist[y];
}

void solve(){
    cnt[s]=1;
    for(int i=1;i<=n;i++) p[i]=i;
    sort(p+1,p+n+1,cmp);
    for(int i=1;i<=n;i++){
        int u=p[i];
        for(int j=0;j<g[u].size();j++){
            int v=g[u][j];
            if(dist[u]+l[u][j]==dist[v]) cnt[v]=(cnt[v]+cnt[u])%mod;
        }
    }
    cnt2[t]=1;
    for(int i=n;i>=1;i--){
        int u=p[i];
        for(int j=0;j<g[u].size();j++){
            int v=g[u][j];
            if(dist[u]-l[u][j]==dist[v]) cnt2[v]=(cnt2[v]+cnt2[u])%mod;
        }
    }
    res=1ll*cnt[t]%mod*cnt[t]%mod;
    for(int i=1;i<=n;i++){
        if(dist[i]*2==dist[t]) res=(res-1ll*cnt[i]%mod*cnt2[i]%mod*cnt[i]%mod*cnt2[i]%mod+mod)%mod;
        for(int j=0;j<g[i].size();j++){
            int v=g[i][j];
            if(dist[v]==dist[i]+l[i][j])
                if(dist[i]*2<dist[t]&&dist[v]*2>dist[t])
                    res=(res-1ll*cnt[i]%mod*cnt2[v]%mod*cnt[i]%mod*cnt2[v]%mod+mod)%mod;
        }
    }
}

int main(){
//  freopen("evade.in","r",stdin);
//  freopen("evade.out","w",stdout);
    n=read(),m=read(),s=read(),t=read();
    for(int i=1;i<=m;i++){
        x=read(),y=read(),w=read();
        g[x].push_back(y),l[x].push_back(w),g[y].push_back(x),l[y].push_back(w);
    }
    spfa(s);
    solve();
    printf("%lld",(res+mod)%mod);
}

T3 Access

做过的题目 详情见三si校联考题选 HGOI0822 【转自genies】T3

题目描述

 有一棵n 个节点,n-1 条边的树。树上有m 条路径,定义两条路径相交仅当这两条路径经过至少一个相同的点。小D 想知道:从这m 条路径中选择两条相交的路径的方案数。

解析

  • 考虑使用树状数组+DFS序+倍增LCA解决本道问题。
  • 因为只需要最终答案,所以可以考虑离线算法。在这里我将所有的查询情况按照LCA的深度进行降序排序,确保后面做到的LCA深度一定大于等于前面的
  • 显而易见,后面的路径若想与前面的路径相交,必然穿过前面路径的LCA。所以只需判断路径的两个端点是否在前面路径LCA的子树中
  • 这里就要用到DFS序若端点在前面路径LCA子树中,则它的DFS一定大于等于其入序小于等于其出序
  • 而这里由于需要计算某个节点在之前多少条路径LCA的子树中,我使用了树状数组进行区间更新单点查询的维护每次查询完就更新当前路径LCA入序出序之间的和
  • 需要注意的是由于两个路径的LCA可能相同,导致左右端点重复计算,所以要减掉当前节点是前面多少节点的LCA,防止重复。

AC程序

#include <bits/stdc++.h>
using namespace std;
#define Rint register int
typedef long long ll;
ll hd[1000010],nxt[2000010],eds[2000010],et=0;
inline ll read(){
    ll x=0,w=1;char c=getchar();
    while(!isdigit(c)){
        if(c=='-')w=-1;
        c=getchar();
    }
    while(isdigit(c)){
        x=(x<<1)+(x<<3)+c-'0';
        c=getchar();
    }
    return x*w;
}
inline void ad(ll u,ll v){
    eds[++et]=v;
    nxt[et]=hd[u];
    hd[u]=et;
}
ll n,m;
ll depth[1000010],fa[1000010][21],clk[1000010][2],clks=0;
void dfs(ll u,ll pa){
    clk[u][0]=++clks;
    fa[u][0]=pa;
    depth[u]=depth[pa]+1;
    for (Rint i=hd[u];i;i=nxt[i])
        if(eds[i]!=pa)
            dfs(eds[i],u);
    clk[u][1]=++clks;
}
ll lca(ll u,ll v){
    if (depth[u]<depth[v])swap(u,v);
    for (Rint i=20;i>=0;i--)
        if (depth[fa[u][i]]>=depth[v])
            u=fa[u][i];
    if(u==v)return u;
    for (Rint i=20;i>=0;i--)
        if (fa[u][i]!=fa[v][i])
            u=fa[u][i],
            v=fa[v][i];
    return fa[u][0];
}
struct v3{
    ll x,y,z;
    bool operator<(const v3 tar)const{
        return depth[z]>depth[tar.z];
    }
}src[1000010];
ll cnt[1000010],bt[2000010];
#define LB(X) ((X)&-(X))
inline void bt_ad(ll u,ll w){
    while(u<=2*n){
        bt[u]+=w;
        u+=LB(u);
    }
}
inline ll bt_qry(ll u){
    ll res=0;
    while(u){
        res+=bt[u];
        u-=LB(u);
    }
    return res;
}
int main(){
    //freopen("access.in","r",stdin);
    //freopen("access.out","w",stdout);
    n=read(),m=read();
    ll t1,t2,t3;
    for (Rint i=1;i<n;i++){
        t1=read(),t2=read();
        ad(t1,t2);
        ad(t2,t1);
    }
    dfs(1,0);
    for (Rint i=1;i<=20;i++)
        for (Rint j=1;j<=n;j++)
            fa[j][i]=fa[fa[j][i-1]][i-1];
    for (Rint i=1;i<=m;i++){
        t1=read(),t2=read();
        t3=lca(t1,t2);
        src[i]=v3{t1,t2,t3};
    }
    sort(src+1,src+1+m);
    #define LT src[i].x 
    #define RT src[i].y 
    #define LCA src[i].z
    ll res=0;
    for (Rint i=1;i<=m;i++){
        res+=bt_qry(clk[LT][0])+bt_qry(clk[RT][0])-cnt[LCA];
        cnt[LCA]++;
        bt_ad(clk[LCA][0],1);
        bt_ad(clk[LCA][1]+1,-1);
    }
    printf("%lld",res);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注