558 - Wormholes 判斷從0這個節點出發能不能回到從前，此題就是檢查是否存在負回路，如果存在，可繞負回路很多圈回到從前。
bellman算法判斷負回路。
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<queue>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
const int MAX = 1005;
const int INF = (1<<29);
int n, m;
struct edge
{
edge(int a, int b, int c)
{
x = a;
y = b;
t = c;
}
int x, y, t;
};
int d[MAX];
bool bellman_ford(vector<edge>& vec)
{
for(int i = 0; i < n; i++)d[i] = INF;
d[1] = 0;
for(int i = 0; i < n; i++)
{
for(int ix = 0; ix < vec.size(); ix ++)
{
if(d[vec[ix].y] > d[vec[ix].x] + vec[ix].t)
d[vec[ix].y] = d[vec[ix].x] + vec[ix].t;
}
}
for(int ix = 0; ix < vec.size(); ix ++)
{
if(d[vec[ix].y] > d[vec[ix].x] + vec[ix].t)
return true;
}
return false;
}
int main()
{
int ncase = 0;
cin >> ncase;
while(ncase --)
{
cin >> n >> m;
vector<edge>vec;
for(int i = 0 , x, y, t; i < m; i++)
{
cin >> x >> y >> t;
vec.push_back(edge(x,y,t));
}
if(bellman_ford(vec))cout << "possible"<<endl;
else cout << "not possible" <<endl;
}
return 0;
}
10034 - Freckles 【樸素的最小生成樹】
最小生成樹，注意兩組輸出數據之間的空格，UVA直接WA
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<queue>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
const int MAX = 105;
const int INF = (1<<29);
int n, ncase ;
struct point
{
double x, y;
}loca[MAX];
double dis[MAX][MAX];
double caldis(const point & a, const point & b)
{
return sqrt((a.x - b.x)*(a.x - b.x) +(a.y - b.y )*(a.y - b.y));
}
double prim()
{
bool visit[MAX];
double d[MAX] , ans = 0;
memset(visit, 0, sizeof visit);
for(int i = 1; i <= n; i++)d[i] = INF;
d[1] = 0;
for(int i = 1; i <= n; i++)
{
double min = INF;
int index = -1;
for(int j = 1; j <= n; j++)
{
if(d[j] < min && !visit[j])
{
min = d[j];
index = j;
}
}
ans += min;
visit[index] = 1;
for(int j = 1; j <= n; j++)
if(!visit[j] && d[j] > dis[index][j])
d[j] = dis[index][j];
}
return ans;
}
int main()
{
cin >> ncase;
while(ncase--)
{
cin >> n;
for(int i = 1; i <= n; i++)
cin >> loca[i].x >> loca[i].y;
for(int i = 1; i <=n; i++)
for(int j = i+ 1; j <= n; j++)
{
dis[i][j] = dis[j][i]= caldis(loca[i], loca[j]);
}
cout.precision(2);
cout << fixed << prim()<<endl;
if(ncase != 0)cout << endl;
}
return 0;
}