spanning tree prim C++

#include <iostream>
#include<string>
#include<vector>
using namespace std;
struct link{
string node1;
string node2;
int weighted;
};
void split(string, vector<link>*);
int count_node(vector<link>*, vector<string>*);
int main()
{
vector<link>input;                      //原始input
vector<string>n_list;     //node的list
vector<string>new_n_list;     //node的list
vector<link>Candidate;
vector<link>answer;                     //最後要輸出的結果
string command;                         //每一行輸入
int size, edge_count = 0, node_count;
while (true)
{
getline(cin, command);
if (command == "exit")
break;
split(command, &input);
}
node_count = count_node(&input, &n_list);                   //算有幾個點 & 做出點的list

/////prim//////
int  total_weighted = 0;
link tmp;
new_n_list.push_back(n_list[0]);       //以第一個當作起點
n_list.erase(n_list.begin());
for (int i = 0; edge_count != (node_count - 1); i++)
{

string n1, n2;
for (int j = 0; j < new_n_list.size(); j++)    //需要想法QAQ
{
n1 = new_n_list[j];
for (int k = 0; k < n_list.size(); k++)
{
n2 = n_list[k];
for (int l = 0; l < input.size(); l++)
{
if (n1==input[l].node1 && n2==input[l].node2)
{
Candidate.push_back(input[l]);
}
else if (n1==input[l].node2 && n2==input[l].node1)
{
Candidate.push_back(input[l]);
}
}
}
}
tmp = Candidate[0];
for (int j = 0; j < Candidate.size(); j++)         //挑最小的
{
if (tmp.weighted>Candidate[j].weighted)
tmp = Candidate[j];
}
answer.push_back(tmp);
edge_count++;
bool flag = 0;           //scan node1 in or not in
for (int j = 0; j < new_n_list.size(); j++)
{
if (tmp.node1 == new_n_list[j])
{
flag = 1;
break;
}
}
if (!flag)
{
new_n_list.push_back(tmp.node1);
for (int j = 0; j < n_list.size(); j++)    //刪除另一個set裡面的東西
{
if (tmp.node1 == n_list[j])
{
n_list.erase(n_list.begin() + j);
break;
}
}
}

flag = 0;              //scan node2 in or not in
for (int j = 0; j < new_n_list.size(); j++)
{
if (tmp.node2 == new_n_list[j])
{
flag = 1;
break;
}
}
if (!flag)
{
new_n_list.push_back(tmp.node2);
for (int j = 0; j < n_list.size(); j++)
{
if (tmp.node2 == n_list[j])
{
n_list.erase(n_list.begin() + j);
break;
}
}
}
for (int j = 0; j < input.size(); j++)
{
if ((tmp.node1 == input[j].node1) && (tmp.node2 == input[j].node2) && (tmp.weighted == input[j].weighted))
{
input.erase(input.begin() + j);
break;
}
}
Candidate.clear();
}

size = answer.size();          //印答案
for (int i = 0; i < size; i++)
{
cout << answer[i].node1 << "-" << answer[i].node2 << "  " << answer[i].weighted << endl;
total_weighted = total_weighted + answer[i].weighted;
}
cout << "total weighted = " << total_weighted << endl;

return 0;
}
void split(string input, vector<link>* data)
{
int dash_pos, space_pos;
int str_len = input.length();
link push_back;
string tmp = "";
for (int i = 0; i < str_len; i++)  //找 - 位置
{
if (input[i] == '-')
{
dash_pos = i;
break;
}
}
for (int i = dash_pos + 1; i < str_len; i++)//找 空白 位置
{
if (input[i] == ' ')
{
space_pos = i;
break;
}
}
for (int j = 0; j < dash_pos; j++)
tmp = tmp + input[j];
push_back.node1 = tmp;
tmp = "";
for (int j = dash_pos + 1; j < space_pos; j++)
tmp = tmp + input[j];
push_back.node2 = tmp;
tmp = "";
for (int j = space_pos + 1; j < str_len; j++)
tmp = tmp + input[j];
push_back.weighted = atoi(tmp.c_str());
data->push_back(push_back);
}
int count_node(vector<link>* data, vector<string>* node_set)    //算點數 同時做出點的list
{
int count = 0;
int size = data->size();
int len;
for (int i = 0; i < size; i++)
{
link tmp = (*data)[i];
string node1 = tmp.node1;
string node2 = tmp.node2;
bool node1_flag = 0, node2_flag = 0;
len = node_set->size();
for (int j = 0; j < len; j++)
{
if (node1 == (*node_set)[j])
{
node1_flag = 1;
break;
}
}
if (node1_flag == 0)
{
(*node_set).push_back(node1);
count++;
}
len = (*node_set).size();
for (int k = 0; k < len; k++)
{
if (node2 == (*node_set)[k])
{
node2_flag = 1;
break;
}
}
if (node2_flag == 0)
{
(*node_set).push_back(node2);
count++;
}
}
return count;
}

