CF2208D2 Tree Orientation (Hard Version) Solution

原来场切 D2 就有 2168 的表现分啊。

链接

解法一

这是我赛时的解法。

可以发现对于 D1 我们考虑使用 Floyd 实现传递闭包，那对于 D2，我们可以考虑优化这一过程。

思考后发现，对于传统的传递闭包，我们都会考虑用 bitset 进行实现，所以对于这里，我们也可以考虑用它来优化。

然后在加边的过程中一定要记录边的数量，超出直接输出 No。

当然，时间复杂度是可能问题的（存疑，存在剪枝），大致是 $O(n^2)$ 或 $O(\frac {n^3} {w}$，但我们只要考虑一些卡常技巧即可通过。

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <bitset>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
typedef int ll;
typedef long double ld;
typedef __int128 i128;
namespace io {
    using namespace std;
    inline ll read () {
        char x=getchar();
        ll ans=0,f=1;
        while (x<'0'||x>'9') {
            if (x=='-') {
                f*=(-1);
            }
            x=getchar();
        }
        while (x>='0'&&x<='9') {
            ans*=10;
            ans+=(x-'0');
            x=getchar();
        }
        return ans*f;
    }
    void print (ll x) {
        if (x<0) {
            x=-x;
            putchar('-');
        }
        if (x>=10) {
            print(x/10);
        }
        putchar(x%10+'0');
    }
}
using namespace io;
const ll N=8e3+5,mod=1e9+7,inf=2e9;
const ld eps=1e-6;
ll n;
bitset<N> g[N],e[N],r[N],kl;
char s[N];
ll u[N],v[N],m,ord[N],sz[N],fa[N];
inline ll fd (ll x) {
    while (fa[x]!=x) {
        fa[x]=fa[fa[x]];
        x=fa[x];
    }
    return x;
}
inline void solve () {
    n=read();
    for (ll i=1;i<=n;i++) {
        scanf("%s",s+1);
        g[i].reset();
        e[i].reset();
        r[i].reset();
        for (ll j=1;j<=n;j++) {
            if (s[j]=='1') {
                g[i].set(j);
            }
        }
    }
    for (ll i=1;i<=n;i++) {
        if (!g[i].test(i)) {
            puts("No");
            return;
        }
    }
    for (ll i=1;i<=n;i++) {
        for (ll j=i+1;j<=n;j++) {
            if (g[i].test(j)&&g[j].test(i)) {
                puts("No");
                return;
            }
        }
    }
    for (ll i=1;i<=n;i++) {
        sz[i]=g[i].count();
        ord[i]=i;
    }
    sort(ord+1,ord+n+1,[] (ll x,ll y){
        return sz[x]>sz[y];
    });
    m=0;
    for (ll i=1;i<=n;i++) {
        kl.reset();
        for (ll t=1;t<=n;t++) {
            ll j=ord[t];
            if (i==j) {
                continue;
            }
            if (!g[i].test(j)) {
                continue;
            }
            if (kl.test(j)) {
                continue;
            }
            u[++m]=i;
            v[m]=j;
            e[i].set(j);
            kl|=g[j];
            if (m>n-1) {
                puts("No");
                return;
            }
        }
    }
    if (m!=n-1) {
        puts("No");
        return;
    }
    for (ll i=1;i<=n;i++) {
        fa[i]=i;
    }
    for (ll i=1;i<=m;i++) {
        ll x=u[i],y=v[i];
        ll fx=fd(x),fy=fd(y);
        if (fx!=fy) {
            fa[fx]=fy;
        }
    }
    ll rt=fd(1);
    for (ll i=2;i<=n;i++) {
        if (fd(i)!=rt) {
            puts("No");
            return;
        }
    }
    for (ll t=n;t>=1;t--) {
        ll i=ord[t];
        r[i].set(i);
        for (ll j=1;j<=n;j++) {
            if (e[i].test(j)) {
                r[i]|=r[j];
            }
        }
    }
    for (ll i=1;i<=n;i++) {
        if (r[i]!=g[i]) {
            puts("No");
            return;
        }
    }
    puts("Yes");
    for (ll i=1;i<=m;i++) {
        print(u[i]);
        putchar(' ');
        print(v[i]);
        puts("");
    }
}
int main () {
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    ll T=1;
    T=read();
    while (T--) {
        solve();
    }
    return 0;
}
/**/

解法二

这是赛后讨论出来的，在这里只提供一种思路。

我们可以考虑对于点 $i$ 那些点它是到不了的，枚举这些到不了的点，找到这些点与这条边之间必须经过的最后一个点即是所与 $i$ 相连的边的另一个点。