POJ 1861 Network(Kruskyal)
1757 ワード
転送ゲート:http://poj.org/problem?id=1861
この問題は普通の最小樹水問題です.一番小さい木を作るのは初めてです.1 Aです.とても楽しいです.
この問題はspecial judgeですので、サンプルは過ぎないまま提出しました.使用した辺を一つのスタックで保存してから戻ってきます.
この問題は普通の最小樹水問題です.一番小さい木を作るのは初めてです.1 Aです.とても楽しいです.
この問題はspecial judgeですので、サンプルは過ぎないまま提出しました.使用した辺を一つのスタックで保存してから戻ってきます.
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<iostream>
#include<cstring>
#include<stack>
using namespace std;
struct node{
int s,e;
int v;
node(int a,int b,int c):s(a),e(b),v(c){}
};
bool cmp(node a,node b)
{
return a.v<b.v;
}
vector<node> edge;
stack<int> st;
int pre[1010];
int Find(int x)// +
{
int s;
for(s=x;pre[s]>=0;s=pre[s]);
while(s!=x)
{
int t=pre[x];
pre[x]=s;
x=t;
}
return s;
}
void join(int a,int b)// , ,
{
int fa=Find(a),fb=Find(b);
int sum=pre[fa]+pre[fb];
if(pre[fa]>pre[fb])
{
pre[fa]=fb;
pre[fb]=sum;
}
else{
pre[fb]=fa;
pre[fa]=sum;
}
}
int kruskal(int n)
{
int ans=0;
int i,j;
int cnt=0;//
for(i=0;i<edge.size();i++)// , ,
{
if(Find(edge[i].s)!=Find(edge[i].e))
{
join(edge[i].s,edge[i].e);
cnt++;
ans=max(edge[i].v,ans);
st.push(i);
}
if(cnt==n-1)
break;
}
return ans;
}
int main()
{
int n,m;
while(scanf("%d%d",&n,&m)!=EOF)
{
while(!st.empty())
st.pop();
edge.clear();
memset(pre,-1,sizeof(pre));
int i,j;
for(i=0;i<m;i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
edge.push_back(node(a,b,c));
}
sort(edge.begin(),edge.end(),cmp);
printf("%d
",kruskal(n));
printf("%d
",st.size());
while(!st.empty())
{
printf("%d %d
",edge[st.top()].s,edge[st.top()].e);
st.pop();
}
}
return 0;
}