spanning tree Kruskal C++

example input :
====================================                  
a-b 2
b-c 4
c-f 5
e-f 5
d-e 2
d-a 4
d-b 4
b-e 3
b-f 1
exit
===================================
#include <iostream>
#include<string>
#include<vector>
using namespace std;
struct link{
string node1;
string node2;
int weighted;
};
void split(string,vector<link>*);
void sort(vector<link>*);
int count_node(vector<link>*, vector<string>*);
int main()
{
vector<link>input;                      //原始input
vector<string>n_list; //node的list
vector<link>answer;                     //最後要輸出的結果
string command;                         //每一行輸入
int size,edge_count=0,node_count;
while (true)
{
getline(cin, command);
if (command == "exit")
break;
split(command, &input);
}
sort(&input);                            //根據權重由小到大排

node_count = count_node(&input,&n_list);                    //算有幾個點 & 做出點的list
int *Visited = new int[node_count]; //建立node set概念用
for (int i = 0; i < node_count; i++)
Visited[i] = 0;
link tmp;
int node1_pos,node2_pos,total_weighted=0;
int min,bigger;
for (int i = 0;edge_count != node_count-1 ; i++) //找出答案
{
tmp = input[i];
for (int j = 0; j < node_count; j++)
{
if (tmp.node1 == n_list[j])
{
node1_pos = j;
break;
}
}
for (int j = 0; j < node_count; j++)
{
if (tmp.node2 == n_list[j])
{
node2_pos = j;
break;
}
}
if ((Visited[node1_pos] == 0) && (Visited[node2_pos] == 0))
{
Visited[node1_pos] = i+1;
Visited[node2_pos] = i+1;
answer.push_back(tmp);
edge_count++;
total_weighted = total_weighted + tmp.weighted;
}
else if (Visited[node1_pos] == 0 || Visited[node2_pos]==0)
{
if (Visited[node1_pos] == 0)
Visited[node1_pos] = Visited[node2_pos];
else
Visited[node2_pos] = Visited[node1_pos];
answer.push_back(tmp);
edge_count++;
total_weighted = total_weighted + tmp.weighted;
}
else if (Visited[node1_pos] != 0 && Visited[node2_pos] != 0 && Visited[node1_pos] != Visited[node2_pos])
{
if (Visited[node1_pos] > Visited[node2_pos])
{
min = Visited[node2_pos];
bigger = Visited[node1_pos];
}
else
{
min = Visited[node1_pos];
bigger = Visited[node2_pos];
}
for (int k = 0; k < node_count; k++)
{
if (Visited[k] == bigger)
Visited[k] = min;
}
answer.push_back(tmp);
edge_count++;
total_weighted = total_weighted + tmp.weighted;
}
else
;
}
size = answer.size(); //印答案
for (int i = 0; i < size; i++)
cout << answer[i].node1 << "-" << answer[i].node2 << "  " << answer[i].weighted << endl;
cout << "total weighted = " << total_weighted << endl;
return 0;
}
void split(string input, vector<link>* data)
{
int dash_pos, space_pos;
int str_len = input.length();
link push_back;
string tmp = "";
for (int i = 0; i < str_len; i++) //找 - 位置
{
if (input[i]=='-')
{
dash_pos = i;
break;
}
}
for (int i = dash_pos + 1; i < str_len; i++)//找 空白 位置
{
if (input[i] == ' ')
{
space_pos = i;
break;
}
}
for (int j = 0; j < dash_pos; j++)
tmp = tmp + input[j];
push_back.node1 = tmp;
tmp = "";
for (int j = dash_pos + 1; j < space_pos; j++)
tmp = tmp + input[j];
push_back.node2 = tmp;
tmp = "";
for (int j = space_pos + 1; j < str_len; j++)
tmp = tmp + input[j];
push_back.weighted = atoi(tmp.c_str());
data->push_back(push_back);
}
void sort(vector<link>* data)
{
int size = data->size();
link tmp;
for (int i = 0; i < size; i++)
{
for (int j = 0; j < size - 1; j++)
{
if ((*data)[j].weighted >(*data)[j+1].weighted)
{
tmp = (*data)[j];
(*data)[j] = (*data)[j + 1];
(*data)[j + 1] = tmp;
}
}
}
}
int count_node(vector<link>* data, vector<string>* node_set) //算點數 同時做出點的list
{
int count = 0;
int size = data->size();
int len;
for (int i = 0; i < size; i++)
{
link tmp = (*data)[i];
string node1 = tmp.node1;
string node2 = tmp.node2;
bool node1_flag = 0, node2_flag = 0;
len = node_set->size();
for (int j = 0; j < len; j++)
{
if (node1 == (*node_set)[j])
{
node1_flag = 1;
break;
}
}
if (node1_flag == 0)
{
(*node_set).push_back(node1);
count++;
}
len = (*node_set).size();
for (int k = 0; k < len; k++)
{
if (node2 == (*node_set)[k])
{
node2_flag = 1;
break;
}
}
if (node2_flag == 0)
{
(*node_set).push_back(node2);
count++;
}
}
return count;
}

