POJ 3164 Command Network
这是最小树形图的题目,1是根节点,在开始的时候自己建图。
输入n,m;代表有n个结点,接下来n行给出结点的坐标。
接下来m行给出i,j两个整数,代表i到j有连通,求出i到j的坐标距离,最后求最小树形图。
用朱刘算法可以解决。
代码:
[cpp]
#include<iostream>
#include<algorithm>
#include<string.h>
#include<cmath>
using namespace std;
const int maxn=105;
#define INF 0x7fffffff
double map[maxn][maxn],visit[maxn];
int pt[maxn][2],n,pre[maxn];
double Dist(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)
{
visit[u]=true;
for(int i=1; i<=n; i++)
if( !visit[i]&&map[u][i]<INF)
DFS(i);
}
bool Connected() //判断是否连通,如果连通一定存在最小树形图。
{
memset(visit,false,sizeof(visit));
int i,cnt=0;
DFS(1);
for( i=1; i<=n; i++)
if( !visit[i])
return false;
return true;
}
double ZLEdmonds(){
int i,j,k;
bool circle[maxn];
double ans=0;
memset(circle,false,sizeof(circle));
while(true){
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(visit,false,sizeof(visit));
while(!visit[j] && j!=1){
visit[j]=true;
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]=true;
}
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()
{
int m,i,j;
while( scanf("%d%d",&n,&m)!=EOF){
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]);
&
补充:软件开发 , C++ ,