Решения задач acmp.ru
Главная
Вход
Регистрация
Воскресенье, 20.09.2020, 20:40Приветствую Вас Гость | RSS
Меню сайта

Категории раздела
Pascal [121]
C++ [76]

Поиск

Мини-чат
200

Легкий заработок!

Статистика

Онлайн всего: 1
Гостей: 1
Пользователей: 0

Форма входа

Главная » Файлы » C++

0142 Минимальный каркас

Скачать файл можно после просмотра рекламы:

05.06.2012, 02:53
#include <stdio.h>
#include <memory.h>

struct edge
{
unsigned int v1, v2, w;
};

int main()
{
int way = 0;
unsigned int vertex_n, edges_n;
edge    tmp;
FILE * f = fopen("input.txt", "r");
fscanf(f, "%d %d", & vertex_n, & edges_n);

edge * edgBuff = new edge [edges_n];
bool * vertBuff = new bool [vertex_n];
memset(vertBuff, NULL, sizeof(bool) * vertex_n);

for (int i = 0; i<edges_n; i++)
{
fscanf(f, "%d %d %d", &edgBuff[i].v1, &edgBuff[i].v2, &edgBuff[i].w); 
edgBuff[i].v1--;
edgBuff[i].v2--;
}

for (int i = 0; i<edges_n; i++)
for (int j = 0; j<edges_n; j++)
if ((edgBuff[i].w < edgBuff[j].w)&&(i>j))
{
tmp = edgBuff[j];
edgBuff[j] = edgBuff[i];
edgBuff[i] = tmp;
}


vertBuff[edgBuff[0].v1] = true;
vertBuff[edgBuff[0].v2] = true;

int p (2), k(1);
way = edgBuff[0].w;
do 
{
if ((vertBuff[edgBuff[k].v1]+vertBuff[edgBuff[k].v2]) == 1)
{
vertBuff[edgBuff[k].v1] = true;
vertBuff[edgBuff[k].v2] = true;
p++;
way += edgBuff[k].w;
k = 0;
}
k++;
} while (p<vertex_n);

f = fopen("output.txt", "wt");
fprintf(f, "%d", way);
fclose(f);

return 0;
Категория: C++ | Добавил: shum
Просмотров: 1433 | Загрузок: 0
Всего комментариев: 0
Добавлять комментарии могут только зарегистрированные пользователи.
[ Регистрация | Вход ]
Это интересно!


Copyright MyCorp © 2020