题解 AT5201 【[AGC038D] Unique Path】

_quasar_ · 2020-10-29 09:09:13 · 题解

首先如果 a,b 只有一条路径，且 b,c 只有一条路径，那么 a,c 一定只有一条路径。显而易见的，a,c 之间的合法路径只能为 a\rightarrow b\rightarrow c 。因此将所有的由 0 类边连起来的点放在一起，形成一个联通块（显然只能是一棵树）。

假设有 k 个联通块，因为每个联通块都是一棵树，因此还剩下 m-n+k 条边。

如果这个时候没有 1 类边的话：

• 边数的最小取值：将 k 棵树连起来的边数花费为 k-1 。
• 边数的最大取值：比较显然的是因为同一联通块中的点不能属于一个环内，所以钦定每个联通块有一个"外交官"专门负责向外面连边，其他点都不能向外面连边。这样的话 k 个"外交官"可以随便连边，因此边数为 \frac{k(k-1)}{2} 。

如果有 1 类边：

• 如果只有两个联通块：想不出怎么构造了，无解。
• 如果有一条 1 类边的两个端点属于同一联通块：两个同一联通块的点不能放在一个环里面，无解。
• 边数的最小取值：将 k 个"外交官"连成一个环即可，边数为 k 。
• 边数的最大取值：同样是 \frac{k(k-1)}{2} 。

维护一下联通块，然后判断 m 是否在合法区间内即可（注意判断 m<n-1）。

const int N=1e5+5;
int n,k,q,a[N],b[N],c[N],fa[N];
ll m;

int find(int x) {return x==fa[x]?x:fa[x]=find(fa[x]);}

int main() {
    IN(n,m,q),k=n;
    lep(i,1,q) IN(a[i],b[i],c[i]);
    lep(i,1,n) fa[i]=i;

    bool flag=false;
    lep(i,1,q) if(!c[i]) {if(find(a[i])!=find(b[i])) fa[find(a[i])]=find(b[i]),--k;}
    lep(i,1,q) if(c[i]) {
        flag=true;
        if(find(a[i])==find(b[i])) return puts("No"),0;
    }

    if(m<n-1) return puts("NO"),0;
    if(!flag) puts((k-1<=m-n+k&&m-n+k<=1ll*k*(k-1)/2)?"Yes":"No");
    else puts((k>2&&k<=m-n+k&&m-n+k<=1ll*k*(k-1)/2)?"Yes":"No");
    return 0;
}