巢穴

P1258

同剛才的題.....
剛才的代碼連改都不怎么用改..
裸prim..

#include <iostream>
using namespace std;

const int MAXN=101;
const int INF=0x7fffffff;
int n;
int edge[MAXN][MAXN];
bool hash[MAXN];
int dist[MAXN];
void prim()
{
     memset(hash,0,sizeof(hash));
     for (int i=0;i<n;i++)
         dist[i]=INF;
     dist[0]=0;
     int ans=0;
     for (int i=0;i<n;i++)
     {
         
         int u=-1;
         int min=INF;
         for (int j=0;j<n;j++)
         {
             if (hash[j]) continue;
             if (min>dist[j]) {min=dist[j];u=j;}
         }
         ans+=dist[u];
       //  cout<<dist[u]<<endl;
         hash[u]=true;
         for (int j=0;j<n;j++)
         {
             if (dist[j]>edge[u][j]) dist[j]=edge[u][j];
         }
     }
     cout<<ans<<endl;
    // system("pause");
}

int main()
{
    while(cin>>n)
    {
     for (int i=0;i<n;i++)
      for (int j=0;j<n;j++)
          cin>>edge[i][j];
     prim();
    }
    
    return 0;
}

posted @ 2009-10-06 16:44 Vincent 閱讀(93) | 評論 (0) | 編輯 收藏

P2485

poj恢復的好快..
prim..然后求出最長的邊..

#include <iostream>
using namespace std;

const int MAXN=501;
int t;
int n;
int edge[MAXN][MAXN];
int dist[MAXN];
bool hash[MAXN];
const int INF=65537;
void prim()
{
     memset(hash,0,sizeof(hash));
     for (int i=0;i<n;i++)
         dist[i]=INF;
     dist[0]=0;
     int max=-1;
     for (int i=0;i<n;i++)
     {
         
         int u=-1;
         int min=INF;
         for (int j=0;j<n;j++)
         {
             if (hash[j]) continue;
             if (min>dist[j]) {min=dist[j];u=j;}
         }
         if (max<dist[u]) max=dist[u];
       //  cout<<dist[u]<<endl;
         hash[u]=true;
         for (int j=0;j<n;j++)
         {
             if (dist[j]>edge[u][j]) dist[j]=edge[u][j];
         }
     }
     cout<<max<<endl;
    // system("pause");
}
int main()
{
 cin>>t;
 while(t--)
 {
  cin>>n;
  for (int i=0;i<n;i++)
   for (int j=0;j<n;j++)
   {
    cin>>edge[i][j];
   }
  prim();
 }
 return 0;
}

posted @ 2009-10-06 16:32 Vincent 閱讀(64) | 評論 (0) | 編輯 收藏

囧

posted @ 2009-10-06 16:21 Vincent 閱讀(139) | 評論 (0) | 編輯 收藏

P1789

裸的樸素的prim...
wa了若干次..
1.判重數字忘記重置了..
2.relax寫成dijkstra了....orz..奇妙的是樣例還是過了..
還是要注意靜態調試...
另外這道題太ooxx..數據量極大..用stl貌似會tle...
就這就夠x的了..

Accepted

15708K

1594MS

#include <iostream>
#include <vector>
#include <string>
using namespace std;

