一区二区三区亚洲,麻豆乱码国产一区二区三区,国产精品久久影院

myUVA

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;
}