度度熊的王國(guó)戰(zhàn)略

Accepts: 310 Submissions: 4163 Time Limit: 40000/20000 MS (Java/Others) Memory Limit: 32768/132768 K (Java/Others) Problem Description

度度熊國(guó)王率領(lǐng)著喵哈哈族的勇士，準(zhǔn)備進(jìn)攻嘩啦啦族。

嘩啦啦族是一個(gè)強(qiáng)悍的民族，里面有充滿智慧的謀士，擁有無(wú)窮力量的戰(zhàn)士。

所以這一場(chǎng)戰(zhàn)爭(zhēng)，將會(huì)十分艱難。

為了更好的進(jìn)攻嘩啦啦族，度度熊決定首先應(yīng)該從內(nèi)部瓦解嘩啦啦族。

第一步就是應(yīng)該使得嘩啦啦族內(nèi)部不能同心齊力，需要內(nèi)部有間隙。

嘩啦啦族一共有n個(gè)將領(lǐng)，他們一共有m個(gè)強(qiáng)關(guān)系，摧毀每一個(gè)強(qiáng)關(guān)系都需要一定的代價(jià)。

現(xiàn)在度度熊命令你需要摧毀一些強(qiáng)關(guān)系，使得內(nèi)部的將領(lǐng)，不能通過(guò)這些強(qiáng)關(guān)系，連成一個(gè)完整的連通塊，以保證戰(zhàn)爭(zhēng)的順利進(jìn)行。

請(qǐng)問(wèn)最少應(yīng)該付出多少的代價(jià)。

Input

本題包含若干組測(cè)試數(shù)據(jù)。

第一行兩個(gè)整數(shù)n，m，表示有n個(gè)將領(lǐng)，m個(gè)關(guān)系。

接下來(lái)m行，每行三個(gè)整數(shù)u,v,w。表示u將領(lǐng)和v將領(lǐng)之間存在一個(gè)強(qiáng)關(guān)系，摧毀這個(gè)強(qiáng)關(guān)系需要代價(jià)w

數(shù)據(jù)范圍：

2<=n<=3000

1<=m<=100000

1<=u,v<=n

1<=w<=1000

Output

對(duì)于每組測(cè)試數(shù)據(jù)，輸出最小需要的代價(jià)。

Sample Input Copy 2 1 1 2 1 3 3 1 2 5 1 2 4 2 3 3 Sample Output Copy 1 3 思路： 就是判斷是否聯(lián)通，連通取所有點(diǎn)中，與其他點(diǎn)連接值和最小值點(diǎn)；不連通直接輸 出0。

AC代碼：

#include <iostream> #include <algorithm> #include <cstdio> #include <cmath> #include <cstring> using namespace std; int father[3010]; int M,N; int a,b,w; int find(int x){ while(x!=father[x]) x=father[x]; return x; } int main() { int i,j; int x,y; int sum[3010];while(cin>>N>>M){ j=1; memset(sum,0,sizeof(sum));for(i=1;i<=N;i++) father[i]=i; for(i=1;i<M+1;i++) { scanf("%d %d %d",&a,&b,&w); if(a==b)continue;//不加會(huì)重復(fù)sum[a]+=w;sum[b]+=w;x=find(a); y=find(b); if(x!=y){ j++; father[x]=y; } } if(j==N) {sort(sum+1, sum+N+1);printf("%d\n",sum[1]); } else printf("0\n"); } return 0; }

總結(jié)

以上是生活随笔為你收集整理的度度熊的王国战略的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。