-
Notifications
You must be signed in to change notification settings - Fork 0
/
problem107_obsoleted_again_again.C
122 lines (88 loc) · 3 KB
/
problem107_obsoleted_again_again.C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
//===========================================
// problem107.C
//
// written by lina <lina.oahz@gmail.com>
// start: Sat Apr 27 23:34:20 SGT 2013
// end:
//
// Please refer to:
// http://en.wikipedia.org/wiki/Reverse-delete_algorithm
//
// 1. Start with graph G, which contains a list of edges E.
// 2. Go through E in decreasing order of edge weights.
// 3. For each edge, check if deleting the edge will further disconnect the graph.
// 4. Perform any deletion that does not lead to additional disconnection.
//
//
//============================================
//============================================
// Inculde
//============================================
#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
//============================================
// main code area
//============================================
struct edges_t {
int edge;
int v1; // vertice 1
int v2; // vertice 2
};
bool myfunction (edges_t i, edges_t j) { return (i.edge > j.edge); }
int main(){
long sum = 0, min = 0;
// Read file and extract data into graph
vector<edges_t> graph;
ifstream myfile ("network.txt");
string line;
if( myfile.is_open() ){
int i = 0, j;
while( myfile.good() ){
getline(myfile, line);
istringstream split(line);
if( !line.empty() ){
j = 0;
for(string each; getline(split, each, ','); j++){
if(each != "-" && j<=i){
edges_t temp;
stringstream(each) >> temp.edge;
temp.v1 = i;
temp.v2 = j;
graph.push_back(temp);
sum += temp.edge;
}
};
i++;
}
}
}
sort(graph.begin(), graph.end(), myfunction);
unsigned int i=0;
// cout << graph[466].edge << endl;
while( i< graph.size() ){
int countv1 = 0, countv2 = 0;
for(unsigned int m=i+1; m<graph.size(); m++){
if(graph[i].v1 == graph[m].v1 || graph[i].v1 == graph[m].v2)
countv1++;
if(graph[i].v2 == graph[m].v1 || graph[i].v2 == graph[m].v2)
countv2++;
}
if( (countv1>=1 && countv2>=2) || (countv1>=2 && countv2>=1) ){
graph.erase(graph.begin()+i);
}else{
i++;
}
}
for(vector<edges_t>::iterator it=graph.begin(); it !=graph.end(); it++){
cout << it->edge << " " << it->v1 << " " << it->v2 << endl;
min += it->edge;
}
int temp = sum - 259679;
cout << sum << " " << sum - min << " remain " << min << " , other remove " << temp << ", need remove extra " << temp-min << endl;
return 0;
}