青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

巢穴

about:blank

#

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 閱讀(101) | 評(píng)論 (0) | 編輯 收藏

P2485

poj恢復(fù)的好快..
prim..然后求出最長(zhǎng)的邊..

#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 閱讀(73) | 評(píng)論 (0) | 編輯 收藏

囧

poj掛了

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

P1789

裸的樸素的prim...
wa了若干次..
1.判重?cái)?shù)字忘記重置了..
2.relax寫(xiě)成dijkstra了....orz..奇妙的是樣例還是過(guò)了..
還是要注意靜態(tài)調(diào)試...
另外這道題太ooxx..數(shù)據(jù)量極大..用stl貌似會(huì)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 閱讀(199) | 評(píng)論 (0) | 編輯 收藏

P2240

   還是floyd...
   orz..最短路切完了.
  
#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 閱讀(140) | 評(píng)論 (0) | 編輯 收藏

P1125

FLOYD
一定要注意,floyd的本質(zhì)是動(dòng)態(tài)規(guī)劃

#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 閱讀(106) | 評(píng)論 (0) | 編輯 收藏

P2253

   dijkstra變種
   wa了3次..
   pe一次
   另外orz一下樣例...太完美了..對(duì)我做題沒(méi)任何幫助
  
#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 閱讀(116) | 評(píng)論 (0) | 編輯 收藏

P1062

WA了多次.因?yàn)闃?gòu)圖時(shí)少打了個(gè)=號(hào)....
枚舉最高rank,多次構(gòu)圖,然后就最短路 O(N^3)

以后要注意靜態(tài)調(diào)試
#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 閱讀(112) | 評(píng)論 (0) | 編輯 收藏

P3259

   還是bellman-ford
#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 閱讀(131) | 評(píng)論 (0) | 編輯 收藏

P1860

Bellman-Ford
看題看了半天..
#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 閱讀(126) | 評(píng)論 (0) | 編輯 收藏

僅列出標(biāo)題
共8頁(yè): 1 2 3 4 5 6 7 8 
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

    • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>

    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>

            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            
