struct node
{
int now,nex,dis;
node(int now,int nex,int dis):
now(now),nex(nex),dis(dis) {}
node(){}
} edge[40005];
int in[1005],id[1005],pre[1005],color[1005];
int mintreegraph(int n,int m,int root)
{
int ans=0;
while(1)
{
for(int i=1; i<=n; i++)
in[i]=inf;
for(int i=1; i<=m; i++)
{
int now=edge[i].now,nex=edge[i].nex;
if(now!=nex && edge[i].dis<in[nex])
pre[nex]=now,in[nex]=edge[i].dis;
}
in[root]=0;
for(int i=1; i<=n; i++)
if(in[i]==inf)return -1;
int cont=0;
memset(color,0,sizeof(color));
memset(id,0,sizeof(id));
for(int i=1; i<=n; i++)
{
ans+=in[i];
int x=i;
while(color[x]!=i && !id[x] && x!=root)
color[x]=i,x=pre[x];
if(!id[x] && x!=root)
{
cont++;
while(!id[x])id[x]=cont,x=pre[x];
}
}
if(!cont)return ans;
for(int i=1; i<=n; i++)
if(!id[i])id[i]=++cont;
for(int i=1; i<=m; i++)
{
int now=edge[i].now,nex=edge[i].nex;
edge[i].now=id[now],edge[i].nex=id[nex];
if(now!=nex)edge[i].dis-=in[nex];
}
n=cont,root=id[root];
}
}
最小树形图
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- 模板题 . UVA--- 11183传送 还有这道 POJ 3164 点这传送 举个例子：某个图的部分图中， 1...
- 这篇依旧是关于26 个世界级产品经理经验分享。上一期分享是否有解答你在创业公司战略制定方面的困惑呢？ 在讨论本期...
- 需求：广告图100%宽度，最小宽度1920，图片居中显示jQuery问题：浏览器可视宽度小于1920时，图片无法水...
