题解：P6898 [ICPC 2014 WF] Metal Processing Plant

· · 题解

思路 1：暴力枚举 D(A) 和 D(B)，转化为 2-SAT 问题后判断是否合法，复杂度 O(n^6)。

思路 2：在枚举 D(A) 的过程中，不用枚举 D(B) 而是对 D(B) 二分答案，复杂度 O(n^4 \log n)。

思路 3：在减小 D(A) 的过程中，为了保持有解 D(B) 应当增大，因此使用双指针即可做到 O(n^4)。

思路 4：容易发现，在思路 3 中 2-SAT 建图后的边变化很少，我们使用 Kosaraju 算法就可以做到单次 O(\frac{n^2}{w}) 判断一组 (D(A),D(B)) 是否合法，总复杂度 O(\frac{n^4}{w}) 已经能通过这道题。

思路 5：不妨设 D(A) \ge D(B)。建立一张新的图 G，如果 w(i,j) > D(A) 就在 (i,j) 间连一条边。如果 (A,B) 存在解，相当于可以将 G 的顶点划分为两个独立集，即可以黑白二染色（是二分图）。如果不是二分图，一定无解；而如果新加的边并不会减少连通块个数（新加的边指的是，从大到小扫描 D(A) 的过程中，D(A) 在减少则 G 中的边在增加），那么加上这条边肯定不会使 D(B) 的最小值变化（由于不存在偶环，那么新加的边的两个端点一定会出现在最优解的同一个集合中，也就是没有任何影响）。因此，可能的 D(A) 出现在“加入奇环”或者“合并两个连通分量”之前，只有 O(n) 种。然后对 D(B) 做二分答案，利用二分位置的移动量是 O(n^2) 即可做到 O(n^3 + \frac{n^3 \log n}{w})。

思路 6：你要进行 O(n \log n) 次 2-SAT 操作，能不能再砍一些啊？感谢 @Forest114514 的题解，我们可以整体二分。即，使用整体二分确定所有 n 个 D(A) 对应的 D(B) 的最小值，内部进行二分。当然我不会证复杂度，通过打表发现只需要进行 O(n) 次 2-SAT 操作。考虑 (D(A),D(B)) 组的变化。首先我们对 D(A) 这一维做整体二分，移动距离为 O(n^2 \log n)；对 D(B) 内层做了若干次二分，总的移动距离也为 O(n^2 \log n)（每一次二分，D(B) 的移动距离是 D(B) 可行区间的长度，每一层这个值为 O(n^2)；D(A) 的移动距离随便用主定理分析一下，发现也是 O(n^2 \log n)）。总复杂度为 O(n^2 \log n + \frac{n^3}{w})，非常厉害。

代码：

#include<bits/stdc++.h>
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=400+10;
int n,dis[MAXN][MAXN],lsh[MAXN*MAXN],m,mx[MAXN];
bitset<MAXN> G[MAXN],g[MAXN];

//====2-SAT====
int col[MAXN],cs,tot,idx[MAXN];
bitset<MAXN> vis;
void dfs1(int u) {
    vis[u]=0;
    while(1) {
        int to=(vis&G[u])._Find_first();
        if(to>=1&&to<=n+n) dfs1(to);
        else break ;
    }
    idx[++tot]=u;
    return ;    
}
void dfs2(int u,int c) {
    vis[u]=0,col[u]=c;
    while(1) {
        int to=(vis&g[u])._Find_first();
        if(to>=1&&to<=n+n) dfs2(to,c);
        else break ;
    }
    return ;
}
void Kosaraju(void) {
    ffor(i,1,n+n) vis[i]=1;
    tot=cs=0;
    ffor(i,1,n+n) if(vis[i]) dfs1(i);
    ffor(i,1,n+n) vis[i]=1;
    roff(i,n+n,1) if(vis[idx[i]]) ++cs,dfs2(idx[i],cs);
    return ;
}
//====2-SAT====

vector<pair<int,int>> occ[MAXN*MAXN];
int tA,tB;
int check(int A,int B) {
    while(tA>A) {
        for(auto pr:occ[tA]) {
            int u=pr.first,v=pr.second;
            G[u][v+n]=G[v][u+n]=g[v+n][u]=g[u+n][v]=1;
        }
        --tA;
    }
    while(tB>B) {
        for(auto pr:occ[tB]) {
            int u=pr.first,v=pr.second;
            G[u+n][v]=G[v+n][u]=g[v][u+n]=g[u][v+n]=1;  
        }
        --tB;
    }
    while(tA<A) {
        ++tA;
        for(auto pr:occ[tA]) {
            int u=pr.first,v=pr.second;
            G[u][v+n]=G[v][u+n]=g[v+n][u]=g[u+n][v]=0;
        }
    }
    while(tB<B) {
        ++tB;
        for(auto pr:occ[tB]) {
            int u=pr.first,v=pr.second;
            G[u+n][v]=G[v+n][u]=g[v][u+n]=g[u][v+n]=0;  
        }
    }
    Kosaraju();
    ffor(i,1,n) if(col[i]==col[i+n]) return 0;
    return 1;
}

int ans,cnt,cA[MAXN],fa[MAXN];
int find(int k) {return (fa[k]==k)?k:(fa[k]=find(fa[k]));}
void solve(int l,int r,int bl,int br) {
    if(l>r) return ;
    if(bl==br) return ans=min(lsh[cA[l]]+lsh[bl],ans),void();
    int p=cA[(l+r>>1)],tans=br,L=bl,R=br-1;
    while(L<=R) {
        int mid=(L+R>>1);
        if(check(p,mid)) tans=mid,R=mid-1;
        else L=mid+1;
    }
    ans=min(ans,lsh[p]+lsh[tans]);
    solve(l,(l+r>>1)-1,tans,br);
    solve((l+r>>1)+1,r,bl,tans);
    return ;
}

int FA[MAXN];
int FIND(int k) {return (FA[k]==k)?k:(FA[k]=FIND(FA[k]));}
int main() {
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n;
    ffor(i,1,n) ffor(j,i+1,n) cin>>dis[i][j],dis[j][i]=dis[i][j],lsh[++m]=dis[i][j];
    lsh[++m]=0;
    sort(lsh+1,lsh+m+1),m=unique(lsh+1,lsh+m+1)-lsh-1;
    ffor(i,1,n) ffor(j,i+1,n) dis[i][j]=dis[j][i]=lower_bound(lsh+1,lsh+m+1,dis[i][j])-lsh,occ[dis[i][j]].push_back({i,j});
    ans=lsh[m];
    ffor(i,1,n) fa[i]=i,FA[i]=i,FA[i+n]=i+n;

    int ts=0;
    roff(i,m,1) {
        int flg=0;
        for(auto pr:occ[i]) {
            int u=pr.first,v=pr.second;
            if(find(u)!=find(v)) flg=1,fa[find(u)]=find(v);

            FA[FIND(u)]=FIND(v+n),FA[FIND(v)]=FIND(u+n);

            if(FIND(u)==FIND(u+n)||FIND(v)==FIND(v+n)) ts=1;
        }

        if(ts) {cA[++cnt]=i;break ;}
        if(flg||i==1) cA[++cnt]=i;
    }

    ffor(i,1,n) fa[i]=i;

    reverse(cA+1,cA+cnt+1);
    tA=tB=m;
    solve(1,cnt,1,m);
    cout<<ans;
    return 0;
}