点的标号必须是0到n-1
必须去除到自身的边,到自身的边的权为无穷大
#include<stdio.h>
#include<string.h>
#include<math.h>
#define M 1007
#define inf 0x3f3f3f
using namespace std;
int pre[M],vis[M],id[M];
int in[M];
int n,m;
struct Node//建立邻接表
{
int u,v;
int cost;
}E[M*M+5];
struct point//点的位置
{
int x,y,z;
}p[M];
int dis(point a,point b)
{
int ans=(fabs(a.x-b.x)+fabs(a.y-b.y)+fabs(a.z-b.z))*y;
if(a.z<b.z)
ans+=z;
return ans;
}
int direct_mst(int root,int nv,int ne)
{
int ret=0;
while(true)
{
//找最小入边
for(int i=0;i<nv;i++)
in[i]=inf;
for(int i=0;i<ne;i++)
{
int u=E[i].u;
int v=E[i].v;
if(E[i].cost<in[v]&&u!=v)
{
pre[v]=u;
/*
找最小入弧时,不断标记
if(u==root)
ansi=i;
*/
in[v]=E[i].cost;
}
}
for(int i=0;i<nv;i++)
{
if(i==root)continue;
if(in[i]==inf)return -1;
}
//找环
int cntnode=0;
memset(id,-1,sizeof(id));
memset(vis,-1,sizeof(vis));
in[root]=0;
for(int i=0;i<nv;i++)//标记每个环
{
ret+=in[i];
int v=i;
while(vis[v]!=i&&id[v]==-1&&v!=root)
{
vis[v]=i;
v=pre[v];
}
if(v!=root&&id[v]==-1)
{
for(int u=pre[v];u!=v;u=pre[u])
{
id[u]=cntnode;
}
id[v]=cntnode++;
}
}
if(cntnode==0)break;//无环
for(int i=0;i<nv;i++)
if(id[i]==-1)
id[i]=cntnode++;
//缩点,重新标记
for(int i=0;i<ne;i++)
{
int v=E[i].v;
E[i].u=id[E[i].u];
E[i].v=id[E[i].v];
if(E[i].u!=E[i].v)
{
E[i].cost-=in[v];
}
}
nv=cntnode;
root=id[root];
}
return ret;
}
int main()
{
while(scanf("%d%d%d%d",&n,&m),n|m)
{
int ansi,sum=0;//sum为所有边的和大一点
建图
。。。。。。
int ans=direct_mst(0,n,m);//n代表点的个数,m代表边的个数
if(ans==-1)
printf("poor XiaoA\n");//无法生成最小树形图
else
printf("%d\n",ans);
/*
如果是无向根,让你求最小费用及根时
printf("%d %d",ans-sum,ansi-m);
*/
}
return 0;
}
手机扫一扫
移动阅读更方便
你可能感兴趣的文章