同样的最小生成树,不一样的结局,求大佬指错

P1546 [USACO3.1] 最短网络 Agri-Net

太多或太少行,意思就是说你的输出有问题,可能是少输出了??
by xw001 @ 2017-10-22 17:33:16


看到你的头像,就感觉不会对
by weeryee @ 2017-10-27 16:15:12


赠一模板 ```cpp #include<iostream> #include<cstring> #include<algorithm> using namespace std; const int MAXN=101,MAXM=4951; int ust[MAXN]; void makeset(int size){ for(int i=1;i<=size;++i) ust[i]=i; } int finds(int x){ if(x^ust[x]) return ust[x]=finds(ust[x]); return x; } int n,m; int u[MAXM],v[MAXM],w[MAXM]; int r[MAXM]; bool cmp(int i,int j){return w[i]<w[j];} int kruskal(){ int ans=0; makeset(n); for(int i=1;i<=m;++i) r[i]=i; sort(r+1,r+m+1,cmp); for(int i=1,e,x,y;i<=m;++i){ e=r[i]; if((x=finds(u[e]))^(y=finds(v[e]))) ans+=w[e],ust[x]=y; } return ans; } int main(){ ios::sync_with_stdio(0); cin.tie(0); cin>>n; for(int i=1,W;i<=n;++i) for(int j=1;j<=n&&cin>>W;++j) if(j>i) u[++m]=i,v[m]=j,w[m]=W; cout<<kruskal(); return 0; } ```
by stationofldyc @ 2017-11-10 01:43:29


拿走不谢
by stationofldyc @ 2017-11-10 01:43:59


是不是exit(0)那里的问题,生成树的终点判断我一般写在for语句里面,比较稳妥
by Dog_Two @ 2017-12-11 17:29:38


你没有输出答案好吧
by 曼恩薄荷 @ 2017-12-27 18:41:15


|