#includestructedge{intu,v,w,flag;}p[4952];intn,m;intf[101];intused[101];intcmp(constvoid*aa,constvoid*bb){return((structedge*)aa)->w-((structedge*)bb)->w;}intfind(intx){returnf[x]==" />

亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

poj1679(The Unique MST)Kruskal

系統 1616 0
    ?
  


最近略忙,就不寫題意思路什么的,直接上代碼。

    #include<stdio.h>

#include<stdlib.h>

struct edge

{

	int u,v,w,flag;

}p[4952];

int n,m;

int f[101];

int used[101];

int cmp(const void*aa,const void*bb)

{

	return ((struct edge*)aa)->w-((struct edge*)bb)->w;

}

int find(int x)

{

	return f[x]==x?x:(f[x]=find(f[x]));

}

int Kruskal()

{

	int sum=0,i,x,y,t=0;

	for(i=0;i<m;i++)

	{

		x=find(p[i].u);

		y=find(p[i].v);

		if(x!=y)

		{

			f[x]=y;

			sum+=p[i].w;

			used[t]=i;

			t++;

			if(t==n-1) break;

		}

	}

	return sum;

}

int reKruskal()

{

	int sum=0,i,x,y,t=0;

	for(i=0;i<m;i++)

	{

		x=find(p[i].u);

		y=find(p[i].v);

		if(x!=y&&!p[i].flag)

		{

			f[x]=y;

			sum+=p[i].w;

			t++;

			if(t==n-1) break;

		}

	}

	return sum;

}

int main()

{

	//freopen("12.3.4.input.txt","r",stdin);

	int t,i,j,ans,tans,k,pt=0;

	scanf("%d",&t);

	for(i=0;i<t;i++)

	{

		scanf("%d %d",&n,&m);

		for(j=1;j<=n;j++) f[j]=j;

		for(j=0;j<n;j++) used[j]=-1;

		for(j=0;j<m;j++)

		{

			scanf("%d %d %d",&p[j].u,&p[j].v,&p[j].w);

			p[j].flag=0;

		}

		qsort(p,m,sizeof(p[0]),cmp);

		ans=Kruskal();

		pt=0;

		for(j=0;j<n-1;j++)

		{

			p[used[j]].flag=1;

			for(k=1;k<=n;k++) f[k]=k;

			tans=reKruskal();

            p[used[j]].flag=0;

			if(ans==tans&&ans!=0) 

			{

				pt=1;

				break;

			}

		}

		if(pt) printf("Not Unique!\n");

		else printf("%d\n",ans);

	}

	return 0;

}


  


?

?

poj1679(The Unique MST)Kruskal


更多文章、技術交流、商務合作、聯系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯系: 360901061

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦!?。?/p>

發表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 天天摸天天干天天操 | 97se亚洲国产综合自在线观看 | 国产羞羞事1000部在线观看 | 九九香蕉网 | 色在线观看视频 | 91粉色视频在线观看 | 一级特黄特色aa大片 | 国产三级久久 | 狠狠久久| 日韩精品片 | 亚洲性生活 | 在线观看免费毛片 | 亚洲欧美国产高清va在线播放 | 桃色视频在线观看 | 997在线观看视频国产 | 91最新在线 | 欧美精品久久久久久久久大尺度 | 亚洲国产天堂久久九九九 | a v在线男人的天堂观看免费 | 日韩在线中文字幕 | 国产欧美一区二区三区视频 | 天天躁狠狠躁狠狠躁夜夜躁 | 久久影院一区二区三区 | 国模无水印一区二区三区 | 伊人免费网 | 国产综合精品久久久久成人影 | 青春草久久 | 狠狠色综合久久丁香婷婷 | 福利视频在线免费观看 | 欧美激情第一区 | 欧美一级特黄乱妇高清视频 | 天天干天天插 | 成人欧美一区二区三区在线 | 国产96福利视频在线观看 | 国产精品真实对白精彩久久 | 亚洲mv | 日韩亚洲欧美综合一区二区三区 | 国产精品第二页在线播放 | 久久久青草青青国产亚洲免观 | 成人精品一区二区久久久 | 日本一区不卡视频 |