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

· · 题解

思路

神仙题。

钦定 d(A)>d(B)，枚举 d(A)，二分 d(B) 的最小取值，判定可以使用 2-sat。时间复杂度 O(n^4\log n^2)。

考虑优化，可以从大到小枚举最大的边，并把这条边加入一个新图中。我们发现，在当前情况中，最大边的两个端点一定在同一个集合中，其他边的端点不在同一个集合中。

分下面几种情况：

  1. 加入后形成一个环：
    • 若为奇环，继续枚举下去，奇环上相邻两点颜色不同，一定不存在一种合法的染色方案，所以可以算完当前最大值的答案后退出枚举；
    • 若为偶环，当前需要两端点相同，把两个端点缩起来后就变成奇环了，一定不存在合法的染色方案，则枚举下一个最大边。
  2. 加入后不形成环：这样的边最多只有 O(n) 个，可以暴力。

最后发现需要计算的最大边只有 O(n) 个，对于每个最大边二分即可做到 O(n^3\log n)。注意特判答案为零的情况。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 205;
int n,f[N<<1],cnt;
inline int find(int x)
{
    if(f[x]==x) return x;
    return f[x] = find(f[x]);
}
struct node{
    int u,v,w;
    inline friend bool operator < (node x,node y)
    {
        return x.w>y.w;
    }
}e[N*N];
vector<int> g[N<<1];
int dfn[N<<1],low[N<<1],idx,stk[N<<1],top,scc[N<<1],c;
bool inc[N<<1];
void dfs(int u)
{
    dfn[u] = low[u] = ++idx,stk[++top] = u,inc[u] = 1;
    for(auto v:g[u])
    {
        if(!dfn[v])
        {
            dfs(v);
            low[u] = min(low[u],low[v]);
        }
        else if(inc[v]) low[u] = min(low[u],dfn[v]);
    }
    if(dfn[u]==low[u])
    {
        c++;
        while(stk[top]!=u)
            inc[stk[top]] = 0,scc[stk[top]] = c,top--;
        inc[u] = 0,scc[u] = c,top--;
    }
}
inline bool ok(int x,int y)
{
    for(int i = 1;i<=2*n;i++)
        g[i].clear(),dfn[i] = low[i] = inc[i] = scc[i] = 0;
    idx = top = c = 0;
    for(int i = 1;i<=cnt;i++)
    {
        int u = e[i].u,v = e[i].v;
        if(e[i].w>x)
        {
            g[u].push_back(v+n),g[v].push_back(u+n);
            g[v+n].push_back(u),g[u+n].push_back(v);
        }
        else if(e[i].w>y)
        {
            g[u].push_back(v+n),g[v].push_back(u+n); 
        }
    }
    for(int i = 1;i<=2*n;i++) if(!dfn[i]) dfs(i);
    for(int i = 1;i<=n;i++)
        if(scc[i]==scc[i+n]) return 0;
    return 1;
}
signed main()
{
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i = 1;i<=n;i++)
        for(int j = i+1;j<=n;j++)
            cnt++,e[cnt].u = i,e[cnt].v = j,cin>>e[cnt].w;
    sort(e+1,e+cnt+1);
    int ans = 2e9;
    for(int i = 1;i<=2*n;i++) f[i] = i;
    for(int i = 1;i<=cnt;i++)
    {
        int u = e[i].u,v = e[i].v,w = e[i].w;
        if(find(u)==find(v+n)) continue;
        f[find(u)] = find(v+n),f[find(v)] = find(u+n);
        int l = i,r = cnt+1,res = -1;
        while(l<=r)
        {
            int mid = (l+r)/2;
            if(ok(w,e[mid].w)) res = mid,l = mid+1;
            else r = mid-1;
        }
        if(res!=-1) ans = min(ans,e[res].w+w);
        if(find(u)==find(u+n)) break;
    }
    if(ok(0,0)) ans = 0;
    cout<<ans<<'\n';
    return 0;
}