嫩草国产精品入口|
欧美肥婆bbw|
…久久精品99久久香蕉国产|
欧美日韩综合网|
欧美日韩中文在线|
国产精品乱人伦中文|
国产精品99免费看
|
国产精品视频|
国产视频自拍一区|
在线欧美不卡|
在线亚洲一区观看|
欧美一区二区三区啪啪|
久久一区二区三区四区|
欧美成人有码|
在线亚洲免费|
久久最新视频|
欧美视频一区二区三区…|
国产精品亚洲一区|
亚洲二区在线观看|
一本大道久久精品懂色aⅴ|
亚洲男人av电影|
欧美成人激情视频免费观看|
亚洲精品色婷婷福利天堂|
欧美在线观看www|
欧美激情一二区|
国产主播一区二区三区四区|
日韩天堂av|
理论片一区二区在线|
亚洲人成高清|
亚洲小视频在线|
免费欧美日韩|
国产偷国产偷亚洲高清97cao|
最新热久久免费视频|
久久精彩免费视频|
99国产精品99久久久久久|
久久精品一区四区|
国产精品久久久久av|
亚洲精品一区在线观看香蕉|
久久亚洲私人国产精品va|
亚洲视屏在线播放|
欧美精品日韩综合在线|
欧美人在线观看|
91久久午夜|
久久精品一区二区三区不卡|
亚洲精品视频在线观看网站|
久久全国免费视频|
国产日韩久久|
亚洲欧美高清|
一区二区欧美在线观看|
欧美国产成人在线|
亚洲国产一区二区三区青草影视|
久久精品国产亚洲精品|
午夜精品久久久久|
国产精品视频区|
亚洲欧美一区二区三区极速播放|
亚洲欧洲美洲综合色网|
美女主播视频一区|
最新亚洲一区|
亚洲国产一区在线|
欧美高清视频一区二区三区在线观看
|
亚洲国产高清自拍|
久久免费视频在线观看|
亚洲欧美自拍偷拍|
国产小视频国产精品|
久久精品国产99精品国产亚洲性色|
亚洲视频福利|
国产伦精品一区二区三区视频孕妇|
亚洲影院色在线观看免费|
中文av一区特黄|
国产老女人精品毛片久久|
性一交一乱一区二区洋洋av|
亚洲免费一区二区|
国内精品福利|
欧美承认网站|
欧美激情1区2区3区|
一区二区三区视频在线|
一区二区高清在线观看|
国产精品欧美日韩一区|
久久久久国产免费免费|
久久免费高清视频|
亚洲欧洲在线免费|
av成人手机在线|
国产午夜精品久久久|
麻豆久久婷婷|
欧美伦理91|
久久九九电影|
欧美福利视频|
香蕉久久a毛片|
久久久久久久成人|
日韩亚洲不卡在线|
午夜精品久久久久久久蜜桃app|
国产一区二区欧美|
亚洲黄色av|
国产欧美一级|
亚洲激情一区二区三区|
国产日韩精品视频一区二区三区|
欧美xart系列高清|
国产精品男女猛烈高潮激情|
欧美成人在线网站|
国产欧美日韩一区|
欧美日韩1080p|
亚洲欧洲精品一区二区三区|
亚洲国产视频直播|
国产精品永久|
亚洲国产精品免费|
国产一区二区三区直播精品电影|
亚洲国产第一|
国产一级一区二区|
一区二区免费在线播放|
亚洲国产成人av|
午夜精品福利电影|
亚洲一区二区在线免费观看视频|
欧美一区二区日韩|
中文精品视频一区二区在线观看|
久久国产欧美日韩精品|
亚洲欧美一级二级三级|
欧美精品黄色|
欧美成人精品激情在线观看|
国产精品午夜在线|
一区二区三区国产|
一本久久精品一区二区|
久久午夜电影|
久久欧美肥婆一二区|
国产精品午夜在线|
亚洲午夜国产一区99re久久
|
久久精品人人|
久久久久国产精品www
|
国内精品视频一区|
午夜激情综合网|
午夜视频久久久久久|
欧美色精品天天在线观看视频|
亚洲国产精品专区久久|
91久久国产综合久久蜜月精品
|
欧美成人视屏|
免费一区二区三区|
在线观看久久av|
久久经典综合|
老司机成人在线视频|
国产午夜精品麻豆|
欧美一区二区三区在线|
久久精品视频va|
一区二区视频欧美|
久久婷婷蜜乳一本欲蜜臀|
蘑菇福利视频一区播放|
在线观看欧美|
欧美高清在线|
一本色道久久综合精品竹菊|
亚洲午夜91|
国产亚洲精久久久久久|
久久国产精品99久久久久久老狼|
性一交一乱一区二区洋洋av|
国产偷自视频区视频一区二区|
欧美专区亚洲专区|
欧美成人午夜|
亚洲视频在线一区|
国产欧美精品va在线观看|
午夜在线精品偷拍|
美国成人直播|
日韩午夜电影av|
国产精品日本精品|
久久久蜜桃精品
|
噜噜噜在线观看免费视频日韩
|
欧美韩国日本一区|
亚洲精品在线二区|
午夜欧美精品久久久久久久|
国产一区二区三区的电影|
久久久爽爽爽美女图片|
亚洲国产三级在线|
午夜免费在线观看精品视频|
激情丁香综合|
欧美午夜寂寞影院|
久久久精品国产一区二区三区|
亚洲国产精品一区二区第四页av|
亚洲欧美国产精品专区久久|
亚洲国产精品久久久久婷婷884|
欧美视频一区二区三区在线观看|
欧美伊人久久大香线蕉综合69|
亚洲国产美女精品久久久久∴|
欧美在线播放视频|
夜夜爽www精品|
狠狠噜噜久久|
国产精品老女人精品视频|
久久亚洲精品一区二区|
亚洲午夜精品网|
亚洲国产精品成人精品|
久久成人免费网|
亚洲美女中文字幕|
国内精品久久久久久久影视麻豆|
欧美日韩www|
久久亚洲精品视频|
亚洲午夜在线|
亚洲乱码久久|
欧美大片在线观看一区二区|
久久国产婷婷国产香蕉|
亚洲午夜在线视频|
日韩视频在线观看|
亚洲全部视频|
伊人精品成人久久综合软件|
国产精品视频一二|
欧美性猛片xxxx免费看久爱|