头像

RingweEH

Ambarónë.




离线:8天前


最近来访(279)
用户头像
lirq
用户头像
222222
用户头像
Escort
用户头像
俺是早睡小朋友
用户头像
翩竹
用户头像
LC.
用户头像
dys
用户头像
tsib
用户头像
抔土托孤.
用户头像
laklc295
用户头像
mynamepfd9
用户头像
Tingting
用户头像
心里没有一点AC数
用户头像
远山淡影0_0
用户头像
CYMario
用户头像
CaiJ
用户头像
池鱼_40
用户头像
唯手熟尔hh
用户头像
no_hard
用户头像
hySensei

新鲜事 原文

RingweEH
7个月前
晚来的樱花。
图片



RingweEH
9个月前

莫名其妙就一百粉了(

搬一篇我的博文证明我还活着((

更好的阅读体验

1 - 最大流

下面那个什么能跑 $1e4,1e5$ 的是前人经验,没拿数据测试过,不过一般网络流题的复杂度好像是玄学,数据范围算出来不是太离谱都能做……

问题概述

基本概念参见 OI-Wiki

有一张图,要求从源点流向汇点的最大流量(可以有很多条路到达汇点)。

高科技:O(nm)最大流

Edmond-Karp(EK)

复杂度:$\mathcal{O}(nm^2)$ ,处理范围在 $1e3\sim 1e4$ 左右。

思路:从源点到汇点有很多条路径,每次抽取一条,并找出路径上的边权最小值 $x$ ,然后把路径上所有边权都减去$x$(也就是找增广路,这条路径上流过 $x$ 的流量),直到没有路径可以给汇点增加流量为止。显然, $0$ 容量是没有用的。具体实现采用 BFS 。

如果是单纯的建边跑不了最大流,因为如果之前选的并不是最优路径后面就不一定能取到最大值。EK 支持一个 反悔操作 ,也就是建反向边,初始为 $0$ ,如果对应的正向边剩余容量减少,那么相应的反向边容量就增加,之后反向边就能流动了。

//Author:RingweEH
//P3376 【模板】网络最大流
const int N=210,M=5e3+10;
const ll INF=0x7f7f7f7f;
struct Edge
{
    int to,nxt; ll val;
}e[M<<1];
int n,m,S,T,tot=1,head[N],pre[N],mp[N][N];
ll mxflow,dis[N];
bool vis[N];

void Add( int u,int v,int ll w )
{
    e[++tot].to=v; e[tot].nxt=head[u]; head[u]=tot; e[tot].val=w;
    e[++tot].to=u; e[tot].nxt=head[v]; head[v]=tot; e[tot].val=0;   //反向边
}

bool BFS()
{
    for ( int i=1; i<=n; i++ )
        vis[i]=0;
    queue<int> q; q.push( S ); vis[S]=1; dis[S]=INF;
    while ( !q.empty() )
    {
        int u=q.front(); q.pop();
        for ( int i=head[u]; i; i=e[i].nxt )
        {
            if ( e[i].val==0 ) continue;    //流没了
            int v=e[i].to;
            if ( vis[v] ) continue; 
            dis[v]=min( dis[u],e[i].val );  //取路径上的最小剩余容量
            pre[v]=i;       //记录从哪条边过来
            q.push( v ); vis[v]=1;
            if ( v==T ) return 1;   //走到汇点了
        }
    }
    return 0;
}

void Update()       //每次找到一条增广路,并更新路径上的值
{
    int u=T;
    while ( u^S )
    {
        int v=pre[u];
        e[v].val-=dis[T]; e[v^1].val+=dis[T];       
        //这条增广路的流量,用来更新路径上所有边和反向边
        u=e[v^1].to;        //本来记录的是过来的边,回去要反向
    }
    mxflow+=dis[T];     //总流量增加
}

int main()
{
    n=read(); m=read(); S=read(); T=read();
    for ( int i=1; i<=m; i++ )
    {
        int u,v; ll w; u=read(); v=read(); w=read();
        if ( mp[u][v]==0 ) Add( u,v,w ),mp[u][v]=tot;
        else e[mp[u][v]-1].val+=w;
        //重边容量合并
    }

    while ( BFS() ) Update();

    printf( "%lld\n",mxflow ); 

    return 0;
}

Dinic

复杂度 $\mathcal{O}(n^2m)$ ,处理范围在 $1e4\sim 1e5$ 左右,稠密图较明显,求解二分图最大匹配是 $\mathcal{O}(m\sqrt n)$ .

思路:BFS 得到分层图,$d[x]$ 表示层次(即 $S$ 到 $x$ 的最少边数)。残量网络中,满足 $d[y]=d[x]+1$ 的边 $(x,y)$ 构成的子图称为分层图。显然,这一定是一张有向无环图,从 $S$ 开始 DFS ,每次向下找一个点,直到到达 $T$ ,然后回溯回去,找另外的点搜索出多条增广路。

总结:

  • 在残量网络上 BFS 求出节点层次,构造分层图
  • 在分层图上 DFS 找增广路,回溯的同时更新边权

当前弧优化 :(没加这个复杂度是假的)

对于一个节点 $u$ ,在 DFS 中, for ( int i=head[u]; i; i=e[i].nxt ) 走到了第 $i$ 条弧时,前 $i-1$ 条到汇点 $T$ 的路径一定流满了,再访问 $u$ 时前 $i-1$ 条就没有意义了。所以每次枚举 $u$ 的时候,要改变枚举的起点,即 $nw$ ,for ( int i=now[x]; i; i=e[i].nxt ) .

//Author:RingweEH
//P3376 【模板】网络最大流
const int N=210,M=5e3+10;
const ll INF=0x7f7f7f7f;
struct Edge
{
    int to,nxt; ll val;
}e[M<<1];
int n,m,S,T,tot=1,nw[N],head[N];
ll mxflow,dis[N];

void Add( int u,int v,ll w )
{
    e[++tot].to=v; e[tot].nxt=head[u]; head[u]=tot; e[tot].val=w;
    e[++tot].to=u; e[tot].nxt=head[v]; head[v]=tot; e[tot].val=0;
}

bool BFS()      //构建分层图,判断残量网络还能不能到达汇点
{
    for ( int i=1; i<=n; i++ )
        dis[i]=INF;
    queue<int> q; q.push( S ); dis[S]=0; nw[S]=head[S];
    while ( !q.empty() )
    {
        int u=q.front(); q.pop();
        for ( int i=head[u]; i; i=e[i].nxt )
        {
            int v=e[i].to;
            if ( e[i].val>0 && dis[v]==INF )
            {
                q.push( v ); nw[v]=head[v]; dis[v]=dis[u]+1;
                if ( v==T ) return 1;
            }
        }
    }
    return 0;
}

int DFS( int u,ll sum )     //sum记录增广路上的最小容量
{
    if ( u==T ) return sum;
    ll res=0;
    for ( int i=nw[u]; i && sum; i=e[i].nxt )
    {
        nw[u]=i; int v=e[i].to;
        if ( e[i].val>0 && (dis[v]==dis[u]+1) )
        {
            ll tmp=DFS( v,min(sum,e[i].val) );
            if ( tmp==0 ) dis[v]=INF;   //v不能再增广了,剪枝
            e[i].val-=tmp; e[i^1].val+=tmp;
            res+=tmp; sum-=tmp;     //res是经过该点的流量和,sum是经过该点剩余流量
        }
    }
    return res;
}

int main()
{
    n=read(); m=read(); S=read(); T=read();
    for ( int i=1; i<=m; i++ )
    {
        int u=read(),v=read(); ll w=read();
        Add( u,v,w );
    }

    while ( BFS() ) mxflow+=DFS(S,INF);

    printf( "%lld\n",mxflow );

    return 0;
}

ISAP

复杂度:$\mathcal{O}(n^2m)$

看看 Dinic 的 while ( BFS() ) mxflow+=DFS(S,INF); ,这样重复 BFS 显然效率低下。于是出现了 ISAP ,只需要跑一遍 $bfs$ !

大体流程:

  • 从 $T$ 到 $S$ 跑 BFS
  • 从 $S$ 到 $T$ 跑 DFS
  • 重复第二步的 DFS 直到出现断层

ISAP 只跑一遍 BFS 标记层次,然后每个点的层次随着 DFS 变高。记 $gap[i]$ 表示高度为 $i$ 的点的个数,$d[i]$ 表示 $i$ 的层次,当结束 $i$ 的增广之后,遍历残量网络上 $i$ 的所有出边,找到 $d$ 最小的出点 $j$ ,令 $d[i]=d[j]+1$ ,如果没有出边,$d[i]=n$ 。当 $gap[i]=0$ 时出现断层,$S$ 和 $T$ 不连通,就可以停止了(这其实是 GAP 优化)。

和 Dinic 类似,ISAP 同样有当前弧优化。且最短路的修改具有连续性,每次不需要真的遍历残量网络出边,直接给 $d[i]$ 加一即可。

//Author:RingweEH
const int N=210,M=5e3+10;
const ll INF=0x7f7f7f7f;
struct Edge
{
    int to,nxt; ll val;
}e[M<<1];
int n,m,S,T,tot=1,head[N],dep[N],gap[N],nw[N];
ll mxflow=0;

void Add( int u,int v,ll w )
{
    e[++tot].to=v; e[tot].nxt=head[u]; head[u]=tot; e[tot].val=w;
    e[++tot].to=u; e[tot].nxt=head[v]; head[v]=tot; e[tot].val=0;
}

void BFS()
{
    memset( dep,-1,sizeof(dep) ); memset( gap,0,sizeof(gap) );
    dep[T]=0; gap[0]=1;
    queue<int> q; q.push( T );
    while ( !q.empty() )
    {
        int u=q.front(); q.pop();
        for ( int i=head[u]; i; i=e[i].nxt )
        {
            int v=e[i].to;
            if ( dep[v]>-1 ) continue;
            q.push( v ); dep[v]=dep[u]+1; gap[dep[v]]++;
        }
    }
}

int DFS( int u,ll sum )
{
    if ( u==T ) { mxflow+=sum; return sum; }
    ll res=0;
    for ( int i=nw[u]; i; i=e[i].nxt )
    {
        nw[u]=i; int v=e[i].to;
        if ( e[i].val && dep[v]+1==dep[u] )
        {
            int tmp=DFS( v,min(e[i].val,sum) );
            if ( tmp )
            {
                e[i].val-=tmp; e[i^1].val+=tmp;
                sum-=tmp; res+=tmp;
            }
            if ( sum==0 ) return res;
        }
    }
    gap[dep[u]]--; 
    if ( gap[dep[u]]==0 ) dep[S]=n+1;
    dep[u]++; gap[dep[u]]++;
    return res;
}

int main()
{
    n=read(); m=read(); S=read(); T=read();
    for ( int i=1; i<=m; i++ )
    {
        int u=read(),v=read(); ll w=read();
        Add( u,v,w );
    }

    BFS(); mxflow=0;
    while ( dep[S]<n ) 
    {
        memcpy( nw,head,sizeof(head) );  DFS( S,INF );
    }

    printf( "%lld\n",mxflow );

    return 0;
}

HLPP(最高标号预流推进)

推荐博客

前面的三种算法都是基于 增广路 的思想。

而这里是另一类:预流推进

预流推进思想:允许水流在非源汇的节点中暂时保存(称为 超额流 ),同时伺机将超额流 推送 出去。只要最后所有的节点超额流为 $0$ ,那么就是合法的。为了避免死循环,引入每个节点的 高度 ,只允许高度较高的节点向高度较低的推送。如果一个节点因为高度原因不能推送出去,那么就抬高这个高度,这个操作称为 重贴标签

HLPP算法流程:用 $e[v]$ 表示超额流,$h[v]$ 表示高度。

首先,将所有除了源点以外的节点高度设为 $0$ ,源点 $S$ 设为 $n$ ,并将 $S$ 的所有边都充满流量推送出去(放水)。将所有推送后超额流不为 $0$ 的节点加入以高度为关键字的优先队列中等待推送。

然后,每次取出对首 $u$ 并尝试推送:

  • 逐一检查 $u$ 的出边,如果某条边还有流量,并且另一端 $v$ 满足 $h[v]+1=h[u]$ ,那么这条边可以推送。
  • 推送流量不能超过边的容量,也不能超过 $e[u]$
  • 推送完毕后修改超额流,如果 $v$ 不在队列中那么加入

完成之后,如果 $e[u]>0$ ,那么说明需要对 $u$ 重贴标签。找到有流量并且另一端 $h[v]$ 最小的边,令 $h[u]=h[v]+1$ ,把操作完的 $u$ 加入优先队列。

直到队列为空。

虽然这样复杂度正确,为 $\mathcal{O}(n^2\sqrt m)$ ,但是需要一些优化才能在随机数据下和增广路算法相当。

  1. 可以通过一边 BFS 将每个点的初始高度设为到汇点的距离。(除了 $S$ )
  2. 如果一个点被重贴标签之后,原来的高度已经没有点了,那么高于它的点必然不能推到 $T$ ,所以可以将高度大于 $h[u]$ 并且小于 $n+1$ 的 $h$ 设为 $n+1$ ,以便尽快推给 $S$ 。也就是和 ISAP 一样的 GAP 优化。

注意 gap 大小要开两倍。


然而事实上博主的写法并不适合我这种大常数选手。于是跑到 LOJ 上去学习了一番最优解,得到了如下写法。

这写法长这样:

记录高度为 $i$ 的节点个数,具体节点,高度为 $i$ 的有超额流的节点,记录更改高度的总次数,记录最大高度;

每次重贴标签直接从 $T$ 开始重新对着残量网络 BFS;

一边往外流一边记录所有出边的端点高度最小值(为了有剩余超额流的时候直接更新高度);

断层就直接把所有高度比当前高的节点置为 INF ;

初始化源点无限流量,先重贴一遍,然后按照高度从高到低依次往外推流,如果更改高度的总次数大于某个阀值,那么就再重贴一遍。

具体可以看代码QWQ 跑得飞快。

//Author:RingweEH
#define pb push_back
const int N=1203,INF=0x3f3f3f3f;
struct Edge
{
    int to,nxt,val;
    Edge ( int _to,int _nxt,int _val ) : to(_to),nxt(_nxt),val(_val) {}
};
vector<Edge> g[N];
int n,m,S,T,h[N],cnt[N],work,ht,rest[N];
vector<int> las[N],gap[N];

void Add( int u,int v,int w )
{
    g[u].pb( Edge(v,g[v].size(),w) );
    g[v].pb( Edge(u,g[u].size()-1,0) );
}

void Update_height( int u,int nw )
{
    ++work;         //work记录更改高度的次数
    if ( h[u]^INF ) --cnt[h[u]];
    h[u]=nw; 
    if ( nw==INF ) return;
    ++cnt[nw]; ht=nw;    //cnt[i]记录高度为i的节点个数
    gap[nw].pb(u);          //gap[i]记录高度为i的节点
    if ( rest[u] ) las[nw].pb(u);   //las[i]记录高度为i且还有超额流的节点
}

void Relabel()      //重置高度
{
    work=0; memset( h,0x3f,sizeof(h) ); memset( cnt,0,sizeof(cnt) );
    for ( int i=0; i<=ht; i++ )
        las[i].clear(),gap[i].clear();
    h[T]=0; queue<int> q; q.push(T);
    while ( !q.empty() )        //每次重新BFS
    {
        int u=q.front(); q.pop();
        for ( Edge &e : g[u] )
            if ( h[e.to]==INF && g[e.to][e.nxt].val ) //如果还有流量且另一个端点没被更新过
            {
                q.push( e.to ); Update_height( e.to,h[u]+1 );   //设为到汇点的距离
            }
        ht=h[u];        //记录最大的一个高度
    }
}

void Push( int u,Edge &e )      //u的超额流通过边e往外流
{
    if ( rest[e.to]==0 ) las[h[e.to]].pb(e.to);     //如果没在里面,现在就要在了
    int del=min( rest[u],e.val );   
    e.val-=del; g[e.to][e.nxt].val+=del;
    rest[u]-=del; rest[e.to]+=del;
}

void Push_Flow( int u )
{
    int nh=INF;
    for ( Edge &e : g[u] )   
        if ( e.val )
            if ( h[u]==h[e.to]+1 )
            {
                Push( u,e );
                if ( rest[u]<=0 ) return;
            }
            else nh=min( nh,h[e.to]+1 );        
            //一边往外流一边以防万一要更新,收集最小值
    if ( cnt[h[u]]>1 ) Update_height( u,nh );       //没断层,直接更新
    else
        for ( int i=h[u]; i<N; i++ )        //断层了
        {
            for ( int j : gap[i] ) 
                Update_height( j,INF );
            gap[i].clear();
        }
}

int HLPP()
{
    memset( rest,0,sizeof(rest) );
    rest[S]=2147483647;
    Relabel();
    for ( Edge &e : g[S] )      //从源点往外推
        Push( S,e );
    for ( ; ~ht; --ht )
        while ( !las[ht].empty() )      //枚举高度,从高到低依次往外推
        {
            int u=las[ht].back(); las[ht].pop_back();
            Push_Flow( u );
            if ( work>20000 ) Relabel();        //如果改变得过多了那么就重新标记
        }
    return rest[T];
}

int main()
{
    n=read(); m=read(); S=read(); T=read();
    for ( int i=1,u,v,w; i<=m; i++ )
        u=read(),v=read(),w=read(),Add( u,v,w );
    printf( "%d\n",HLPP() );
}

2 - 最小割

可以参考这篇论文

概念&定理

对于一个网络流图 $G=(V,E)$ ,将所有点划分成 $S$ 和 $T=V-S$ ,其中源点 $s\in S$ ,汇点 $t\in T$ . 定义割 $(S,T)$ 的容量为所有 $S$ 到 $T$ 的边的容量之和。

最大流最小割定理 :最大流=最小割,即 $f(s,t)_{max}=c(S,T)_min$ 。证明

求方案:可以从源点 $s$ 开始 DFS ,每次走残量大于 $0$ 的边,找到所有 $S$ 点集内的点。

求割边数量:将容量变为 $1$ ,跑 Dinic 即可。

模型

有两个集合 $A,B$ 和 $n$ 个物品,第 $i$ 个物品放入 $A$ 产生花费 $a_i$ ,放入 $B$ 为 $b_i$ ,还有若干个限制 $(u_i,v_i,w_i)$ ,如果 $u_i$ 和 $v_i$ 不在同一个集合里花费 $w_i$ ,每个物品只能属于一个集合,求最小代价。

二者选其一 的最小割。对每个集合设置源点 $s$ 和汇点 $t$ ,第 $i$ 个点由 $s$ 连一条容量为 $a_i$ 的边,向 $t$ 连一条容量为 $b_i$ 的边,在 $u_i,v_i$ 之间连容量为 $w_i$ 的双向边。当源汇不相连的时候,代表这些点都选择了其中一个集合。如果将连向 $s$ 或者 $t$ 的边割开,表示不放在 $A$ 或者 $B$ ,如果物品间割开,表示不放在同一个集合。最小割就是最小花费。

3 - 费用流

每条边除了容量限制还有单位流量的费用 $w(u,v)$ 。当 $(u,v)$ 的流量为 $f(u,v)$ 时,花费 $f(u,v)\times w(u,v)$ .

研究问题:最小费用最大流

SSP

SSP(Successive Shortest Path)算法:在最大流的 EK 算法求解最大流的基础上,把 用 BFS 求解任意增广路 改为 用 SPFA 求解单位费用之和最小的增广路 即可。

相当于 把费用作为边权,在残存网络上求最短路

//Author:RingweEH
const int N=410,M=15010,INF=0x3f3f3f3f;
struct Edge
{
    int to,nxt,flow,cap;
    Edge ( int _to=0,int _nxt=0,int _flow=0,int _cap=0 ) :
        to(_to),nxt(_nxt),flow(_flow),cap(_cap) {}
}e[M<<1];
int n,m,S,T,tot=1,head[N];
int pre[N],dis[N],mxflow,mncost;
bool vis[N];

void Add( int u,int v,int fl,int cap )
{
    e[++tot]=Edge(v,head[u],fl,cap); head[u]=tot;
    e[++tot]=Edge(u,head[v],0,-cap); head[v]=tot;
}

bool BFS()
{
    for ( int i=1; i<=n; i++ )
        vis[i]=0,dis[i]=INF;
    queue<int> q; q.push( S ); dis[S]=0;
    while ( !q.empty() )
    {
        int u=q.front(); q.pop(); vis[u]=0;
        for ( int i=head[u]; i; i=e[i].nxt )
        {
            int v=e[i].to; 
            if ( dis[v]>dis[u]+e[i].cap && e[i].flow )
            {
                dis[v]=dis[u]+e[i].cap; pre[v]=i;
                if ( !vis[v] ) vis[v]=1,q.push( v );
            }
        }
    }
    return dis[T]!=INF;
}

void Update()
{
    int mn=INF;
    for ( int i=T; i^S; i=e[pre[i]^1].to )
        bmin( mn,e[pre[i]].flow );
    for ( int i=T; i^S; i=e[pre[i]^1].to )
    {
        e[pre[i]].flow-=mn; e[pre[i]^1].flow+=mn;
        mncost+=mn*e[pre[i]].cap;
    }
    mxflow+=mn;
}

int main()
{
    n=read(); m=read(); S=1; T=n;
    for ( int i=1,u,v,f,c; i<=m; i++ )
        u=read(),v=read(),f=read(),c=read(),Add( u,v,f,c );

    while ( BFS() ) Update();

    printf( "%d %d\n",mxflow,mncost );
}

类 Dinic

在 Dinic 算法的基础上进行改进,把 BFS 求分层图 改为用 SPFA求一条单位费用之和最小的路径(由于有负权的反向边,不能直接用 Dijkstra ),相当于 把 $w(u,v)$ 当做边权在残量网络上求最短路

优化:使用 Primal-Dual 原始对偶算法,将 SPFA 改成 Dijkstra (有需要看 这篇 ,不过 代码也不长?

复杂度上界:$\mathcal{O}(nmf)$

//Author:RingweEH
const int N=410,M=15010,INF=0x3f3f3f3f;
struct Edge
{
    int to,nxt,flow,cap;
    Edge ( int _to=0,int _nxt=0,int _flow=0,int _cap=0 ) :
        to(_to),nxt(_nxt),flow(_flow),cap(_cap) {}
}e[M<<1];
int n,m,S,T,tot=1,head[N],dis[N],mxflow,mncost,nw[N];
bool vis[N];

void Add( int u,int v,int fl,int cap )
{
    e[++tot]=Edge(v,head[u],fl,cap); head[u]=tot;
    e[++tot]=Edge(u,head[v],0,-cap); head[v]=tot;
}

bool BFS()  
{
    for ( int i=1; i<=n; i++ )
        dis[i]=INF,vis[i]=0;
    queue<int> q; q.push( S ); dis[S]=0; nw[S]=head[S]; vis[S]=1;
    while ( !q.empty() )
    {
        int u=q.front(); q.pop(); vis[u]=0;
        for ( int i=head[u]; i; i=e[i].nxt )
        {
            int v=e[i].to;
            if ( e[i].flow && dis[v]>dis[u]+e[i].cap )
            {
                nw[v]=head[v]; dis[v]=dis[u]+e[i].cap;
                if ( !vis[v] ) vis[v]=1,q.push(v);
            }
        }
    }
    return dis[T]!=INF;
}

int DFS( int u,int sum )        
{
    if ( u==T ) return sum;
    vis[u]=1; int res=0;
    for ( int i=nw[u]; i && sum; i=e[i].nxt )
    {
        nw[u]=i; int v=e[i].to;
        if ( !vis[v] && e[i].flow && (dis[v]==dis[u]+e[i].cap) )
        {
            int tmp=DFS( v,min(sum,e[i].flow) );
            if ( tmp )
            {
                e[i].flow-=tmp; e[i^1].flow+=tmp;
                res+=tmp; sum-=tmp; mncost+=e[i].cap*tmp;
            }
        }
    }
    vis[u]=0; return res;
}

int main()
{
    n=read(); m=read(); S=1; T=n;
    for ( int i=1,u,v,f,c; i<=m; i++ )
        u=read(),v=read(),f=read(),c=read(),Add(u,v,f,c);

    while ( BFS() ) mxflow+=DFS(S,INF);

    printf( "%d %d\n",mxflow,mncost );

    return 0;
}

4 - 上下界网络流

解决每条边流量有上下界限制的网络流。

无源汇上下界可行流

问题 :有 $n$ 个点, $m$ 条边,每条边有一个流量下界 $low$ 和流量上界 $up$ ,求可行方案使得所有点满足流量平衡的前提下,所有边满足流量限制。

思路 :两个限制同时考虑会很麻烦,先考虑下界。

先给每条弧加一个 $low$ 的流量下界,那么这个限制就没了。但是现在这个图不一定满足流量平衡,称为初始流

应该在这张图上再添加一个附加流,使得初始流和附加流之和满足流量平衡。显然,每条弧的附加流上界是 $up-low$ ,所以不妨在建边的时候直接设容量为 $up-low$ ,提出 $low$ . 设现在图中点的流入流出量之差为 $c[i]$ 。

设置虚拟源汇,源点向每个 $c[i]>0$ 的点连边,容量为 $c[i]$ ;每个 $c[i]<0$ 的点向汇点连边,容量为 $-c[i]$ . 如果某个点 $x$ 的 $c[x]>0$ ,那么就从源点给它 $c[x]$ 的流,这些流在原本的边上流动,直到流到某个 $c[y]<0$ 的点 $y$ ,通过这里流出。之后留在原有边上的流量就是附加流。

如果附加流加上初始流之后流量守恒,那么直接与虚拟源点和汇点相连的边应该都满流。由于 $c[]$ 之和为 $0$ ,所以新图中的最大流要等于 $\sum [c[i]>0]c[i]$ . 如果成立那么就存在可行流。求流量就直接找每条边的反向弧即可。

模板

//Author:RingweEH
int main()
{
    n=read(); m=read(); S=n+1; T=S+1;
    for ( int i=1; i<=m; i++ )
    {
        int u=read(),v=read(),lower=read(),upper=read();
        Add( u,v,upper-lower ); c[v]+=lower; c[u]-=lower;
        low[i]=lower;
    }

    int Sum=0;
    for ( int i=1; i<=n; i++ )
    {
        if ( c[i]>0 ) Add( S,i,c[i] ),Sum+=c[i];
        if ( c[i]<0 ) Add( i,T,-c[i] );
    }

    while ( BFS() ) mxflow+=DFS(S,INF);

    if ( mxflow==Sum )
    {
        printf( "YES\n" );
        for ( int i=3,j=1; j<=m; i+=2,j++ )
            printf( "%lld\n",e[i].flow+low[j] );
    }
    else printf( "NO\n" );

    return 0;
}

有源汇上下界可行流

源点和汇点流量不守恒,但是可以手动守恒:从 $T$ 向 $S$ 连一条下界为 $0$ ,上界为 INF 的边,跑无源汇即可。流量就是 $T$ 到 $S$ 的反向弧流量。

有源汇上下界最大流

在有源汇上下界可行流的基础上,在残量网络上跑最大流,相加即可。显然这样不会超出上下界。

具体实现:用虚拟源汇跑完之后,再用实际的源汇跑跑一遍最大流即可。

原理:原图中跑完第一次,剩下的就是残量网络,且可行流保存在 $T$ 到 $S$ 的反向边中。这时候跑 $S$ 到 $T$ 的最大流,就得到了残量网络最大流+将 $ST$ 反向边退回去的流量,也就是最大流加上可行流。

模板

//Author:RingweEH
int main()
{
    n=read(); m=read(); int s=read(),t=read(); S=n+1,T=S+1;
    for ( int i=1; i<=m; i++ )
    {
        int u=read(),v=read(),lower=read(),upper=read(); low[i]=lower;
        Add( u,v,upper-lower ); c[v]+=lower; c[u]-=lower;
    }

    int Sum=0; Add( t,s,INF );
    for ( int i=1; i<=n; i++ )
    {
        if ( c[i]>0 ) Add( S,i,c[i] ),Sum+=c[i];
        if ( c[i]<0 ) Add( i,T,-c[i] );
    }
    while ( BFS() ) mxflow+=DFS(S,INF);
    if ( mxflow!=Sum ) { printf( "please go home to sleep" ); return 0; }
    S=s; T=t; mxflow=0;
    while ( BFS() ) mxflow+=DFS(S,INF);
    printf( "%d\n",mxflow );

    return 0;
}

有源汇上下界最小流

和最大流一样,先求出可行流,然后考虑在此基础上减去最大的流量,使之仍然守恒。

如果我们找到一条 $T\to S$ 的增广路,那么就说明去掉这条增广路上的流量,仍然守恒。那么就直接从 $T$ 到 $S$ 跑一遍最大流,用可行流减去流量即可。注意这里 不能 保留 $T$ 到 $S$ 的 INF 边。

模板

//Author:RingweEH
int main()
{
    n=read(); m=read(); int s=read(),t=read(); S=n+1,T=S+1;
    for ( int i=1; i<=m; i++ )
    {
        int u=read(),v=read(); ll lower=read(),upper=read(); 
        low[i]=lower; Add( u,v,upper-lower ); c[v]+=lower; c[u]-=lower;
    }

    int Sum=0;
    for ( int i=1; i<=n; i++ )
    {
        if ( c[i]>0 ) Add( S,i,c[i] ),Sum+=c[i];
        if ( c[i]<0 ) Add( i,T,-c[i] );
    }
    Add( t,s,INF );
    while ( BFS() ) mxflow+=DFS(S,INF);
    if ( mxflow!=Sum ) { printf( "please go home to sleep" ); return 0; }
    mxflow=e[tot].flow;
    S=t; T=s; e[tot].flow=e[tot^1].flow=0;
    while ( BFS() ) mxflow-=DFS(S,INF);
    printf( "%lld\n",mxflow );

    return 0;
}


新鲜事 原文

RingweEH
10个月前
04年的USACO国家队选手全把这题给过了 这就是题面/jk
图片


新鲜事 原文

RingweEH
10个月前
数数天下第一!
图片



RingweEH
10个月前

希望能对做这套题的人有所帮助,去掉部分真的没什么意义的题。

前置知识:网络流


更好的阅读体验&目录链接

LOJ 真好,代码公开省了我很多空间QWQ


网络流24题虽然有好题,但是也有莫名其妙的……并没有想象中那么值得一做。

提交网站挂在LOJ,倒是很建议做完之后参考一下最优解为什么跑那么快。

以下是对于题目的类型归类,加删除线的是我感觉真的不用再做的题。不过评价可能有部分基于题目顺序。

二分图匹配 :搭配飞行员,圆桌聚餐 ,最小路径覆盖

美妙拆点 :最长递增子序列,餐巾计划,数字梯形 ,星际转移,航空路线

美妙拆边 :深海机器人,火星探险(和深海机器人类似,但是如果要练习输出方案可以做这个)

最小割 :太空飞行计划,方格取数,骑士共存(与方格取数类似)

费用流分配问题 ,运输问题,最长 k 可重区间集(比后面那题少了个特判) ,最长 k 可重线段集

感觉过于基础的题 :试题库

莫名其妙不用网络流的题 :魔术球(网络流可做,但是第一反应贪心),软件补丁(状压最短路),负载平衡(均分纸牌),孤岛营救(状压最短路),汽车加油行驶

搭配飞行员

一架飞机需要一正一副两个飞行员,给出若干对正副飞行员(表示可以同机飞行),求最多可以配多少对。

Solution

很显然的二分图匹配。让我想跑匈牙利 不你不行。

考虑一个很基础的建模:

  • 建立超级源点 $S$ ,向所有正飞行员连容量为 $1$ 的有向边;
  • 建立超级汇点 $T$ ,向所有负飞行员连容量为 $1$ 的有向边;
  • 如果两个飞行员能搭配,那么从正飞行员向副连一条容量为 $1$ 的有向边。

然后跑最大流即可。

代码链接

太空飞行计划

有 $m$ 个实验,第 $j$ 个实验用到了器材集合 $R_j$ ,配置仪器 $I_k$ 的费用为 $c_k$ ,实验 $E_j$ 有收益 $p_j$ ,求最大的净收入。

Solution

证明 建图方式:

  • 起点向实验连流量为费用的边
  • 实验向仪器连流量为 INF 的边
  • 仪器向终点连流量为费用的边

答案就是总费用减去最小割。对于输出方案,发现 Dinic 跑 BFS 的时候,有层次标记的点就是残量网络上还剩下的点,而一个点流完了就说明仪器的费用不比收获小,那还不如不取,所以从源点 $s$ 开始的 BFS 之后,有标记的点就相当于选择的点。那么只需要正常执行完之后根据 $dis$ 输出即可。

代码链接 这道题的 IO 简直是杀人……

最小路径覆盖

给定有向图 $G$ ,设 $P$ 是 $G$ 的一个简单路集合,如果 $V$ 中每个点恰好在 $P$ 的一条路上,称 $P$ 是 $G$ 的一个路径覆盖。 $P$ 中路径可以长度可以为 $0$ . $G$ 的最小路径覆盖是所含路径条数最少的路径覆盖。求最小路径覆盖。

Solution

奇妙的模型,拆点转化成二分图匹配。我们将每个点 $i$ 拆成一个左部点 $x_i$ 和一个右部点 $y_i$ ,对于每一条边 $(i,j)$ ,连边 $(x_i,y_j)$ . 注意到二分图的任何一个匹配都对应了原图中的一个路径构造方案,如果没有匹配那么就是路径数=点数。而每增加一个匹配,就减少了一条路径,求最小路径覆盖就是要求最大匹配,跑最大流即可。

对于求方案,只需要在求出匹配之后沿着匹配边跳即可。

代码链接

魔术球

有 $n$ 根柱子,依次放入编号为 $1,2,3,\cdots $ 的球。每次只能在顶端放,且同一根中任何两个相邻球的编号之和为完全平方数。

求最多能放多少个球。

Solution

Link

圆桌聚餐

有 $m$ 个单位的代表参加会议,第 $i$ 个单位有 $r_i$ 个人。一共有 $n$ 张餐桌,每张可以有 $c_i$ 个人,且同一个单位的人不能在同一个餐桌。求一个合法的方案。

Solution

建立超级源汇,以单位为左部点,餐桌为右部点,$S$ 向所有左部点连容量为 $r_i$ 的边,每个左部点向所有右部点连容量为 $1$ 的边,每个右部点向 $T$ 连容量为 $c_i$ 的边。跑最大流(或者说最大匹配),如果最大匹配不等于人数那么无解,否则输出方案即可。

代码链接

最长递增子序列

给定正整数序列 $x_1\sim x_n$ ,计算其最长递增子序列的长度 $s$ ,求方案数,并计算如果能多次使用 $x_1,x_n$ 的方案数。

Solution

第一问:直接 $\mathcal{O}(n^2)$ DP。

第二问:把每个点拆成 $i,i+n$ ,然后将之间连一条 $1$ 的边,如果 $i$ 后面能接 $j$ (就是 $a[i]\leq a[j],f[i]+1=f[j]$ ),就连接 $i+n,j$ ,$S$ 与 $f[i]=1$ 的点相连,$f[i]=ans$ 的点与 $T$ 相连, 跑最大流。

第三问:依然拆点,如果 $i\neq 1,n$ 那么连接 $(i,i+n,1)$ ,否则是 $(i,i+n,n)$ (因为可以多次使用);如果 $f[i]=1$ 且 $i\neq 1$ ,连接 $(S,i,1)$ ,如果 $i=1$ 那么 $(S,i,n)$ ;如果 $f[i]=ans$ ,且 $i\neq n$ ,那么 $(i+n,T,1)$ ,如果 $i=n$ 那么 $(i+n,T,n)$ .

代码链接

试题库

有 $n$ 道题,$k$ 个标签,每道有若干个标签,要求取出 $m$ 道题使得组成的试卷包含指定类型的试题。无解 No Solution! .

Solution

$S$ 向标签连“该类型选择题数”的边,标签向每个属于它的试题连容量为 $1$ 的边,然后试题再连向 $T$ 即可。

一开始脑子抽了居然以为 $\sum k[i]\neq m$ ……

代码链接

方格取数

$m\times n$ 的方格,每个方格有一个正整数。从中取数,使得任意两个没有公共边,且取出的数总和最大。

Solution

感觉我对最小割异常迟钝……

先对这个玩意儿黑白染色(其实就是作为左部点和右部点),然后每个黑色格子向四联通的格子连 INF 的边(不能同时选),$S$ 向左部连点权,右部向 $T$ 连点权,答案就是总和减去最小割,跑最大流即可。

代码链接

餐巾计划

一个餐厅在连续的 $n$ 天里,第 $i$ 天需要 $r_i$ 块餐巾,新的餐巾价格为 $P$ ,洗一块旧的餐巾需要 $M$ 天,价格为 $F$ ,或者用 $N$ 天,价格为 $S$ ,求满足需求的最小花费。

Solution

美妙费用流。考虑拆点,把一天拆成新的毛巾(买的)和旧的毛巾(洗好的)。

  • 从 $S$ 向所有干净点连费用为 $P$ ,流量 INF 的边(购买);
  • 从干净点向 $T$ 连费用为 $0$ ,流量为 $r[i]$ 的边(提供);
  • 从 $S$ 向脏点连费用为 $0$ ,流量为 $r[i]$ 的边(丢出来的处理物);
  • 从脏点向 $m$ 天后的干净点连费用为 $F$ ,流量为 INF 的边(快洗);
  • 从脏点向 $n$ 天后的干净点连费用为 $s$ ,流量为 INF 的边(慢洗);
  • 从脏点往下一个脏点连费用为 $0$ ,流量为 INF 的边。

跑费用流即可。

代码链接

软件补丁

有 $n$ 个错误和 $m$ 个补丁,对于每个补丁,当且仅当错误包含 $B_1(i)$ 中的所有错误,不包含 $B_2(i)$ 的任何错误时可以使用,效果是修复错误集合 $F_1(i)$ ,加入错误集合 $F_2(i)$ ,每个补丁有耗时。求没有错误的最小耗时。

Solution

$\huge \color{yellowgreen}{去你的网络流24题}$

这明明是状压最短路……

$n\leq 20,m\leq 100$ ,所以可以直接把 $20$ 位压成一个状态,表示当前有哪些错误。从 $2^n-1$ 开始,跑最短路,每次枚举有哪些补丁可以用即可。

代码链接

数字梯形

给定一个 $n$ 行数字组成的数字梯形,第一行有 $m$ 个数字。分别求出满足以下规则的最大总和:

  1. 从顶至底 $m$ 条路径互不相交
  2. 从顶至底 $m$ 条路径仅在节点处相交
  3. 从顶至底 $m$ 条路径仅在节点处或边相交

Solution

第一问:每个点拆成两个点 $X,Y$ ,容量为 $1$ ,费用为这个数,每个点的 $Y$ 向能到达的 $X$ 点连边。$S$ 向第一层的 $X$ 连边,最后一层的 $Y$ 向 $T$ 连边,容量为 $1$ ,费用为 $0$ ,跑最大费用最大流。

第二问:不拆点,直接连边,但是最后一层的点直接连 $T$ ,容量为 INF ,费用为这个数。

第三问:直接选,没有限制,相当于所有边的容量都是 INF。

好好的问题偏要 $3$ 个一起来增加码量 (ノ`Д)ノ

代码链接

运输问题

有 $m$ 个仓库和 $n$ 个零售店,第 $i$ 个仓库有 $a_i$ 的货物,第 $j$ 个零售店需要 $b_j$ 的货物,供需平衡。从第 $i$ 个仓库运送一单位货物到第 $j$ 个零售店需要 $c_{i,j}$ 的费用,求满足供需的最少费用。

Solution

最小费用最大流。

  • $S$ 向 $m$ 个仓库连流量为 $a_i$ ,费用为 $0$ 的边
  • $m$ 个仓库向 $n$ 个零售店连流量为 INF ,费用为 $c_{i,j}$ 的边
  • $n$ 个零售店向 $T$ 连流量为 $b_j$ ,费用为 $0$ 的边。

代码链接

分配问题

有 $n$ 件工作要分配给 $n$ 个人做。第 $i$ 个人做第 $j$ 件工作产生的效益为 $c_{i,j}$ 。试设计一个将 $n$ 件工作分配给 $n$ 个人做的分配方案,使产生的总效益最大。

Solution

上一题的简化版。把所有流量改成 $1$ 即可。

代码链接

负载平衡

有 $n$ 个环形排列的仓库,每个都有一定的货物。求最少的搬运量使得库存相同(只能在相连间搬运)。

Solution

均分纸牌裸题。

代码链接

最长 k 可重区间集

给定 $n$ 个开区间的集合 $I$ 和一个正整数 $k$ ,从中选取开区间集合 $S\subseteq I$ ,所得实直线 $L$ 的任何一点 $x$ ,$S$ 中包含 $x$ 的开区间个数不超过 $k$ ,且 $\sum_{z\in S}|z|$ 最大。求最大值。

Solution

显然并不是所有点都有用,只需要保留所有端点即可。所以首先要离散化,这样点的个数至多为 $2n$ .

每个点向下一个点连边,容量为 $k$ ,费用为 $0$ 。对于每个区间 $l,r$ ,从 $l$ 向 $r$ 连容量为 $1$ ,费用为区间长度的边。最后,$S$ 向第一个点连容量为 $k$ ,费用为 $0$ 的边限流,最后一个点向 $T$ 同理,直接跑最大费用最大流即可。

代码链接

星际转移

有 $n$ 个点和 $m$ 条船,每条船有容量 $H_i$ ,一次行驶费用为 $1$ ,且周期性停靠一系列点。求从 $S$ 到 $T$ 最大流至少为 $k$ 的最小费用。

Solution

哦这该死的周期没法下手。所以只能一天一天来。这样就需要枚举答案。

其实枚举答案不需要二分。如果逐个枚举能够在原先的残量网络上加边,二分要重新建图,效率反而不如直接枚举。

但是这样对于“周期”还是没法连边,所以考虑拆点,把一个点按“点+秒数”拆开,然后随着枚举的答案新建对于新的一秒的一套点。

源点 $S$ 向所有时间点的起点连容量为 INF,费用为 $0$ 的边;同理,所有时间的终点向 $T$ 连容量为 INF ,费用为 $0$ 的边。

每个点向下一秒的自己连容量为 INF ,费用为 $0$ 的边。

对于每一艘船,(如果停靠在了当前点)向下一秒的下一个点连容量为 $H_i$ ,费用为 $1$ 的边。

然后每次跑最小费用最大流即可。注意,这里的终点流量是至少为 $k$ .

一点点小优化:由于我们已经枚举了答案,其实并不需要跑费用流,直接最大流就好了我不对劲

代码链接

孤岛营救

有一个 $n\times m$ 的方格,四个方向上相邻的两个单元格可能互通,可能有锁,可能不相通。有一些单元格中有钥匙。所有门分为 $P$ 类,打开同一类的钥匙相通,不同类的钥匙可能不同。求从 $(1,1)$ 到 $(n,m)$ 的最小时间,移动一格速度为 $1$ .

Solution

看到题完全不知道怎么网络流,数据范围很小倒是可以暴搜。真就不是网络流啊草 我还期待着有什么高妙建模呢TNT

直接状压钥匙,最短路就好了……

代码链接

航空路线

给定一张航空图,图中顶点代表城市,边代表直通航线,找出一条满足条件且途径城市最多的旅行路线。

  1. 从最西端城市出发,单向从西向东途经若干城市到达最东端城市,然后再单向从东向西飞回起点(可以途径)
  2. 除起点外所有城市只能访问一次

求出答案和路线。

Solution

拆点。对于两个拆分后的点,连 $x_1\to x_2$ ,流量为 $1$ ,费用为 $1$ 的边,除了起点和终点流量为 $2$ . 对于原图的边直接连出点和入点即可。当最大流等于 $2$ 时,最大花费减去 $2$ 就是经过的最大节点数。注意特判 $1\to n$ .

输入字符串是真的一点都不想写……

代码链接

汽车加油行驶

题面太长了自己看。

Solution

?$100\times 100$ 的网格图让我跑网络流?不存在的。这垃圾24题到底是谁出的啊。

代码链接

深海机器人

给定一张带边权的网格图和多个机器人(及其出发点和目标),每个人都向东或向北走,位置可以重合。每个边权由第一次经过的人拿走,计算最优方案下能获得的最大边权。$P,Q\leq 15$ .

Solution

写出数据范围就是要说明,极其小的网格图也是能跑网络流的(

终于出现了一道拆边题QWQ。显然,每条边都能经过无数次,但每条边都只能有一次贡献,那么可以拆成容量为 $1$ 费用为边权的边,和一条容量 INF 费用为 $0$ 的边。

拆完之后,多起点多终点,分别连 $S$ 和 $T$ ,跑最大费用最大流即可。

如果你 WA9 了不妨看看输入输出,挺坑人的。

代码链接

火星探险

在上一题中增加障碍物的限制,固定起点和终点,并且一定要全部到达。

Solution

???无聊。

代码链接

骑士共存

给定一个 $n\times n$ 的棋盘,有障碍,计算最多能放置几个互不攻击的马。

Solution

和方格取数类似,注意到能相互攻击的马一定是不同色的格子上的。

黑白染色之后,对于所有黑色点,向 $8$ 联通的格子连容量为 INF 的边,$S$ 向黑色点连容量为 $1$ 的边,白色点向 $T$ 连容量为 $1$ 的边,跑最小割即可。

为什么 $200\times 200$ 的网格图能跑网络流啊……不懂了哦,诶。

代码链接

最长 k 可重线段集

给定平面 $\text{xoy}$ 上 $n$ 个开线段组成的集合 $I$ 和一个正整数 $k$ ,从中选出 $S\in I$ 使得在 $x$ 轴上任意一点 $p$ ,$S$ 中与 $x=p$ 相交的开线段个数不超过 $k$ ,且长度和最大。

Solution

?这和“最长 k 可重区间集”有区别吗?并没有。

不过是当线段平行于 $y$ 轴的时候会出现自环,所以要先 $\times 2$ 然后再判断,最后离散化。

代码链接




RingweEH
11个月前

网上和洛谷绝大部分讲解模拟退火的实现都是错误的……这里给出我的写法,如有错误还请指正。

其实是希望白嫖巨佬帮我检查

Statement

给定一个二维平面和 $N$ 个圆表示建筑,$M$ 个点表示敌人。可以任意放置一个半径任意的圆,使得覆盖尽可能多的敌人,且不会损伤建筑。

Solution

注意到,如果将问题转化成一个判定性的问题,即给定一个圆,判断覆盖了多少个点以及有没有损伤建筑。也就是说,checker 是很好写的。

那么我们可以使用随机化算法来解决这个问题,多次执行以及调试参数之后能达到很高的正确率。

模拟退火讲解看这里

Code

//Author:RingweEH
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <ctime>
#define ll long long
#define db double
using namespace std;
int min( int a,int b ) { return (a<b) ? a : b; }
int max( int a,int b ) { return (a>b) ? a : b; }
void bmin( int &a,int b ) { a=(a<b) ? a : b; }
void bmax( int &a,int b ) { a=(a>b) ? a : b; }
int read()
{
    int x=0,w=1; char ch=getchar();
    while ( ch>'9' || ch<'0' ) { if ( ch=='-' ) w=-1; ch=getchar(); }
    while ( ch<='9' && ch>='0' ) { x=x*10+ch-'0'; ch=getchar(); }
    return x*w;
}

const int N=11,M=1010;
const double delta=0.996,Te=1e-10;          //D和最终温度
int n,m,x[N],y[N],r[N],p[M],q[M],R,ansout=0;
double ansx,ansy;

double dis( double ax,double ay,double bx,double by )       //求两点间距离
{
    double res=(bx-ax)*(bx-ax)+(by-ay)*(by-ay);
    res=sqrt(res);
    return res;
}

int calc( double xx,double yy )         //估价函数
{
    double nowr=R;
    for ( int i=1; i<=n; i++ )
        nowr=min( nowr,dis(xx,yy,x[i],y[i])-(double)r[i] );
    int cnt=0;
    for ( int i=1; i<=m; i++ )
        if ( dis(xx,yy,p[i],q[i])<=nowr ) cnt++;
    return cnt;
}

void SA()
{
    double T=6000;      //初始温度
    int ans=0;
    while ( T>Te )
    {
        double nowx=ansx+(rand()*2-RAND_MAX)*T;
        double nowy=ansy+(rand()*2-RAND_MAX)*T;
        int nowans=calc( nowx,nowy );
        int DelE=nowans-ans;
        if ( DelE>0 ) ansx=nowx,ansy=nowy,ans=nowans,ansout=max( ansout,ans );
        //更优的解,必然接受
        else if ( exp(DelE/sqrt(T))>(double)rand()/1215 ) ansx=nowx,ansy=nowy,ans=nowans;
        //按概率接受,保证了越到后期,和最优解的差距越大,越难被接受
        T*=delta;
    }
}

int main()
{
    srand(time(0)); ansx=ansy=0;
    n=read(); m=read(); R=read();
    for ( int i=1; i<=n; i++ )
        x[i]=read(),y[i]=read(),r[i]=read();
    for ( int i=1; i<=m; i++ )
        p[i]=read(),q[i]=read(),ansx+=x[i],ansy+=y[i];

    ansx/=m; ansy/=m; ansout=calc( ansx,ansy );
    while ( (double)clock()/CLOCKS_PER_SEC<=0.85 ) SA();

    printf( "%d",ansout );
}



RingweEH
11个月前

网络流24题,就不都水一篇题解了QWQ 但是这题的贪心做法比较有意思,所以就写一写,网上好像找不到比较完整的证明。

更好的阅读体验

众所周知,网络流24题不需要网络流(doge)。

Statement

有 $n$ 根柱子,依次放入编号为 $1,2,3,\cdots $ 的球。每次只能在顶端放,且同一根中任何两个相邻球的编号之和为完全平方数。

求最多能放多少个球。

Solution

$\color{black}{小}\color{red}{卷猫}$ 曰:可以枚举答案转化为判定性问题。

那么就二分最多能放的个数,然后对于所有 $i+j=k^2(i<j)$ 的东西连边,跑最小路径覆盖即可。


但是!这道题还有更为优美的性质:贪心。也就是在已有的柱子上,能放就放,放不了新开,这样就是最优解。

这篇博客 给出了对于贪心正确性的证明,首先得到贪心的答案是
$$
f(n)=
\begin{cases}
(n^2-1)/2+n & n\equiv 1(\bmod 2)\\
(n^2-2)/2+n & n\equiv 0(\bmod 2)
\end{cases}
$$
如果最终答案比 $f(n)$ 大,那么至少放了 $f(n)+1$ 个球。

当 $n\equiv 1(\bmod 2)$ 时,即 $(n^2-1)/2+n+1$ 个。(另一种同理)

在 $1\sim (n^2-1)/2+n+1$ 个数中,最后 $n+1$ 个数最大和为 $n^2+2n<(n+1)^2$ ,最小和为 $n^2+2>n^2$ ,所以这 $n+1$ 个数必定属于 $n+1$ 个柱子,而不可能在 $n$ 个柱子中放下。于是贪心的答案就一定正确。

但是博客并没有给出 $f(n)$ 的通项式证明。

1 3 6 10 15 21 28 36 45 55
2 7 9 16 20 29 35 46 54
4 5 11 14 22 27 37 44 56
8 17 19 30 34 47 53
12 13 23 26 38 43 57
18 31 33 48 52
24 25 39 42 58
32 49 51
40 41 59
50

观察上面 $n=10$ 的情况,不妨设第 $i$ 个柱子最底下的数为 $g[i]$ ,根据贪心实现和上面的式子,等价于证明 $g[i]=\lfloor i^2/2\rfloor$ (当 $i>2$ 时)(事实上,这是数列 A007590 )。那么我们需要证明的就是 $\lfloor (n-1)^2/2\rfloor+1\sim \lfloor n^2/2\rfloor-1$ 之间的数可以被 $n-1$ 个柱子放下,而 $\lfloor n^2/2\rfloor$ 不行。不妨增设一个额外条件:在放上这 $n$ 个数之前,$n-1$ 个柱子顶端的数都是当前放好的最大的 $n-1$ 个数。

假设这个结论对 $n-1$ 成立。考虑 $n$ 。

如果 $n$ 为偶数,注意到有 $\lfloor (n-1)^2/2\rfloor +1+\lfloor (n-1)^2/2\rfloor=(n-1)^2$ ,那么 $\lfloor (n-1)^2/2\rfloor +1\sim \lfloor n^2/r\rfloor -1$ 的任何一个数都能和顶端的 $n-1$ 个数配对,但 $\lfloor n^2/2\rfloor$ 不能和其中任何一个配对。这样的情形对于偶数 $n$ 显然成立。

如果 $n$ 为奇数,有 $\lfloor (n-1)^2/2\rfloor +1+\lfloor (n-1)^2/2\rfloor-1=(n-1)^2$ ,那么 $\lfloor (n-1)^2/2\rfloor +1\sim \lfloor n^2-1\rfloor$ 都能和 $\lfloor (n-2)^2/2\rfloor+1\sim \lfloor (n-1)^2/2\rfloor-1$ 配对,此时上一组剩下的 $\lfloor (n-1)/2\rfloor$ 和当前剩下的 $\lfloor n^2/2\rfloor$ (也就是新的柱子的顶端)分别是顶端的数中的最小、最大值,并且依然满足顶端的数是最大的 $n$ 个数。

根据归纳假设,结论对任意 $n$ 都成立。

代码链接




RingweEH
11个月前

更好的阅读体验

不愧是大常数选手,AcWing 无论原题还是加强都要开 O2 才能过去 TAT

另外,希望 y总有空的话能出个加强版?QWQ

Statement

给定一个长度为 $n$ 的序列,求前 $k$ 大的区间异或和。

$1\leq n\leq 5e5,1\leq k\leq \min(\frac{n(n-1)}{2},2e5),0\leq a_i<2^{32}$

Solution

虽然是十二省联考,但是题不难,也不是很毒瘤。

考虑区间异或和显然可以转化成两个前缀和的异或,那么现在的问题就变成了求前 $k$ 大的异或对。由于这里是有序对,我们可以在开头把 $k\times 2$ ,最后再让 $ans/=2$ ,这样就可以直接统计无序点对了。

题目中有 $a_i<2^{32}$ 的限制,容易想到用 Trie 来处理二进制数位。

首先,对于每个右端点,将使异或和取到最大值的左端点位置+异或和放进堆里。

然后,每次显然是取堆顶的一对。考虑如何在取出之后放入该右端点的次大值。一个显然的想法是把之前的删除,但是这样时空和实现都很麻烦。

考虑一个更简单的做法:其实 Trie 上不一定只能查询最值!我们也可以在 Trie 上用类似平衡树查询第 $p$ 大的思想来找特定串的第 $k$ 大异或和。具体做法:在向 Trie 中插入的时候顺便统计子树大小。对于一个原串在 Trie 上走到了 $g[pos][ch]$ 的点,找最大值的时候是往 $g[pos][ch\oplus 1]$ 走,由于是从高位到低位,所以节点 $g[pos][ch\oplus 1]$ 子树中的任何串,和原串的异或和都比 $g[pos][ch]$ 中的串要大,那么如果当前要求第 $p$ 大的异或和,而 $siz[g[pos][ch\oplus 1]]<p$ ,显然答案应该在 $g[pos][ch]$ 中,那么 $pos-=siz[g[pos][ch\oplus 1]]$ ,然后向 $g[pos][ch]$ 走;否则加上当前位的贡献 $|=1<<i$ ,向 $g[pos][ch\oplus 1]$ 走。代码如下:

 if ( siz[g[pos][ch^1]]<p ) p-=siz[g[pos][ch^1]],pos=g[pos][ch];
else res|=1ll<<i,pos=g[pos][ch^1];

这样就只需要记录所有右端点当前用到了第几大 $rk[i]$ ,在弹出一个右端点的时候 $rk[i]++$ ,并查询对应 $rk[i]$ 的异或和,插回堆里面即可。

Code

//Author:RingweEH
const int N=500010,M=N*35;
struct Node
{
    int pos; ll val;
    Node ( int _pos=0,ll _val=0 ) : pos(_pos),val(_val) {}
    bool operator < ( const Node &tmp ) const { return val<tmp.val; }
};
priority_queue<Node> q;
int n,k,tot,rk[N],g[M][2],siz[M];
ll ans,a[N],b[N];

void Insert( ll x )
{
    int pos=0;
    for ( int i=33; ~i; i-- )
    {
        int ch=(x>>i)&1;
        if ( !g[pos][ch] ) g[pos][ch]=++tot;
        pos=g[pos][ch]; siz[pos]++;
    }
}

ll Query( ll x,int p )
{
    int pos=0; ll res=0;
    for ( int i=33; ~i; i-- )
    {
        int ch=(x>>i)&1;
        if ( siz[g[pos][ch^1]]<p ) p-=siz[g[pos][ch^1]],pos=g[pos][ch];
        else res|=1ll<<i,pos=g[pos][ch^1];
    }
    return res;
}

int main()
{
    n=read(); k=read(); k<<=1;
    Insert( 0 );
    b[0]=0;
    for ( int i=1; i<=n; i++ )
    {
        a[i]=read(); b[i]=b[i-1]^a[i];
        Insert( b[i] );
    }

    for ( int i=0; i<=n; i++ )
    {
        ll tmp=Query(b[i],rk[i]=1);
        q.push( Node(i,tmp) );
    }
    ll ans=0;
    while ( k-- )
    {
        ans+=q.top().val;  int p=q.top().pos; q.pop();
        ll tmp=Query(b[p],++rk[p]);
        q.push( Node(p,tmp) );
    }

    printf( "%lld\n",ans>>1 );

    return 0;
}

加强版

Orz Apocrypha 为什么它也出现在了我们的模拟赛里
范围:$n\leq 7.5\times 10^5,k\leq\frac{n*(n+1)}{2},a_i<2^{32}$ . 于是需要一个 $\mathcal{O}(n\log n)$ 的优秀做法。

Solution

同样做一遍异或前缀和,记为 $b$ ,将题目转化为点对异或。有序对和无序对的处理同上。

考虑到 $K$ 很大,显然不能枚举,那么可以枚举每一位计算贡献。大致思路就是,找出异或值第 $K$ 大的数,然后求所有大于这个数的异或值之和。在 Trie 上找第 $K$ 大的思路同上,但是中间要多统计一些东西:

同原题一样,首先我们要记录一个 $siz$ 表示 Trie 树上节点的子树大小(注意是有效的结束节点个数),统计方法同上。

设当前节点为 $pos$ ,当前这一位的值是 $ch$ ,那么只有在 $g[pos][ch\oplus 1]$ 这个节点的子树中的 $b$ 才能在这一位上产生贡献。

如果出现 $siz[g[pos][ch\oplus 1]]<K$ ,即上文需要减去 $siz$ 的情况,再在 $g[pos][ch\oplus 1]$ 处打一个 $b[i]$ 的标记,表示子树中所有的 $b[j]\oplus b[i]$ 都会对答案产生贡献,记录 $ans[bit]+=siz[g[pos][ch\oplus 1]]$ ,表示二进制下这一位上 $1$ 的个数。

否则,$ans[bit]+=K$ 。

这样做完之后,再 DFS 一遍,处理每个标记,然后加入答案的贡献即可,或者直接顺带统计也行。但是在统计答案的时候,处理标记仍然需要拆位,复杂度 $\mathcal{O}(n\log ^2n)$ ,还需要优化。

考虑打标记是什么形式。能够在某个点上打上标记的数的集合一定都在某一棵子树里面,那么标记就转化成了两棵子树中所有 $b[i]$ 的两两异或和。仍然拆位维护,统计子树中某一位上 $1$ 的个数,在插入之前将 $b$ 排序,这样每个子树就对应一段区间,比较好处理。

复杂度之所以是 $n\log$ 的,是因为标记个数不超过 $\mathcal{O}(n)$ 个。标记只会在三度点上出现。因此,一个节点 $x$ 至多只会和另外一个点打标记。那么就不需要去重。

Code

小范围(但是保证时间复杂度与 $K$ 无关)的提交地址:CF241B

这里是正经大范围的代码:数据自己造XD

我要杀了出题人!不知道为什么我的程序在所有数相同的时候会 WA ,然后特判了还是过不去,结果发现就算是这样的部分分也要开 Int128 !骗个分容易吗。

//Author:RingweEH
#define Int128 __int128
const int N=750010,M=32;
int n,tot=1,g[N*M][2],siz[N*M],bit[N][M],nw[N];
ll lim,a[N],m,cnt;
Int128 sum;

void Insert( int x )
{
    int pos=1;
    for ( int i=31; ~i; i-- )
    {
        int ch=x>>i&1;
        if ( !g[pos][ch] ) g[pos][ch]=++tot;
        pos=g[pos][ch]; siz[pos]++;
    }
}

void GetLim()
{
    ll las=m;
    for ( int i=1; i<=n; i++ )
        nw[i]=1;
    for ( int i=31; ~i; i-- )
    {
        ll tmp=0;
        for ( int j=1; j<=n; j++ )
        {
            int ch=a[j]>>i&1;
            tmp+=siz[g[nw[j]][ch^1]];
        }
        if ( tmp>=las ) lim|=(1ll<<i);
        else las-=tmp;
        for ( int j=1; j<=n; j++ )
        {
            int ch=(a[j]^lim)>>i&1;
            nw[j]=g[nw[j]][ch];
        }
    }
}

void GetSum()
{
    for ( int i=31; ~i; i-- )
    {
        if ( lim>>i&1 ) continue;
        ll now=((lim>>i)<<i)|(1ll<<i);
        for ( int j=1; j<=n; j++ )
        {
            ll l=((a[j]^now)>>i)<<i,r=l|((1ll<<i)-1);
            l=lower_bound( a+1,a+1+n,l )-a;
            r=upper_bound( a+1,a+1+n,r )-a;
            sum+=now*(r-l);
            cnt+=r-l;
            if ( l<=j && j<r ) cnt--;
            for ( int k=i-1; ~k; k-- )
            {
                int tmp=bit[l][k]-bit[r][k];
                if ( (a[j]>>k)&1 ) tmp=r-l-tmp;
                sum+=(1ll<<k)*tmp;
            }
        }
    }
}


void print( Int128 x)
{
    if ( !x ) return;
    print(x/10);
    putchar( (char)(x%10+'0') );
}

void Same()
{
    int cnt=0; ll num=0;
    for ( int i=1; i<=n; i++ )
        if ( a[i]==0 ) num+=(i-1)-cnt,cnt++;
        else num+=cnt;
    m>>=1;
    Int128 res=a[2],mul=min( m,num );
    print( res*mul );
}

int main()
{
    n=read()+1; m=read()<<1;  a[1]=0;
    bool fl=1; ll a1;
    for ( int i=2; i<=n; i++ )
    {
        ll x=read(); a[i]=x^a[i-1];
        if ( i==2 ) a1=x;
        else fl&=(a1==x);
    }

    if ( fl ) { Same(); return 0; }

    sort( a+1,a+1+n );
    for ( int i=n; i; i-- )
    {
        Insert( a[i] );
        for ( int j=0; j<32; j++ )
            bit[i][j]=bit[i+1][j]+((a[i]>>j)&1);
    }

    GetLim(); GetSum();
    sum>>=1; cnt>>=1; m>>=1;
    Int128 ans=(sum+(m-cnt)*lim);

    print( ans );

    return 0;
}



RingweEH
11个月前

更好的阅读体验

还不会用 Markdown 的时候写的文章……重修&复习了一遍。主要修改的还是习题部分。

原来那篇低质量烂文已经删掉了awa 虽然这篇也没好到哪去

0 - 意义

线性基是向量空间的一组基,通常可以解决有关异或的一些题目。

简单讲就是由一个集合构造出来的另一个集合,这个集合大小最小且能异或出原来集合中的任何一个数,并且不能表示出除了原集合的其他数。

性质

  1. 线性基能相互异或得到原集合的所有相互异或得到的值。

  2. 线性基是满足性质1的最小的集合

  3. 线性基没有异或和为 $0$ 的子集。

  4. 假设线性基中有 $cnt$ 个数,线性基能异或出的数的集合大小为 $2^{cnt}-1$(去掉一个都不取),也就是说,线性基中不同的组合异或出的数都不一样。

1 - 构造

设当前插入的数是 $x$ ,线性基数组为 $a$ ,从高位向低位走,考虑所有为 $1$ 的当前位 $i$ ,

  • 如果线性基的第 $i$ 位为 $0$ ,那么直接在这一位插入 $x$ ,退出;
  • 否则,令 $x=x\oplus a[i]$
  • 重复上述操作直到 $x=0$

如果退出循环的时候 $x=0$ ,那么说明原有的线性基已经可以表示 $x$ ,无需再插入;反之,则说明为了表示 $x$ 插入了一个新的元素。

void Insert( ll x )
{
    for ( int i=30; ~i; i-- )
        if ( x&(1ll<<i) )
            if ( !a[i] ) { a[i]=x; return; }
            else x^=a[i];
    flag=1;
}

检验存在

检查一个数是否能被某个线性基表示出来。

和插入类似,只要中途或者最后变成 $0$ 了,就说明能够表示。

bool check( ll x )
{
    for ( int i=30; ~i; i-- )
        if ( x&(1ll<<i) )
            if ( !a[i] ) return 0;
            else x^=a[i];
    return 1;
}

2 - 查询异或最值

最小值

查询最小值相对比较简单。

考虑在插入的过程中,每一次异或 $a[i]$ 的操作,$x$ 的二进制最高位都在降低,所以不可能插入两个二进制最高位相同的数。

此时线性基中的最小值异或上其他的数,必然会增大,所以直接输出线性基中的最小值即可。

注意要特判能否异或出 $0$ . 因为线性基有性质:没有异或和为 $0$ 的子集。特判也很简单,只要一个数在插入过程中没有被插入到某个 $a[i]$ ,那么就被异或成了 $0$ ,说明 $0$ 是可以取到的。

ll Query_min( ll res=0 )
{
    if ( fl ) return 0;    //flag 是 Insert 中传出来的变量,表示是否能表示 0 
    for ( int i=0; i<=30; i++ )
        if ( a[i] ) return a[i];
}

最大值

从高到低遍历线性基,设当前考虑到第 $i$ 位。如果当前答案 $res$ 的第 $i$ 位为 $0$ ,就将 $res=res\oplus a[i]$ ;否则不操作。或者说,更简便的写法是直接和异或后的值取 $\max$ (其实是一个道理,高位从 $0\to 1$ 一定是变大的嘛)

这是显然的,求最小值部分已经说过,线性基中数的最高位显然单调递减,那么每次这样的操作之后答案都不会变劣。

这是对序列中元素求相互异或的最大值。如果是另一个给定的数 $x$ ,那么用类似的方式可以解决,只需要把 $res$ 的初始值改变即可。

ll Query_max( ll res=0 )
{
    for ( int i=30; ~i; i-- )
        res=max( res,res^a[i] );
    return res;
}

模板

写到这里就可以写 模板题 了。代码:

//Author:RingweEH
const int N=55,MX=50;
int n;
ll a[N];

void Insert( ll x )
{
    for ( int i=MX; ~i; i-- )
        if ( x>>i&1 )
        {
            if ( !a[i] ) { a[i]=x; return; }
            x^=a[i];
        }
}

ll Query_mx( ll res=0 )
{
    for ( int i=MX; ~i; i-- )
        res=max( res,res^a[i] );
    return res;
}

int main()
{
    n=read();
    for ( int i=1; i<=n; i++ )
    {
        ll x=read(); Insert( x );
    }

    printf( "%lld\n",Query_mx() );

    return 0;
}

3 - 求第 k 小

首先,线性基的构造方式跟之前不太一样了,我们知道,线性基是以每个二进制为最高位存一个数的,容易想到把 k 二进制分解,这样的话,只需要改点限制:规定 $a[i]$ 的值最高位是第 $i$ 位,且在此基础上 $a[i]$ 最小。

考虑之前的 $a[i]$ ,它除了在第 $i$ 位有个 $1$ 外,在更低的位还有若干个 $1$ 。那是否可以用线性基中的某些数,尽量消去低位的那些 $1$ ? 这个很好做,往线性基插入一个新数时,用这个 $a[i]$ 更新 $a$ 数组的其它所有值就行了。

详细做法:

  • 对于低位

现在插入的一个数放到了 $a[i]$ ,它在一个更低的二进制位(设其为第 $j$ 位)上为 $1$ ,且 $a[j]$ 已被赋过值,那就把 $a[i]$ 更新为 $a[i]\oplus a[j]$ 。为了方便,从大到小枚举 $j$ 即可。

  • 对于高位

只考虑低位显然不对,因为有可能 $a[i]$ 的第 $j$ 个二进制位为 $1$ ,而 $a[j]$ 此时可能没有值,但它以后被赋了值,这种情况下也应该用 $a[j]$ 更新 $a[i]$ 。我们只能用赋值晚的更新赋值早的,所以对于插入的一个数 $a[i]$ ,不仅要用更低位的 $a[j]$ 更新它,还要用它更新更高位的 $a[j]$ 。依然从大到小枚举 $j$ 。

代码:

for ( int i=N; ~i; i-- )
    if ( x>>i&1 )
    {
        if ( a[i] ) x^=a[i];
        else
        {
            a[i]=x;
            for ( int j=i-1; ~j; j-- )
                if ( a[j] && (a[i]>>j&1) ) a[i]^=a[j];
            for ( int j=N; j>i; j-- )
                if ( a[j]>>i&1 ) a[j]^=a[i];
            return;
        }
    }

其实这才是线性基的通用构造方式(比如对于模板题,多出来的要求对答案没有影响,因此该构造方案可以兼容使用)。

换个角度看这个构造方式,其实就是标准的高斯消元,所谓的把不在对角线上的 $1$ 能消掉就消掉,其实也就是让每行的数最小。

如上改变线性基的构造方式后,把 $k$ 二进制分解,若第 $i$ 位为 $1$ 就把 $ans$ 异或上 $p_i$ 即可。

注意也要特判能否异或出 $0$ ,并且在插入完之后要压缩线性基数组,只留下 $a[i]\neq 0$ 的部分。(这个显然,为 $0$ 相当于是无效位,对 $k$ 没有任何贡献,当然也不能算进位数里面)

模板题

//Author:RingweEH
const int N=63,M=65;
int n,cnt;
ll a[M],b[M];
bool fl=0;

void Insert( ll x )
{
    for ( int i=N; ~i; i-- )
        if ( x>>i&1 )
        {
            if ( a[i] ) x^=a[i];
            else
            {
                a[i]=x;
                for ( int j=i-1; ~j; j-- )
                    if ( a[j] && (a[i]>>j&1) ) a[i]^=a[j];
                for ( int j=N; j>i; j-- )
                    if ( a[j]>>i&1 ) a[j]^=a[i];
                return;
            }
        }
    if ( x==0 ) fl=1;
}

int main()
{
    int T=read();
    for ( int cas=1; cas<=T; cas++ )
    {
        memset( a,0,sizeof(a) ); fl=0; cnt=0;

        n=read();
        for ( int i=1; i<=n; i++ )
        {
            ll x=read(); Insert( x );
        }

        for ( int i=0; i<=N; i++ )
            if ( a[i] ) b[cnt++]=a[i];
        int q=read(); printf( "Case #%d:\n",cas );
        while ( q-- )
        {
            ll k=read(),ans=0; k-=fl;
            if ( k>=(1ll<<cnt) ) { printf( "-1\n" ); continue; }
            for ( int i=0; i<cnt; i++ )
                if ( k>>i&1 ) ans^=b[i];
            printf( "%lld\n",ans );
        }
    }

    return 0;
}

4 - 习题

也许大概或许可能是按难度排序的吧(

彩灯

有一个长度为 $N$ 的01串,初始全 $0$ 。给出 $M$ 个操作,每个操作能使特定的几位取反,问能产生几种不同的 $01$ 串。

Solution

显然是裸题。将每个操作看成一个数,构造线性基,题目也就是问能表示出多少个数。

注意到有性质:

假设线性基中有 $cnt$ 个数,线性基能异或出的数的集合大小为 $2^{cnt}-1$(去掉一个都不取)

那就做完了。不过这题全 $0$ 也算一种方案,不需要 $-1$ .

我怎么又没看见取模(悲)

//Author:RingweEH
const int N=55,MX=50;
const ll Mod=2008;
int n,m;
ll a[N],cnt=0;
char s[N];

void Insert( ll x )
{
    for ( int i=MX; ~i; i-- )
        if ( x>>i&1 )
        {
            if ( !a[i] ) { a[i]=x; cnt++; return; }
            x^=a[i];
        }
}

int main()
{
    n=read(); m=read();
    for ( int i=1; i<=m; i++ )
    {
        scanf( "%s",s ); ll x=0;
        for ( int j=0; j<n; j++ )
        {
            x<<=1;
            if ( s[j]=='O' ) x|=1;
        }
        Insert( x );
    }

    printf( "%lld\n",(1ll<<cnt)%Mod );

    return 0;
}

最大XOR和路径

给定一个边权为非负整数的无向连通图,求 $1$ 到 $N$ 的路径,使得边权异或和最大。点边可以重复经过。

$N\leq 5e4,M\leq 1e5,D_i\leq 1e18$ .

Solution

做法很简单:找出所有环,扔到线性基里,然后随便找一条路径作为初始值,求异或最大值即可。

考虑为什么是对的。

首先找环肯定是没有疑问的,因为重复走两遍相当于没有走,唯一能产生变数的就是环了。

然后考虑为什么随便一条路径就行。假设存在至少两条,设为 $path_1,path_2$ ,那么它们本身就构成了一个大环,异或一下就能得到对方。因此只要任意一条路径+所有环就好了。

//Author:RingweEH
const int N=5e4+10;
struct Edge
{
    int to,nxt; ll val;
}e[N<<2];
int head[N],tot=0,n,m;
ll path[N],a[64];
bool vis[N];

void Add( int u,int v,ll w )
{
    e[++tot].to=v; e[tot].nxt=head[u]; head[u]=tot; e[tot].val=w;
}

void Insert( ll x )
{
    for ( int i=62; ~i; i-- )
        if ( x>>i&1 )
        {
            if ( !a[i] ) { a[i]=x; return; }
            x^=a[i];
        }
}

void Dfs( int u,int fa,ll now )
{
    vis[u]=1; path[u]=now;
    for ( int i=head[u]; i; i=e[i].nxt )
    {
        int v=e[i].to;
        if ( v==fa ) continue;
        if ( !vis[v] ) Dfs( v,u,now^e[i].val );
        else Insert( path[v]^now^e[i].val );
    }
}

int main()
{
    n=read(); m=read();
    for ( int i=1; i<=m; i++ )
    {
        int u=read(),v=read(); ll w=read();
        Add( u,v,w ); Add( v,u,w );
    }

    Dfs( 1,0,0 ); ll ans=path[n];
    for ( int i=62; ~i; i-- )
        ans=max( ans,ans^a[i] );

    printf( "%lld\n",ans );

    return 0;
}

albus就是要第一个出场

给定一个长度为 $n$ 的序列 $A$ ,将所有 $A$ 的子集的异或和从小到大排成序列 $B$ ,求一个数在 $B$ 中第一次出现的下标。

Solution

还是用这个性质:

假设线性基中有 $cnt$ 个数,线性基能异或出的数的集合大小为 $2^{cnt}-1$(去掉一个都不取)

然后注意到除了这 $cnt$ 个数,还有 $n-cnt$ 个,而它们所能组成的异或和一定能被线性基中的数表示出来,也就相当于我们有 $2^{n-cnt}$ 个异或和为 $0$ 的子集。那么就是,所有能异或出的数的集合中,每个数在 $B$ 序列里都出现了 $2^{n-cnt}$ 次。我们只需要查询数 $x$ 在不重复的序列中的排名 $rk$ ,然后 $ans=rk\times2^{n-cnt}+1$ 即可。

现在考虑如何求排名。从高到低枚举每一位 $a[i]\neq 0$ 的位置,如果 $x$ 的当前位为 $1$ ,那么就是比 “当前位为 $0$ 的 $2^{n-cnt}$ 个异或和”都要大,就加上这一部分的贡献;否则不加。(注:这里的 $cnt$ 指的是到当前位位置,$a[i]\neq 0$ 的个数。这应该很好理解,因为如果当前这个高位为 $1$ ,那么无论后面怎么取,都比高位为 $0$ 的要大)

被位运算优先级坑了一发 /kk

//Author:RingweEH
const int N=1e5+10,M=30,Mod=10086;
int n,a[M+5];

ll power( ll a,ll b )
{
    ll res=1;
    for ( ; b; b>>=1,a=a*a%Mod )
        if ( b&1 ) res=res*a%Mod;
    return res;
}

void Insert( int x )
{
    for ( int i=M; ~i; i-- )
        if ( x>>i&1 )
        {
            if ( !a[i] ) { a[i]=x; return; }
            x^=a[i];
        }
}

ll Query_rk( int x )
{
    int cnt=0; ll ans=0;
    for ( int i=M; ~i; i-- )
        if ( a[i] )
        {
            cnt++;
            if ( x>>i&1 ) ans=(ans+power(2ll,n-cnt))%Mod;
        }
    return ans;
}

int main()
{
    n=read();
    for ( int i=1; i<=n; i++ )
        Insert( read() );

    ll Q=read(); ll ans=Query_rk(Q);

    printf( "%lld\n",(ans+1)%Mod );

    return 0;
}

新Nim游戏

在 Nim 游戏的第一轮,允许两个玩家特殊操作:可以拿走若干个整堆,可以一堆都不拿,但是不能全部拿走。其余同 Nim。

问先手是否必胜,如果是那么给出第一轮拿的最小数量。

Solution

其实先手肯定必胜,第一次拿的时候只剩下一堆就好了。

那么问题在于如何让第一轮拿走的数量最小。

显然可以发现,先手第一轮拿完之后不能剩下异或为 $0$ 的子集。而这显然是个线性基(性质 $3$ ),也就是要构造和最大的一组线性基。

那么将每一堆排序,然后依次尝试加入线性基,并求出所有成功加入的数之和即可。

//Author:RingweEH
const int N=110,M=30;
int n,a[35],b[N];

bool Insert( int x )
{
    for ( int i=M; ~i; i-- )
        if ( x>>i&1 )
        {
            if ( !a[i] ) { a[i]=x; return 1; }
            x^=a[i];
        }
    return 0;
}

int main()
{
    n=read(); ll sum=0;
    for ( int i=1; i<=n; i++ )
        b[i]=read(),sum+=b[i];

    sort( b+1,b+1+n ); ll ans=0;
    for ( int i=n; i>=1; i-- )
        if ( Insert(b[i]) ) ans+=b[i];

    printf( "%lld\n",sum-ans );

    return 0;
}

元素

给定一个长度为 $n$ 的序列 $A[i][0/1]$ ,求一个子集,满足 $A[i][0]$ 的异或和不为 $0$ 的情况下,$A[i][1]$ 和最大。

Solution

神笔题,直接按照 $A[i][1]$ 排序,然后依次尝试插入即可。和上题差不多。

//Author:RingweEH
const int N=1010,M=60;
struct Node
{
    ll num; ll val;
    bool operator < ( const Node &tmp ) const { return val<tmp.val; }
}b[N];
int n;
ll a[M];

bool Insert( ll x )
{
    for ( int i=M; ~i; i-- )
        if ( x>>i&1 )
        {
            if ( !a[i] ) { a[i]=x; return 1; }
            x^=a[i];
        }
    return 0;
}

int main()
{
    n=read();
    for ( int i=1; i<=n; i++ )
        b[i].num=read(),b[i].val=read();

    sort( b+1,b+1+n ); ll ans=0;
    for ( int i=n; i>=1; i-- )
        if ( Insert(b[i].num) ) ans+=b[i].val;

    printf( "%lld\n",ans );

    return 0;
}

装备购买

$n$ 个装备,每个装备 $m$ 个属性,每个装备还有个价格。如果手里有的装备的每一项属性为它们分配系数(实数)后可以相加得到某件装备,则不必要买这件装备。求最多装备下的最小花费。

Solution

“能被已有的装备组合出来”这一点很像线性基,但这里不再是异或线性基了,而是实数。

回归本真的线性基,可喜可贺

其实方式和异或线性基差不多,不过是把原来的 $x=x\oplus a[i]$ 换成了消元(具体参考高斯消元的方式),之前 $a[i]$ 记录的是每一位上留下的那个数,现在就记录一个位置,使得矩阵中第 $i$ 列(也就是第 $i$ 个变量)只有 $a[i]$ 这一行不为 $0$ (对应高斯消元中把每一行的方程消成只剩下一个变量, $a[i]$ 记录的是第 $i$ 个变量所在的方程)。每次找当前行不为 $0$ 的列 $j$ ,如果 $a[j]$ 还没有值就赋值并退出,否则就用 $c[i][j]/c[a[j]][j]$ 乘上 $c[a[j]][k]$ 去减 $a[i][k]$ 。不会高斯消元的你试试看怎么消元解多元方程就好了吧

然后要求最小花费,那就排个序即可。

精度yyds! 要开 long double 或者把 $eps$ 调成 $1e-5$ .

//Author:RingweEH
const int N=510;
const db eps=1e-5;
struct Vector
{
    db a[N]; int val;
    db &operator [] ( const int &x ) { return a[x]; }
    bool operator < ( const Vector&tmp ) const { return val<tmp.val; }
}c[N];
int n,m,a[N];


int main()
{
    n=read(); m=read();
    for ( int i=1; i<=n; i++ )
        for ( int j=1; j<=m; j++ )
            scanf( "%lf\n",&c[i][j] );
    for ( int i=1; i<=n; i++ )
        c[i].val=read();

    sort( c+1,c+1+n ); int cnt=0; ll ans=0;
    for ( int i=1; i<=n; i++ )
        for ( int j=1; j<=m; j++ )
        {
            if ( fabs(c[i][j])<eps ) continue;
            if ( !a[j] ) { a[j]=i; cnt++; ans+=c[i].val; break; }
            db tmp=1.0*c[i][j]/c[a[j]][j];
            for ( int k=j; k<=m; k++ )
                c[i][k]-=tmp*c[a[j]][k];
        }

    printf( "%d %lld\n",cnt,ans );

    return 0;
}



RingweEH
11个月前

做具体数学习题看到的生草式子(

前置定义

$\varphi(n)$ :$1\sim n$ 中与 $n$ 互质的数的个数,即 $\sum_{i=1}^n[\gcd(i,n)=1]$

$\pi(n)$ : $1\sim n$ 中的质数个数。

${x}$ :取 $x$ 的小数(分数)部分,即 $x\bmod 1$ .

$\lfloor x\rfloor,\lceil x\rceil $ :下取整和上取整。

题目

当 $n$ 是正整数时,证明恒等式:
$$
\sum_{1\leq k<n}\Big\lfloor \frac{\varphi(k+1)}{k}\Big\rfloor
=\sum_{1<m\leq n}\Big\lfloor \Big(\sum_{1\leq k<m}\lfloor (m/k)/\lceil m/k\rceil \rfloor\Big)^{-1}\Big\rfloor
=n-1-\sum_{k=1}^n\Big\lceil \Big\{\frac{(k-1)!+1}{k}\Big\}\Big\rceil.
$$
其实这个式子看上去有毒,但是显然得很(

引理

威尔逊定理:

$$
(n-1)!\equiv -1(\bmod n)\iff n>1,n\in primes
$$

Proof

如果 $n>1$ 且并非质数,那么显然不成立;(证明的话,$n$ 不是质数,所以一定有一个 $\leq \sqrt n$ 的因子,这里取最小的不是 $1$ 的因子。如果 $<\sqrt n$ 显然可以用 $1\sim n-1$ 组合出 $n$ ,如果等于,那么对于 $\sqrt n>2$ ,$\sqrt n\cdot 2<n$ ,一定能取出另一个 $\sqrt n$ 因子;对于 $\sqrt n=2$ ,特殊处理即可。 )

对于另一部分,考虑使用逆元来解决它。

显然,(在模意义下)如果数 $x$ 的逆元是 $y$ ,那么 $x,y$ 一定互为逆元。

所以唯一要做的就是确定哪些数的逆元是它本身,也就是求解同余方程:
$$
x^2\equiv 1(\bmod p)
$$
当 $p>2$ 时,可以做如下变换:
$$
(x+1)(x-1)\equiv 0(\bmod p)
$$
所以方程有且仅有两个根:$x=p-1,x=1$ .

而如果 $p=2$ ,那么显然有 $(p-1)!\equiv-1$ .

从而其他数都可以两两配对。因此,$(p-1)!\equiv 1\times (p-1)\equiv -1(\bmod p)$ .

证明

先把式子抄一遍:
$$
\sum_{1\leq k<n}\Big\lfloor \frac{\varphi(k+1)}{k}\Big\rfloor
=\sum_{1<m\leq n}\Big\lfloor \Big(\sum_{1\leq k<m}\lfloor (m/k)/\lceil m/k\rceil \rfloor\Big)^{-1}\Big\rfloor
=n-1-\sum_{k=1}^n\Big\lceil \Big\{\frac{(k-1)!+1}{k}\Big\}\Big\rceil.
$$
考虑逐个击破,对于第一个式子,显然 $\varphi(k+1)$ 最大是 $k$ ,当且仅当 $k+1$ 是质数时第一个式子才为 $1$ ,那么就相当于 $\pi(n)$ .

对于第二个式子,中间那个 $\lfloor (m/k)/\lceil m/k\rceil \rfloor$ 只有在 $k|m$ 的时候为 $1$ ,其余为 $0$ ,那么前两个式子简化为:

$$
\pi(n)
=\sum_{1<m\leq n}\Big\lfloor \Big(\sum_{1\leq k<m}[k|m]\Big)^{-1}\Big\rfloor
$$

对于某个数的真因数(暂且这么叫吧,反正就是排除 $n$ )倒数然后下取整,当且仅当个数为 $1$ 的时候才 $>0$ ( $=1$ ),也就是说 $m$ 必须是个质数。那么第二个式子就是 $\pi(n)$ ,等价了。

现在来看第三个式子。根据约定,${}$ 是取分数部分,只有在 $(k-1)!\bmod k=-1$ 时为 $0$ .

这意味着什么呢,这说明 $k$ 为质数的时候这个式子为 $0$ .(根据引理可得)

否则,如果不是质数,那么小数上取整就是 $1$ . 整个式子就是 $n-1-\sum_{k=1}^n[\gcd(k,n)\neq 1]$ ,那么也就是 $1\sim n$ 中的质数个数,即 $\pi(n)$ .

Q.E.D.

是不是很生草