算法
最小生成树
易错
在加的时候如果优惠价比原价高就加原价(这也是很多人90分的原因)
代码
#include <cstdio> #include <algorithm> using namespace std; int father[510],ans,g[510][510]; inline int getfather(int x) { if(father[x] == x) return x; return father[x] = getfather(father[x]); } inline void merge(int x,int y) { int fx = getfather(x); int fy = getfather(y); father[fx] = fy; } int n,m; struct EDGE { int u,v,w; } edge[250010]; inline bool cmp(const EDGE &a,const EDGE &b){return a.w < b.w;} int main() { scanf("%d%d",&ans,&n);//废物利用直接以ans读入 for(register int i = 1;i <= n;++i) for(register int j = 1;j <= n;++j) { scanf("%d",&g[i][j]); if(g[i][j] == 0||g[i][j]>ans) g[i][j] = ans;//这步不能丢,注意这里ans还没有发生改变 } for(register int i = 1;i <= n;++i) for(register int j = 1;j < i;++j) { edge[++m].u = i; edge[m].v = j; edge[m].w = g[i][j]; } for(register int i = 1;i <= n;++i) father[i] = i; sort(edge + 1,edge + m + 1,cmp); for(register int i = 1;i <= m;++i) if(getfather(edge[i].u) != getfather(edge[i].v)) { ans += edge[i].w;//更新答案 merge(edge[i].u,edge[i].v); } printf("%d\n",ans); }