const int MAXN=2001;
string s_vec[MAXN];
int edge[MAXN][MAXN];
int n;
int dist[MAXN];
bool hash[MAXN];
int answer=0;
#define INF 0x7fffffff
void prim()
{
     answer=0;
     memset(dist,0x7f,sizeof(dist));
     memset(hash,0,sizeof(hash));
     for (int i=0;i<n;i++)
         dist[i]=INF;
     
     dist[0]=0;
     for (int i=0;i<n;i++)
     {
         int min=INF;
         int u=-1;
         for (int j=0;j<n;j++)
         {
             if (hash[j]) continue;
             if (min>dist[j]) {min=dist[j];u=j;}
         }
         hash[u]=true;
         answer+=dist[u];
         for (int j=0;j<n;j++)
         {
             if (dist[j]>edge[u][j])
             {
              dist[j]=edge[u][j];
             }
         }
     }
     cout<<"The highest possible quality is 1/"<<answer<<"."<<endl;
     //system("pause");
     
}
int main()
{
    while(1)
    {
 //           s_vec.clear();
            cin>>n;
            if (0==n) break;
            for (int i=0;i<n;i++)
            {
             string str;
             cin>>s_vec[i];
            }
            for (int i=0;i<n;i++)
            {
                string str1=s_vec[i];
                for (int j=0;j<n;j++)
                {
                    if (i==j) {edge[i][j]=0;continue;}
                    string str2=s_vec[j];
                    int count=0;
                    for (int k=0;k<7;k++)
                     if (str1[k]!=str2[k]) count++;
                    edge[i][j]=count;
                }
            }
            prim();
            
    }
    return 0;
}

posted @ 2009-10-06 12:05 Vincent 閱讀(189) | 評論 (0) | 編輯 收藏

P2240

#include <iostream>
#include <string>
#include <map>
#include <fstream>
#include <math.h>
using namespace std;
ifstream fin("t2240.in");
map<string,int> hash;

#define eps 1e-8
const int MAXN=31;
int n,m;
double edge[MAXN][MAXN];
//string name[MAXN];
int main()
{
    int num=0;
    while(1)
    {
      cin>>n;
      if (0==n) break;
      for (int i=1;i<=n;i++)
      {
          string str;
          cin>>str;
          hash.insert(make_pair<string,int>(str,i));
          //name[i]=str;
      }
      cin>>m;
      memset(edge,1,sizeof(edge));
      for (int i=1;i<=m;i++)
      {
          string name1,name2;
          double r;
          cin>>name1>>r>>name2;
          edge[hash[name1]][hash[name2]]=r; 
      }
      for (int k=1;k<=n;k++)
       for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
        {
            double temp=edge[i][k]*edge[k][j];
            if (edge[i][j]+eps<temp)
            {
              edge[i][j]=temp;
            }
        }
      bool ok=true;
      for (int i=1;i<=n;i++)
       if (edge[i][i]+eps<1||fabs(edge[i][i]-1)<eps)
       {
         ok=false;break;
       } 
     if (ok)
     {
      cout<<"Case "<<++num<<": Yes"<<endl;
     }
     else
      cout<<"Case "<<++num<<": No"<<endl;
      
     //system("pause"); 
    }
    
    return 0;
}

posted @ 2009-10-05 12:17 Vincent 閱讀(129) | 評論 (0) | 編輯 收藏

P1125

#include <iostream>
using namespace std;

const int MAXN=101;
int dist[MAXN][MAXN];
int max_[MAXN];
int main()
{
    int n,m;
    while(1)
    {
            cin>>n;
            if (0==n) break;
            for (int i=1;i<=n;i++)
                for (int j=1;j<=n;j++)
                    dist[i][j]=0xffff;
            memset(max_,0,sizeof(max_));
            for (int i=1;i<=n;i++)
                dist[i][i]=0;
            for (int i=1;i<=n;i++)
            {
                cin>>m;
                for (int j=1;j<=m;j++)
                {
                    int to,temp;
                    cin>>to>>temp;
                    dist[i][to]=temp;
                }
            }
            for (int i=1;i<=n;i++)
             for (int j=1;j<=n;j++)
              for (int k=1;k<=n;k++)
              {
                  int dist_=dist[j][i]+dist[i][k];
                  if (dist[j][k]>dist_) dist[j][k]=dist_;
              }
           for (int i=1;i<=n;i++)
           {
            for (int j=1;j<=n;j++)
            {
                if (j==i) continue;
                if (max_[i]<dist[i][j]) max_[i]=dist[i][j];
            }
           }
          int min=0x7fffffff;
          int k=0;
          for (int i=1;i<=n;i++)
          {
              if (min>max_[i]) {min=max_[i];k=i;}
          }
          cout<<k<<" "<<min<<endl;
         // system("pause");
    }
    return 0;
}

