题解 AT5201 【[AGC038D] Unique Path】

首先如果 $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`）。 ```cpp 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; } ```