免费做淘宝店铺招牌的网站,做网站类网站费用,邯郸市出租房屋信息网,常州网站建设服务一.题目
P1550 [USACO08OCT] Watering Hole G - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 二.分析
1.我们是要使所有的农场都要有水
2.可以从起点引水#xff0c;也可以互相引水。
3.费用要最小
这时我们可以想到最小生成树#xff0c;建立一个虚拟节点即可。思路一…一.题目
P1550 [USACO08OCT] Watering Hole G - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 二.分析
1.我们是要使所有的农场都要有水
2.可以从起点引水也可以互相引水。
3.费用要最小
这时我们可以想到最小生成树建立一个虚拟节点即可。思路一目了然。 三.参考代码
#includebits/stdc.h
#define maxn 91000
using namespace std;
struct Edge{int u,v,w;
}edge[maxn];
int n,cnt;
int fa[305];
int find(int x){return xfa[x] ? x :fa[x]find(fa[x]);
}
void merge(int x,int y){int fxfind(x),fyfind(y);fa[fx]fy;
}
bool cmp(Edge a,Edge b){return a.wb.w;
}
long long ans;
void kruskal(){sort(edge1,edgecnt1,cmp);int tot0;for(int i1;icnt;i){int xedge[i].u,yedge[i].v;if(find(x)find(y)) continue;tot;ansedge[i].w;merge(x,y);if(totn) return;}
}
int main(){scanf(%d,n);int w;for(int i1;in;i){scanf(%d,w);edge[cnt](Edge){0,i,w};}for(int i1;in;i){for(int j1;jn;j){scanf(%d,w);if(w!0){edge[cnt](Edge){i,j,w};}}}for(int i1;in;i) fa[i]i;kruskal();coutans;return 0;
}四.总结
当看到这些条件可以想到最小生成树
1.涉及到每个节点
2.最小/最大的值
3.一般都要用到虚拟节点以处理初始点