posted @ 2009-10-05 11:28 Vincent 閱讀(97) | 評論 (0) | 編輯 收藏

P2253

#include <iostream>
#include <math.h>
using namespace std;

struct node
{
 int x,y;
};
const int MAXN=201;
node point[MAXN];
double dist[MAXN];
double answer[MAXN];
bool hash[MAXN];
int n;
inline double distances(int u,int v)
{
 double value=(point[u].x-point[v].x)*(point[u].x-point[v].x)+(point[u].y-point[v].y)*(point[u].y-point[v].y);
 return sqrt(value);
     
}
double max(double x,double y)
{
       return x>y?x:y;
}
int main()
{
    int num=0;
    while(1)
    {
      cin>>n;
      if (0==n) break;
      for (int i=1;i<=n;i++)
      {
          cin>>point[i].x>>point[i].y;
      }
      memset(dist,0x7f,sizeof(dist));
      memset(answer,0x7f,sizeof(dist));
      memset(hash,0,sizeof(hash));
      dist[1]=0.0f;
      answer[1]=0.0f;
      for (int i=1;i<=n;i++)
          dist[i]=distances(1,i);
      
      for (int i=1;i<n;i++)
      {
       int u=0;
       double min=0x7fffffff;
       for (int j=1;j<=n;j++)
       {
           if (hash[j]) continue;
           if (min>dist[j]) {min=dist[j];u=j;}
       }
       hash[u]=true;
       if (0==u) break;
       for (int j=1;j<=n;j++)
       {
           {
              if (dist[j]>max(dist[u],distances(u,j))) dist[j]=max(dist[u],distances(u,j));
           }
       }
      }
      printf("%s%d\n","Scenario #",++num);
      printf("%s%.3f\n\n","Frog Distance = ",dist[2]);
    }
    return 0;
    
}

posted @ 2009-10-05 10:33 Vincent 閱讀(105) | 評論 (0) | 編輯 收藏

P1062

WA了多次.因為構圖時少打了個=號....
枚舉最高rank,多次構圖,然后就最短路 O(N^3)

#include <iostream>
//#include <fstream>
#include <math.h>
using namespace std;

//ifstream fin("t1062.in");


const int MAXN=101;
#define INF 2147483647
int p[MAXN],l[MAXN],x;
int u[MAXN][MAXN];
int q[MAXN];
int m,n;

void dijkstra()
{
     int dist[MAXN];
     bool hash[MAXN];
     int answer=INF;
     for (int i=n;i>=1;--i)
     {
      int maxRank=l[i];
      for (int j=1;j<=n;++j)
          if (l[j]>maxRank||maxRank-l[j]>m) q[j]=1;
          else q[j]=0;
      memset(hash,0,sizeof(hash));
      for (int j=1;j<=n;++j)
          dist[j]=p[j];
      for (int j=1;j<=n;++j)
      {
       int u1=0;
       int min=INF;
       for (int k=1;k<=n;++k)
       {
        if (q[k]) continue;
        if (hash[k]) continue;
        if (min>dist[k])    {min=dist[k];u1=k;}
        
       }
       hash[u1]=true;
       if (u1==0) break;
       if (dist[u1]==0x7f) break;
       for (int k=1;k<=n;++k)
       { 
           if (q[k]) continue;
           if (u[u1][k]==0x7f) continue; 
           if (dist[k]>dist[u1]+u[u1][k])
           {
            dist[k]=dist[u1]+u[u1][k];
           }
       }
      }
      if (answer>dist[1]) answer=dist[1];
     }
     cout<<answer<<endl;

}
int main()
{
    memset(u,0x7f,sizeof(u));
    cin>>m>>n;
    for (int i=1;i<=n;i++)
    {
        cin>>p[i]>>l[i]>>x;
        for (int j=1;j<=x;j++)
        {
            int t,v;
            cin>>t>>v;
            u[t][i]=v;
        }
    }
    dijkstra();
    return 0;
}

