3208424_wa.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <algorithm>

using namespace std;

int n, m;
struct edge
{
	int id, w;
	int u, v;
	bool operator < ( const edge x) const
	{
		return w < x.w;
	}
}E[1001], MST[1001];

int f[1001], can[10001], from[10001], id[10001];

int find(int p)
{
	if(f[p]!=p)
		return f[p]=find(f[p]);
	else
		return f[p];
}

int main()
{
	int i, j, TOT;
	int s1, s2;
	int p5, q5, p6, q6, id5, id6;

	scanf("%d%d",&n,&m);
	for(i = 0; i < m; i++)
	{
		scanf("%d%d%d",&E[i].u,&E[i].v,&E[i].w);
		E[i].v--;E[i].u--;E[i].id = i+1;
	}
	scanf("%d%d%d%d",&p5,&q5,&p6,&q6);
	id5 = 5;id6 = 6;
	if(p5 > p6)
	{
		swap(p5,p6);
		swap(q5,q6);
		swap(id5,id6);
	}
	sort(E,E+m);
	for(i = 0; i < n; i++)
	{
		f[i] = i;
	}
	TOT = 0;
	i = j = 0;
	while(i<m&&j<n-1)
	{
		s1 = find(E[i].u);
		s2 = find(E[i].v);
		if(s1!=s2)
		{
			f[s1] = s2;
			MST[j++] = E[i];
			TOT += E[i].w;
		}
		i++;
	}
	if(j!=n-1)
	{
		puts("Impossible");
		return 0;
	}
	memset(can,0,sizeof(can));
	can[0] = 1;
	for(i = 0; i < n-1; i++)
	{
		for(j = q5-MST[i].w; j >= 0; j--)
		{
			if(can[j]&&!can[j+MST[i].w])
			{
				can[j+MST[i].w] = 1;
				from[j+MST[i].w] = i;
			}
		}
	}
	i = q5;
	while(!can[i])
		i--;
	if(TOT - i > q6)
	{
		puts("Impossible");
		return 0;
	}
	printf("%d\n",p5*i+(TOT-i)*p6);
	for(j = 0; j < n-1; j++)
	{
		id[j] = id6;
	}
	if(i!=0)
	{
		while(i>=0)
		{
			id[from[i]] = id5;
			i -= MST[from[i]].w;
		}
	}
	for(i = 0; i < n-1; i++)
	{
		printf("%d %d\n",MST[i].id,id[i]);
	}
	return 0;
}