Agri Net POJ1258 && Constructing Roads POJ2421
2024-10-12 02:27:33
题意,在给出的图中,使用最小花费的边,使这个图仍然连通。
#include <cstdio> #include <algorithm> #include <cstring> using namespace std; const int maxn=10005; int head[maxn]; int n,len=0,counter; long long ans; struct node{ int v,cost,u; //操作符的重写默认是小于等于 bool operator < (const node& tmp) const{ return cost< tmp.cost; } }gra[maxn]; struct BingCha{ //并查集 int father[105]; void initial(){ //初始化不要忘记 for(int i=1;i<=n;i++){ father[i]=i; } } int getfather(int v){ if(father[v]==v)return v; return father[v]=getfather(father[v]); //状态压缩 } bool findtwo(int a,int b){ //看是否是同根的 return getfather(a)==getfather(b); } void unioned(int a,int b){ int fa=father[a],fb=father[b]; father[fa]=fb; } }jihe; void addedge(int u,int v,int cost){ gra[len].u=u; gra[len].v=v; gra[len].cost=cost; len++; } void init(){ len=0; counter=1;ans=0; int x; memset(head,-1,sizeof(head)); //memset gra? for(int i=1;i<=n;i++){//add the edges for(int j=1;j<=n;j++){ scanf("%d",&x); if(i<j){ addedge(i,j,x); } } } } int main(){ while(scanf("%d",&n)!=EOF){ init(); sort(gra,gra+len); //已经有序,那么从小值开始选边添加即可,也保证了最优结果 int idx=0; jihe.initial(); while(counter<n || idx<len){ if(!jihe.findtwo(gra[idx].u,gra[idx].v)){ //如果不同根,就选择这条边,执行更新操作 ans+=gra[idx].cost; counter++; jihe.unioned(gra[idx].u,gra[idx].v); } idx++; } printf("%d\n",ans); } }
2421 也是裸的mst:只要把已经建了的作为输入先处理一下就好了。
#include <cstdio> #include <algorithm> #include <cstring> using namespace std; ; int n,len,counter; long long ans; struct node{ int v,cost,u; bool operator < (const node& tmp) const{ return cost< tmp.cost; } }gra[maxn*(maxn-)>>]; struct BingCha{ ]; void initial(){ ;i<=n;i++){ father[i]=i; } } int getfather(int v){ if(father[v]==v)return v; return father[v]=getfather(father[v]); } bool findtwo(int a,int b){ return getfather(a)==getfather(b); } void unioned(int a,int b){ int fa=getfather(a),fb=getfather(b); father[fa]=fb; } }jihe; void addedge(int u,int v,int cost){ gra[len].u=u; gra[len].v=v; gra[len].cost=cost; len++; } int findxy(int x,int y){ if(x>y){int z=y;y=x;x=z;} ,id=; ;i<x;i++){ id+=j--; } y-=x;// here!!! id+=y; return id; } void init(){ len=; counter=;ans=; jihe.initial(); int x,q,y; //memset gra? ;i<=n;i++){//add the edges ;j<=n;j++){ scanf("%d",&x); if(i<j){ addedge(i,j,x); } } } scanf("%d",&q); ;i<=q;i++){ scanf("%d%d",&x,&y); ; if(!jihe.findtwo(gra[idx].u,gra[idx].v)){ counter++; jihe.unioned(gra[idx].u,gra[idx].v); } } } int main(){ while(scanf("%d",&n)!=EOF){ init(); sort(gra,gra+len); ; while(counter<n){//|| idx<=len if(!jihe.findtwo(gra[idx].u,gra[idx].v)){ ans+=gra[idx].cost; counter++; jihe.unioned(gra[idx].u,gra[idx].v); } idx++; } printf("%d\n",ans); } }
最新文章
- Javascript9张思维导图
- php常用函数汇总
- asp.net中导出Excel的方法
- DX11.2 Tiled Resource Pool
- Java Swing的进化
- XMPP 常见错误:(<;failure xmlns="urn:ietf:params:xml:ns:xmpp-sasl">;<;not-autho
- eclipse中使用tomcat图解
- 88 Merge Sorted Array(归并排序Easy)
- jquery1.9学习笔记 之层级选择器(一)
- 挖一下插件v1.3版本发布
- QTP脚本汇总比较有价值
- Hibernate的一对多查询及去掉重复的对象distinct
- qemu 模拟-arm-mini2440开发板-启动u-boot,kernel和nfs文件系统【转】
- 关于datagrid中控件利用js调用后台方法事件的问题
- android 开发之 ListView 与Adapter 应用实践
- js_jquery_创建cookie有效期问题_时区问题
- JSON 解析 (三)—— FastJSON与Jackson比较
- 逻辑运算的妙用-Single Number
- WebForm母版页
- 24-Python3 OS