记录编号	41108	评测结果	AWWWTWTTTT
题目名称	[河南省队2012] 阻击补给线	最终得分	10
用户昵称	苏轼	是否通过	未通过
代码语言	C++	运行时间	1.135 s
提交时间	2012-07-20 16:25:41	内存使用	0.32 MiB

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<vector>
using namespace std;
vector<int>a[505];
vector<int>b[505];
int number;
int n,m,answer=1000000000;
bool used[505]={0};
int main()
{
	freopen ("t2bb.in","r",stdin);
	freopen ("t2bb.out","w",stdout);
	scanf("%d%d\n",&n,&m);
	for (int i=0;i<m;i++)
	{
		int d,e,f;
		cin>>d>>e>>f;
		a[d].push_back(e);
		a[e].push_back(d);
		b[d].push_back(f);
		b[e].push_back(f);
	}
	number=n;
	while (number>0)
	{
		bool use[505]={0};
		int qi,shu=1;
		for (int i=0;i<n;i++)
		{
			if (!used[i])
			{
				qi=i;
				break;
			}
		}
		int q[600]={0};
		q[0]=qi;
		int answ,ans=0,ji;
		while (shu<=number)
		{
			ans=0;
			for (int i=0;i<shu;i++)
			{
				for (int j=0;j<a[q[i]].size();j++)
				{
					int k;
					k=a[q[i]][j];
					if (use[k]&&used[k])
						continue;
					if (b[q[i]][j]>ans)
					{
						ji=q[i];
						answ=k;
						ans=b[q[i]][j];
					}
				}
			}
			q[shu]=answ;
			shu++;
		}
		used[answ]=1;
		int num=0;
		for (int i=0;i<a[answ].size();i++)
		{
			a[ji].push_back(a[answ][i]);
			b[ji].push_back(b[answ][i]);
			num+=b[answ][i];
		}
		if (num<answer)
			answer=num;
		number--;
	}
	cout<<answer;
	return 0;
}