25/7/2012 ICPC培训 第十天
啦啦啦
又来喽
今天一直在做小生成树问题。总共刷了7题，用来两种算法，prime和kurskal。
而且还都是HDU畅通工程系列的。
上午把prime算法的模板谢了出来，然后用模板刷了三题。
HDU1863、HDU1233、HDU1879
由于代码神似呀，这里只贴1863的代码了。
代码：
#include<iostream>#include<cstring>#include<vector>using namespace std;const int maxn=101; //顶点数 const int INF=0x7fffffff;struct edge //边 { int to; //到达的点 int cost; //边的花费 bool flag; //是否入选 };int choosed[maxn]; //已选边 int unchoosed[maxn]; //未选边 int nodeNum,edgeNum,MST; //顶点数、边数、最小生成树 bool choose[maxn]; //顶点是否已选 vector<edge> myV[maxn]; //图的邻接表 /* //这是无向图有重复边的建图，取重复边中最小的边存储 bool exist(int from,int to,int cost){ bool existFlag=false,smallFlag=false; for(int i=0;i<myV[from].size();i++) { if(myV[from][i].to==to) { existFlag=true; if(myV[from][i].cost>cost) { smallFlag=true; myV[from][i].cost=cost; break; } } } if(smallFlag) { for(int j=0;j<myV[to].size();j++) { if(myV[to][j].to==from) { myV[to][j].cost=cost; break; } } } if(existFlag) return true; return false;} void storeMap() //邻接表存图 { for(int j=0;j<maxn;j++) //清空 { myV[j].clear(); } memset(choose,false,sizeof(choose)); //标志图的各个点是否被选，不能重复 int from,to,cost,num=0; //从from到to花费cost的边 for(int i=0;i<edgeNum;i++) { scanf("%d%d%d",&from,&to,&cost); //把图上的所有点不重复的放到unchoosed[]表中 if(!choose[from]) { unchoosed[num++]=from; choose[from]=true; } if(!choose[to]) { unchoosed[num++]=to; choose[to]=true; } if(!exist(from,to,cost)) //图中存在重复边的处理 { edge tmp; tmp.flag=false; tmp.cost=cost; //无向图 tmp.to=to; myV[from].push_back(tmp); tmp.to=from; myV[to].push_back(tmp); } }}*///无向图，无重复边的建图 void storeMap() //邻接表存图 { for(int j=0;j<maxn;j++) //清空 { myV[j].clear(); } memset(choose,false,sizeof(choose)); //标志图的各个点是否被选，不能重复 int from,to,cost,num=0; //从from到to花费cost的边 for(int i=0;i<edgeNum;i++) { scanf("%d%d%d",&from,&to,&cost); //把图上的所有点不重复的放到unchoosed[]表中 if(!choose[from]) { unchoosed[num++]=from; choose[from]=true; } if(!choose[to]) { unchoosed[num++]=to; choose[to]=true; } edge tmp; tmp.flag=false; tmp.cost=cost; //无向图 tmp.to=to; myV[from].push_back(tmp); tmp.to=from; myV[to].push_back(tmp); }} void prime() //prime算法 { //初始化一些信息 MST=0; memset(choose,false,sizeof(choose)); choosed[0]=unchoosed[0]; choose[unchoosed[0]]=true; int choosedNum=1,from,to,cost,index; bool flag; while(choosedNum<nodeNum) { cost=INF; flag=false; for(int i=0;i<choosedNum;i++) { for(int j=0;j<myV[choosed[i]].size();j++) { edge tmp=myV[choosed[i]][j]; if(!choose[tmp.to] && !tmp.flag && tmp.cost<cost) { flag=true; //表示该次找到了一次路径 from=choosed[i]; to=tmp.to; cost=tmp.cost; index=j; } } } if(!flag) break; //当顶点没有都被选择时，只有有一次没能找到能够加入的顶点，图不畅通 myV[from][index].flag=true; for(int k=0;k<myV[to].size();k++) { if(myV[to][k].to==from) { myV[to][k].flag=true; break; } } choosed[choosedNum++]=to; choose[to]=true; MST+=cost; } if(flag) printf("%d\n",MST); else printf("?\n"); } int main(){ while(scanf("%d%d",&edgeNum,&nodeNum)==2,edgeNum) //输入图的点数、边数 { storeMap(); prime(); } system("pause"); return 0;}
可是下午第一题（HDU1875）就不顺喽，TLE、TLE、TLE。。。
prime算法O(n^2)的时间复杂度。。。
后来没办法，有写了kruskal算法模板，A啦
代码：
#include<iostream>#include<cmath>#include<queue>using namespace std;const int maxn=101; //图的最大节点数 struct edge //边 { int from; //起点 int to; //终点 double cost; //路径长 friend bool operator < (const edge &e1,const edge &e2) { return e1.cost>e2.cost; }};struct location //小岛位置 { int x,y;}temp[maxn];int father[maxn]; //用来做并查集 int nodeNum,edgeNum; //顶点数、边数 double MST; //最小生成树 priority_queue<edge> myQ; //kruskal算法，存放边 void inputLocation() //输入小岛位置 { for(int i=0;i<nodeNum;i++) { scanf("%d%d",&temp[i].x,&temp[i].y); }}void storeMap() //存储岛的桥构成的图 { while(!myQ.empty()) myQ.pop(); //清空 double dis,cost; edgeNum=0; for(int from=0;from<nodeNum;from++) { for(int to=from+1;to<nodeNum;to++) { dis=sqrt(pow(double(temp[from].x-temp[to].x),2)+pow(double(temp[from].y-temp[to].y),2)); if(dis>=10 && dis<=1000) { cost=dis*100; } else { continue; //如果两岛间距离不满足条件，该边不存在 } edgeNum++; edge e; e.from=from; e.to=to; e.cost=cost; myQ.push(e); } }} int find(int x) //查找 { if(x==father[x]) return father[x]; return father[x]=find(father[x]);}bool judge() //判断是否是一棵最小生成树 { int f=find(0); for(int i=1;i<nodeNum;i++) { if(f!=find(i)) { return false; } } return true;}void kruskal() //kruskal算法 { MST=0; for(int i=0;i<maxn;i++) { father[i]=i; } int num=0; //记录MST的边数 while(!myQ.empty() && num!=nodeNum-1) { edge e=myQ.top(); myQ.pop(); int fx=find(e.from); int fy=find(e.to); if(fx!=fy) { father[fx]=fy; MST+=e.cost; num++; } } if(judge()) printf("%.1lf\n",MST); else printf("oh!\n");} int main(){ int cas; scanf("%d",&cas); while(cas--) { scanf("%d",&nodeNum); inputLocation(); storeMap(); if(edgeNum<nodeNum-1) //特殊情况的处理 { printf("oh!\n"); continue; } kruskal(); } system("pause"); return 0;}
然后呢，又用kruskal模板A了HDU1301、1162、1102
基本就没遇到啥障碍了，求最小生成树没太大的问题，有时需要在建图上做点文章，其他都很套路化。
还有就是kruskal算法的时间复杂度为O(nlogn)的。
另外，还想说的是STL给我们带来很大的方便，包含头文件，直接调函数，个人觉得还是不能过度依赖。。。
最后，明天下午是第三次比赛啦。
听说不会太难的，希望自己能AK啦。。。