Time Limit: 1000MS | Memory Limit: 131072K | |
Total Submissions: 10253 | Accepted: 2976 |
Description
After a long lasting war on words, a war on arms finally breaks out between littleken’s and KnuthOcean’s kingdoms. A sudden and violent assault by KnuthOcean’s force has rendered a total failure of littleken’s command network. A provisional network must be built immediately. littleken orders snoopy to take charge of the project.
With the situation studied to every detail, snoopy believes that the most urgent point is to enable littenken’s commands to reach every disconnected node in the destroyed network and decides on a plan to build a unidirectional communication network. The nodes are distributed on a plane. If littleken’s commands are to be able to be delivered directly from a node A to another node B, a wire will have to be built along the straight line segment connecting the two nodes. Since it’s in wartime, not between all pairs of nodes can wires be built. snoopy wants the plan to require the shortest total length of wires so that the construction can be done very soon.
Input
The input contains several test cases. Each test case starts with a line containing two integer N (N ≤ 100), the number of nodes in the destroyed network, and M (M ≤ 104), the number of pairs of nodes between which a wire can be built. The next N lines each contain an ordered pair xi and yi, giving the Cartesian coordinates of the nodes. Then follow M lines each containing two integers i and j between 1 and N(inclusive) meaning a wire can be built between node i and node j for unidirectional command delivery from the former to the latter. littleken’s headquarter is always located at node 1. Process to end of file.
Output
For each test case, output exactly one line containing the shortest total length of wires to two digits past the decimal point. In the cases that such a network does not exist, just output ‘poor snoopy
’.
Sample Input
4 6 0 6 4 6 0 0 7 20 1 2 1 3 2 3 3 4 3 1 3 2 4 3 0 0 1 0 0 1 1 2 1 3 4 1 2 3
Sample Output
31.19 poor snoopy
Source
这是最小树形图的题目,1是根节点,在开始的时候自己建图。
输入n,m;代表有n个结点,接下来n行给出结点的坐标。
接下来m行给出i,j两个整数,代表i到j有连通,求出i到j的坐标距离,最后求最小树形图。
用朱刘算法可以解决。
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> using namespace std; const int VN=110; const int INF=99999999; double map[VN][VN]; int n,m,vis[VN],pt[VN][2],pre[VN]; double Cal(int i,int j){ return sqrt(pow(pt[i][0]-pt[j][0],2.0)+pow(pt[i][1]-pt[j][1],2.0)); } void DFS(int u){ vis[u]=1; for(int i=1;i<=n;i++) if(!vis[i] && map[u][i]!=INF) DFS(i); } bool Connected(){ //判断是否连通,如果连通一定存在最小树形图。 memset(vis,0,sizeof(vis)); DFS(1); for(int i=1;i<=n;i++) if(!vis[i]) return 0; return 1; } double ZLEmonds(){ int i,j,k; bool circle[VN]; double ans=0; memset(circle,0,sizeof(circle)); while(1){ for(i=2;i<=n;i++){ //找出最短弧集合E0 if(circle[i]) continue; pre[i]=i; map[i][i]=INF; for(j=1;j<=n;j++){ if(circle[j]) continue; if(map[j][i]<map[pre[i]][i]) pre[i]=j; } } for(i=2;i<=n;i++){ if(circle[i]) continue; j=i; memset(vis,0,sizeof(vis)); while(!vis[j] && j!=1){ vis[j]=1; j=pre[j]; } if(j==1) //检查是否有环,能找到根节点说明没环 continue; i=j; ans+=map[pre[i]][i]; for(j=pre[i];j!=i;j=pre[j]){ //i不用标记,用作后面缩点用 ans+=map[pre[j]][j]; circle[j]=1; } for(j=1;j<=n;j++){ if(circle[j]) continue; if(map[j][i]!=INF) map[j][i]-=map[pre[i]][i]; } for(j=pre[i];j!=i;j=pre[j]) //将环中所有的点成点i,改变边 for(k=1;k<=n;k++){ if(circle[k]) continue; map[i][k]=min(map[i][k],map[j][k]); if(map[k][j]!=INF) map[k][i]=min(map[k][i],map[k][j]-map[pre[j]][j]); } break; } if(i>n){ //求出最小树形图的权值 for(j=2;j<=n;j++){ if(circle[j]) continue; ans+=map[pre[j]][j]; } break; } } return ans; } int main(){ //freopen("input.txt","r",stdin); while(~scanf("%d%d",&n,&m)){ int i,j; for(i=1;i<=n;i++) for(j=1;j<=n;j++) map[i][j]=INF; for(i=1;i<=n;i++) scanf("%d%d",&pt[i][0],&pt[i][1]); while(m--){ scanf("%d%d",&i,&j); map[i][j]=Cal(i,j); } if(!Connected()) printf("poor snoopy\n"); else printf("%.2f\n",ZLEmonds()); } return 0; }
相关推荐
北大POJ2531-Network Saboteur 解题报告+AC代码
北大POJ初级-图算法 解题报告+AC代码
NULL 博文链接:https://128kj.iteye.com/blog/1705139
poj 1459 Power Network.md
解决算法问题 poj1082, poj1150, poj1180, poj1201, poj1222,代码完成所给题目要求。
POJ题目分类,列出了所有的类目,里面写了一些很好的框架。
poj上的算法题目分类,对于大家想练习算法的同鞋可以参考一下,里面按类列出了各种算法的题号。
POJ各题算法分类和题目推荐 ACM必看 POJ各题算法分类和题目推荐 ACM必看 POJ各题算法分类和题目推荐 ACM必看
北大POJ初级-基本算法 解题报告+AC代码
NULL 博文链接:https://128kj.iteye.com/blog/1704752
NULL 博文链接:https://128kj.iteye.com/blog/1707218
POJ中级图算法所有题目【解题报告+AC代码】 我的所有POJ解题报告 http://blog.csdn.net/lyy289065406/article/details/6642573
北大POJ1459-Power Network 解题报告+AC代码
【二分图顶点覆盖->最小割->最大流->Dinic算法求解】 解题报告+AC代码 http://hi.csdn.net/!s/WKVPR0 ----> 我的所有POJ解题报告 http://blog.csdn.net/lyy289065406/article/details/6642573
poj acm题解,包括绝大部分poj题目的题解,可以供acm爱好者学习研究
NULL 博文链接:https://200830740306.iteye.com/blog/603493
关于C++ 算法 北大网站POJ 八数码问题
用贪心算法解决POJ 1065的木棍处理问题
这里面有介绍ACM中的算法,包括算法分类,以及对应在POJ上面的训练题目
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类