|
|
 #include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
struct Edge
   {
  int x, y, w; /**//*邊集，邊(x,y)，權為c*/
 }e[20001];
int rank[1001]; /**//*節點的秩*/
int p[1001]; /**//*p[x]表示x節點父節點*/
int ans=0;
int ma;
void Make(int x)
{
 p[x] = x;
rank[x] = 1;
}
int Find(int x) /**//*查找x所在集合子樹的根*/
{
if (x == p[x]) return x;
return p[x] = Find( p[x] );;
}
void Union(int x, int y, int c)
{
x = Find(x);
y = Find(y);
if ( x != y ) /**//*若x,y不屬于同一集合*/
{
if ( rank[x] > rank[y] ) /**//*將秩較小的樹連接到秩較大的樹后*/
{
p[y] = x;
 }
else
{
if(rank[x] == rank[y])
rank[y]++;
p[x] = y;
}
ans += c;
ma++;
}
}
bool cmp (const Edge & a, const Edge & b)
{
return a.w > b.w;
}
int N, M;
int main()
{
int n; /**//*邊的條數*/
int i;
//ifstream in("123.txt");
ans=0;
ma = 1;
scanf("%d %d", &N, &M);
//cin >> N >> M;
for ( i = 1; i <= N; ++i)
Make(i);
for ( i = 0; i < M; ++i)
{
scanf("%d %d %d", &e[i].x, &e[i].y, &e[i].w);
}
sort(e, e + M, cmp); /**//*按權值非降序排序*/
for ( i = 0; i < M; ++i)
{
Union(e[i].x, e[i].y, e[i].w);
}
if (ma == N)
printf("%d", ans);
else
printf("-1");
//system("pause");
return 0;
}
#include <stdio.h>
#include <assert.h>
#include <malloc.h>
void c(int n)
{
extern void _c(int n, int cur, int *a, int now);
int *a;
a = (int *) malloc(n * sizeof(int));
assert(a != NULL);
_c(n, 0, a, 1);
free(a);
}
void _c(int n, int cur, int *a, int now)
{
int i,j;
for (i=now; i<=n; i++)
{
a[cur] = i;
for (j=0; j<=cur; j++)
{
printf("%d ", a[j]);
}
printf("\n");
_c(n, cur+1, a, i+1);
}
}
int main()
{
c(3);
}
#include <stdio.h>
#include <assert.h>
#include <malloc.h>
void p(int n)
{
extern void _p(int n, int cur, int *a);
int *a;
a = (int *) malloc(n * sizeof(int));
assert(a != NULL);
_p(n, 0, a);
free(a);
}
void _p(int n, int cur, int *a)
{
int i,j;
if (cur == n)
{
for (j=0; j<cur; j++)
{
printf("%d ", a[j]);
}
printf("\n");
return;
}
for (i=1; i<=n; i++)
{
for (j=0; j<cur; j++)
{
if (a[j] == i)
{
break;
}
}
if (j>=cur)
{
a[cur] = i;
_p(n, cur+1, a);
}
}
}
int main()
{
p(3);
}
#include <iostream>
#include <vector>
#include <list>
#include <iterator>
#include <algorithm>
#include <numeric>
#include <functional>
#include <climits>
using namespace std;
int n; // n : 頂點個數
vector<vector<int> > g; // g : 圖(graph)(用鄰接矩陣(adjacent matrix)表示)
int s; // s : 源點(source)
vector<bool> known; // known : 各點是否知道最短路徑
vector<int> dist; // dist : 源點s到各點的最短路徑長
vector<int> prev; // prev : 各點最短路徑的前一頂點
void Dijkstra() // 貪心算法(Greedy Algorithm)
{
known.assign(n, false);
dist.assign(n, INT_MAX);
prev.resize(n); // 初始化known、dist、prev。
dist[s] = 0; // 初始化源點s到自身的路徑長為0。
for (;;)
{
int min = INT_MAX, v = s;
for (int i = 0; i < n; ++i)
if (!known[i] && min > dist[i])
min = dist[i], v = i; // 尋找未知的最短路徑長的頂點v，
if (min == INT_MAX) break; // 如果找不到，退出；
known[v] = true; // 如果找到，將頂點v設為已知，
for (int w = 0; w < n; ++w) // 遍歷所有v指向的頂點w，
if (!known[w] && g[v][w] < INT_MAX && dist[w] > dist[v] + g[v][w])
dist[w] = dist[v] + g[v][w], prev[w] = v; // 調整頂點w的最短路徑長dist和最短路徑的前一頂點 prev。
}
}
void Print_SP(int v)
{
if (v != s) Print_SP(prev[v]);
cout << v << " ";
}
int main()
{
n = 7;
g.assign(n, vector<int>(n, INT_MAX));
g[0][1] = 2; g[0][3] = 1;
g[1][3] = 3; g[1][4] = 10;
g[2][0] = 4; g[2][5] = 5;
g[3][2] = 2; g[3][4] = 2; g[3][5] = 8; g[3][6] = 4;
g[4][6] = 6;
g[6][5] = 1;
s = 0;
Dijkstra();
copy(dist.begin(), dist.end(), ostream_iterator<int>(cout, " ")); cout << endl;
for (int i = 0; i < n; ++i)
if(dist[i] != INT_MAX)
{
cout << s << "->" << i << ": ";
Print_SP(i);
cout << endl;
}
system("pause");
return 0;
}
/**//*============優先隊列版================*/
class great
{
public:
bool operator() (pair<int, int>& p1, pair<int, int>& p2) {
return (p1.second > p2.second);
}
};
int G[N][N];
int dijkstra(int src, int dst) {
vector<int> cost(N, INT_MAX);
vector<bool> visited(N, false);
priority_queue< pair<int, int>, vector< pair<int, int> >, great > Q;
cost[src] = 0;
Q.push( make_pair(src, 0) );
while(!Q.empty()) {
pair<int, int> top = Q.top();
Q.pop();
int v = top.first;
if (v == dst) return cost[v];
if (visited[v]) continue;
visited[v] = true;
for(int v2 = 0; v2 < N; v2++) if (G[v][v2] != 0) {
int dist = G[v][v2];
if(cost[v2] > cost[v] + dist) {
cost[v2] = cost[v] + dist;
Q.push( make_pair(v2, cost[v2]) );
}
}
}
return -1;
}
#include<fstream>
#define Maxm 501
using namespace std;
ifstream fin("APSP.in");
ofstream fout("APSP.out");
int p, q, k, m;
int Vertex, Line[Maxm];
int Path[Maxm][Maxm], Map[Maxm][Maxm], Dist[Maxm][Maxm];
void Root(int p,int q)
{
if (Path[p][q]>0)
{
Root(p, Path[p][q]);
Root(Path[p][q], q);
}
else
{
Line[k]=q;
k++;
}
}
int main()
{
memset(Path,0,sizeof(Path));
memset(Map,0,sizeof(Map));
memset(Dist,0,sizeof(Dist));
fin >> Vertex;
for(p=1;p<=Vertex;p++)
for(q=1;q<=Vertex;q++)
{
fin >> Map[p][q];
Dist[p][q]=Map[p][q];
}
for(k=1;k<=Vertex;k++)
{
for(p=1;p<=Vertex;p++)
{
if (Dist[p][k]>0)
{
for(q=1;q<=Vertex;q++)
{
if (Dist[k][q]>0)
{
if (((Dist[p][q]>Dist[p][k]+Dist[k][q])||(Dist[p][q]==0))&&(p!=q))
{
Dist[p][q]=Dist[p][k]+Dist[k][q];
Path[p][q]=k;
}
}
}
}
}
}
for(p=1;p<=Vertex;p++)
{
for(q=p+1;q<=Vertex;q++)
{
fout << "\n==========================\n";
fout << "Source:" << p << '\n' << "Target " << q << '\n';
fout << "Distance:" << Dist[p][q] << '\n';
fout << "Path:" << p;
k=2;
Root(p,q);
for(m=2;m<=k-1;m++)
fout << "-->" << Line[m];
fout << '\n';
fout << "==========================\n";
}
}
fin.close();
fout.close();
return 0;
}
/**//*
注解:無法連通的兩個點之間距離為0;
Sample Input
7
00 20 50 30 00 00 00
20 00 25 00 00 70 00
50 25 00 40 25 50 00
30 00 40 00 55 00 00
00 00 25 55 00 10 70
00 70 50 00 10 00 50
00 00 00 00 70 50 00
*/
摘要:
// PRIM(簡單版) 最小生成樹算法 (Minimum Spanning Tree) // 輸入：圖g； /... 閱讀全文
#include <iostream>
using namespace std;
#define N 100
struct TNode
{
int left, right;
int n;
};
TNode T[N*2+1];
void build(int s, int t, int step)
{
T[step].left = s;
T[step].right = t;
T[step].n = 0;
if(s == t)
return;
int mid = (s + t) / 2;
build(s, mid, step*2);
build(mid+1, t, step*2+1);
}
void insert(int s, int t, int step)
// insert [s, t] in the tree
{
if(s == T[step].left && t == T[step].right)
{
T[step].n++;
return;
}
int mid = (T[step].left + T[step].right) / 2;
if(t <= mid)
insert(s, t, step*2);
else if(s > mid)
insert(s, t, step*2+1);
else
{
insert(s,mid, step*2);
insert(mid+1, t, step*2+1);
}
}
void calculate(int s, int t, int step, int target, int& count)
// caculate target in the tree
{
count += T[step].n;
if(s == t)
return;
int mid = (s + t) / 2;
if(target <= mid)
calculate(s, mid, step*2, target, count);
else
calculate(mid+1, t, step*2+1, target, count);
}
int main()
{
build(0, 7, 1);
insert(2, 5, 1);
insert(4, 6, 1);
insert(0, 7, 1);
int count = 0;
calculate(0, 7, 1, 4, count);
cout << count << endl;
return 0;
}
|