Description

Input

Output

Sample Input

1
5 7
1 2 2
1 4 1
2 4 2
4 3 2
2 3 1
4 5 1
1 5 2

Sample Output

5
No

Data Constraint

Hint

Solution

• 顯然，第一個詢問就是簡單的最小生成樹，直接打一個 Kruskal 算法過掉。

• 但問題是如何判斷答案是否是唯一的?

• 考慮枚舉一條未加入最小生成樹中的邊 x，若加入其中，則必定構(gòu)成一個環(huán)。

• 且該環(huán)除了 x 以外的邊的最大權(quán)值一定不比 x 大，否則 x 可以代替該邊，不符最小生成樹的定義。

• 那么我們只要找到那個最大權(quán)值，判斷是否小于 x 的權(quán)值即可。

• 若有某個邊相等，則還有別的連接方案，不然答案就是唯一的。

• 枚舉邊已經(jīng)是 O(M) 的了，那么如何快速求出路徑上的最大權(quán)值呢？

• 可以運用倍增。開始時將最小生成樹定一個根，并處理出該樹的信息。

• 之后倍增維護(hù)路徑上的最大值即可，總時間復(fù)雜度為 O(M?log?M) 。

Code

#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; const int N=1e5+1; struct data {int x,y,z; }a[N<<1]; int tot; int first[N],next[N<<2],en[N<<2],w[N<<2]; int f[N],fa[N][18],mx[N][18],dep[N]; bool bz[N<<1]; inline int read() {int X=0,w=1; char ch=0;while(ch<'0' || ch>'9') {if(ch=='-') w=-1;ch=getchar();}while(ch>='0' && ch<='9') X=(X<<3)+(X<<1)+ch-'0',ch=getchar();return X*w; } inline bool cmp(data x,data y) {return x.z<y.z; } inline int max(int x,int y) {return x>y?x:y; } inline int get(int x) {if(f[x]==x) return x;return f[x]=get(f[x]); } inline void insert(int x,int y,int z) {next[++tot]=first[x];first[x]=tot;en[tot]=y;w[tot]=z; } inline void dfs(int x) {dep[x]=dep[fa[x][0]]+1;for(int i=first[x];i;i=next[i])if(en[i]!=fa[x][0]){fa[en[i]][0]=x;mx[en[i]][0]=w[i];dfs(en[i]);} } inline int lca(int x,int y) {if(dep[x]<dep[y]) swap(x,y);int val=0;for(int i=log2(dep[x]);i>=0;i--)if(dep[fa[x][i]]>=dep[y]) val=max(val,mx[x][i]),x=fa[x][i];if(x==y) return val;for(int i=log2(dep[x]);i>=0;i--)if(fa[x][i]!=fa[y][i]){val=max(val,mx[x][i]);val=max(val,mx[y][i]);x=fa[x][i],y=fa[y][i];}val=max(val,mx[x][0]);val=max(val,mx[y][0]);return val; } int main() {int T=read();while(T--){int n=read(),m=read();long long ans=0;memset(bz,false,sizeof(bz));memset(first,tot=0,sizeof(first));for(int i=1;i<=m;i++) a[i].x=read(),a[i].y=read(),a[i].z=read();sort(a+1,a+1+m,cmp);for(int i=1;i<=n;i++) f[i]=i;for(int i=1,k=0;i<=m;i++){int x=a[i].x,y=a[i].y,z=a[i].z;int f1=get(x),f2=get(y);if(f1!=f2){f[f1]=f2;ans+=z;insert(x,y,z);insert(y,x,z);bz[i]=true;if(++k==n-1) break;}}printf("%lld\n",ans);mx[1][0]=0;dfs(1);for(int j=1;j<18;j++)for(int i=1;i<=n;i++){fa[i][j]=fa[fa[i][j-1]][j-1];mx[i][j]=max(mx[fa[i][j-1]][j-1],mx[i][j-1]);}bool pd=false;for(int i=1;i<=m;i++)if(!bz[i])if(a[i].z==lca(a[i].x,a[i].y)){pd=true;break;}if(pd) printf("No\n"); else printf("Yes\n");}return 0; }

總結(jié)

以上是生活随笔為你收集整理的JZOJ 5275. 水管的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。