模板題 . UVA--- 11183傳送
還有這道 POJ 3164 點這傳送
舉個例子：某個圖的部分圖中， 1->2權值為3邻遏， 2->1權值為4， 3->1權值為9赎线， 4->2權值為7糊饱。 那么可以看到，結點1和結點2是形成了一個環(huán)的。我們僅從其大小不知道刪除哪條邊比較好狭归，這時看到3->1權值為9文判， 如果走這條邊，那么接下來只能刪除掉2->1這條邊疚宇，同理走4->2的話就要刪除掉1->2這條邊。 那么就不妨建立新圖赏殃， 將1和2縮成一點，3->1的權值就變成了9-4=5讼撒， 4->2的權值變成了7-3=4股耽。 這樣的話物蝙，就相當于變相刪除了不需要走的邊了。形成新圖后诬乞，又變成了最小樹形圖的求解钠导，就這樣循環(huán)下去，直到圖中的最小邊集沒有環(huán)為止.
裸模板,直接上:
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<cstring>
#define ll long long int
#define db double
using namespace std;
const int maxn=1e3; //點數[0-n-1]
const int maxm=1e7; //邊數
const int inf=1e9;
int n,m;
struct edge
{
int u,v,w;
} s[maxn*maxn/2];
int pre[maxn]; //記錄前驅.
int id[maxn];
int vis[maxn];
int in[maxn];
void p(int *a,int n)
{
for(int i=1;i<=n;i++)
printf("%d%c",a[i],i==n?'\n':' ');
}
int dirMst(int root) //這種圖中根一定是確定的.
{
int ans=0;
while(1)
{
for(int i=0; i<n; i++)
in[i]=inf;
memset(id,-1,sizeof(id));
memset(vis,-1,sizeof(vis));
for(int i=0;i<m;i++)
{
int u=s[i].u;
int v=s[i].v;
int w=s[i].w;
if(w<in[v] && v != u )
{
pre[v] = u;
in[v] = w;
}
} //求最小入邊集
in[root]=0;
pre[root]=root;//為之后的遍歷做準備票堵，in[]用于存儲最小邊集
for(int i=0; i<n; i++)
{
if(in[i] == inf)
return -1;
ans += in[i];
} //此循環(huán)判斷是否有孤立節(jié)點悴势，同時計算當前最小權值和
int idx = 0;//idx是用來給新的節(jié)點賦名稱的（新序號）
for(int i=0;i<n;i++)
{
if(vis[i] == -1 )
{
int u = i;
while(vis[u] == -1){
vis[u] = i;
u = pre[u];
} //將vis[u]賦值為i是為了做標記
if(vis[u] != i || u == root ) continue; //判斷是否形成環(huán),未形成環(huán)就直接跳出.
//只有是環(huán)的才能進入for循環(huán).
for(int v=pre[u];v!=u;v=pre[v] )
id[v] = idx; //給環(huán)上的點賦值一個統一的標號措伐，形成一個新的點(id[i]用于存儲i點的新標號）
id[u] = idx++; //不在環(huán)上的新標號跟著另.
}
}
if(idx==0) break;//沒有環(huán)，跳出循環(huán)
for(int i=0;i<n;i++){
if(id[i]== -1){
id[i]=idx++;//在上一個循環(huán)給環(huán)賦予新的序號捧存，這一步是給非環(huán)的點新的序號，保證新圖中每個點有相應的標號
}
}
for(int i=0;i<m;i++) //造新圖.
{
s[i].w -= in[s[i].v];//把每個點的其他入邊看做環(huán)的入邊镰官，將增值賦給環(huán)的入邊傻咖，作為新圖的這個新的點的該條入邊的權值
s[i].u = id[s[i].u];
s[i].v = id[s[i].v];
} //這個循環(huán)是修改舊圖，把id中存儲的映射到圖中形成新圖
n = idx; //這個很重要卿操，要知道把環(huán)捏成一個點，那么圖中點個數改變了扇雕，所以循環(huán)次數改變
root = id[root];//給根新的標號
}
return ans;
}
int main()
{
int t;
cin >> t;
while(t--)
{
scanf("%d%d",&n,&m);
for(int i=0; i<m; i++)
{
scanf("%d%d%d",&s[i].u,&s[i].v,&s[i].w);
}
int res=dirMst(0); //以0為根開始搜.
printf("%d\n",res);
}
}