posted @ 2009-10-05 09:23 Vincent 閱讀(98) | 評論 (0) | 編輯 收藏

P3259

#include <iostream>
#include <vector>
//#include <fstream>
using namespace std;

//ifstream fin("t3259.in");


struct node
{
 int u,v,w;
};
vector<node> edge_vec;
int f;
int n,m,w;
bool bellman()
{
     int dist[10000];
     memset(dist,0x7f,sizeof(dist));
     
     dist[edge_vec.at(0).u]=0;
     int flag;
     for (int i=1;i<=n;i++)
     {
      flag=0;
      for (int j=0;j<edge_vec.size();j++)
      {
          node edge=edge_vec.at(j);
          if (dist[edge.v]>dist[edge.u]+edge.w)
             {dist[edge.v]=dist[edge.u]+edge.w;flag=1;}
      }
      if (!flag) return false;
     }
     for (int i=0;i<edge_vec.size();i++)
     {
         node edge=edge_vec.at(i);
         if (dist[edge.v]<dist[edge.u]+edge.w)
            return true;
     }
     return false;     
}
int main()
{
    cin>>f;
    while (f--)
    {
     cin>>n>>m>>w;
     edge_vec.clear();
     for (int i=1;i<=m;i++)
     {
      int u_,v_,w_;
      cin>>u_>>v_>>w_;
      node edge;
      edge.u=u_;
      edge.v=v_;
      edge.w=w_;
      edge_vec.push_back(edge);
      edge.u=v_;
      edge.v=u_;
      edge.w=w_;
      edge_vec.push_back(edge);     
     }
     for (int i=1;i<=w;i++)
     {
      int u_,v_,w_;
      cin>>u_>>v_>>w_;
      node edge;
      edge.u=u_;
      edge.v=v_;
      edge.w=-w_;
      edge_vec.push_back(edge);      
     }
     if  (bellman()) cout<<"YES"<<endl;
     else
         cout<<"NO"<<endl;
    }
}

posted @ 2009-10-04 18:45 Vincent 閱讀(119) | 評論 (0) | 編輯 收藏

P1860

#include <iostream>
#include <vector>
#include <fstream>
using namespace std;

//ifstream fin("t1860.in");
struct node
{
 int u,v;
 double r,c;
};
vector<node> edge_vec;
int n,m,s;
int f;
#define eps 1e-8
double v;
double dist[200];
void relax(int x,int y,double r,double c)
{
     if (dist[y]+eps<(dist[x]-c)*r)
        {f=1;dist[y]=(dist[x]-c)*r;}
}
bool bellman()
{
     for (int i=1;i<=n;i++)
        dist[i]=0;
     dist[s]=v;
    
    while(dist[s]<=v+eps)
    {
     f=0;
     for (int j=0;j<edge_vec.size();j++)
     {
         node edge=edge_vec.at(j);
         relax(edge.u,edge.v,edge.r,edge.c);    
     }
     if (!f) break;
    }
   if (dist[s]>v+eps) return true;
         else return false;
    
}
int main()
{
    cin>>n>>m>>s>>v;
    for (int i=1;i<=m;i++)
    {
        int x,y;
        double rxy,cxy,ryx,cyx;
        cin>>x>>y>>rxy>>cxy>>ryx>>cyx;
        node edge;
        edge.u=x;
        edge.v=y;
        edge.r=rxy;
        edge.c=cxy;
        edge_vec.push_back(edge);
        edge.u=y;
        edge.v=x;
        edge.r=ryx;
        edge.c=cyx;
        edge_vec.push_back(edge);
        
    }
        
    if (bellman()) cout<<"YES"<<endl;
       else
           cout<<"NO"<<endl;
  // system("pause");
    return 0;
}

posted @ 2009-10-04 17:23 Vincent 閱讀(119) | 評論 (0) | 編輯 收藏