UVA 12468 C++

#include <iostream>
using namespace std;
int main()
{
int a, b;
while (cin >> a, cin >> b)
{
if (a == -1 && b == -1)
break;
if (a > b)
{
if ((a - b) > 50)
cout << b + 100 - a << endl;
else
cout << a - b << endl;
}
else
{

if ((b - a) > 50)
cout << a + 100 - b << endl;
else
cout << b - a << endl;
}
}
return 0;
}

UVA 12149 C++

#include <iostream>
#include <iomanip>
using namespace std;
int main()
{
long long n, ans;
while (cin >> n)
{
if (n<1 || n>100)
break;
ans = 0;
for (int i = 1; i <= n; i++)
ans = i*i + ans;
cout << ans << endl;
}
}

簡單的數學問題!?

UVA 11984 C++

#include <iostream>
#include <iomanip>
using namespace std;
int main()
{
long long t ;
double c, d, f;
while (cin >> t)
{
for (int i = 0; i <= t - 1; i++)
{
cin >> c;
cin >> d;
c = (c * 9 / 5 )+ 32;
f = c+d;
f = 1.0*(f - 32) * 5 / 9;
cout <<"Case "<<i+1<<": "<<fixed<<setprecision(2)<< f << endl;
}
}
}

很無聊的一題，不過setprecision倒是滿實用的

UVA 10106 C++

#include <iostream>
#include<string>
using namespace std;
string inverse(string);
void inverse_int(int *, int);
int main()
{
string x="", y="",tmp="";
int ch_to_int_x, ch_to_int_y,tmp_int;
int len_x, len_y,tmp_len;
bool flag = 0;
while (cin >> x>>y)
{
int arr[1000] = { 0 };
flag = 0;
len_x = x.length();
len_y = y.length();
if (len_y > len_x) //x比較長   y比較短
{
tmp = x;
tmp_len = len_x;
x = y;
len_x = len_y;
y = tmp;
len_y = tmp_len;
}
x = inverse(x);
y = inverse(y);
for (int i = 0; i <= len_y - 1; i++) //乘法
{
for (int j = 0; j <= len_x - 1; j++)
{
ch_to_int_y = y[i] - 48;
ch_to_int_x = x[j] - 48;
tmp_int = ch_to_int_y*ch_to_int_x;
arr[i + j] = arr[i+j]+tmp_int;
}
}
for (int k = 0; k <= len_x+len_y; k++) //進位
{
tmp_int = arr[k] / 10;
arr[k] = arr[k] % 10;
arr[k + 1] = arr[k + 1] + tmp_int;
}
for (int l = len_x + len_y;; l--) //範圍
{
if (arr[l] != 0)
{
tmp_int = l;
break;
}
}
inverse_int(arr, tmp_int);
for (int m = 0; m <= tmp_int; m++)
{
flag = 1;
cout << arr[m];
}
if (!flag)
cout << "0";
cout << endl;
}
return 0;
}
string inverse(string in)
{
string output=in;
char ch;
int max = in.length() - 1;
int len = in.length() / 2;
for (int i = 0; i < len; i++)
{
ch = in[max];
output[max] = output[i];
output[i] = ch;
max--;
}
return output;
}
void inverse_int(int *input,int flag)
{
int tmp;
int size = flag;
for (int i = 0; i < (flag+1) / 2; i++)
{
tmp = input[size];
input[size] = input[i];
input[i] = tmp;
size--;
}
}