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

巢穴

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) | 評論 (0) | 編輯 收藏

P2485

poj恢復(fù)的好快..
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 閱讀(74) | 評論 (0) | 編輯 收藏

囧

poj掛了

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

P1789

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

P1125

FLOYD
一定要注意,floyd的本質(zhì)是動態(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 閱讀(107) | 評論 (0) | 編輯 收藏

P2253

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

P1062

WA了多次.因為構(gòu)圖時少打了個=號....
枚舉最高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 閱讀(116) | 評論 (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 閱讀(132) | 評論 (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 閱讀(128) | 評論 (0) | 編輯 收藏

僅列出標(biāo)題
共8頁: 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>
            
亚洲午夜精品国产|
久久人人爽爽爽人久久久|
国产精品激情偷乱一区二区∴|
亚洲精品在线免费|
91久久久久久国产精品|
免费亚洲婷婷|
亚洲精品视频免费在线观看|
亚洲成色精品|
欧美福利小视频|
亚洲老板91色精品久久|
亚洲欧洲精品一区二区精品久久久|
欧美88av|
正在播放亚洲一区|
一区二区三区av|
国产精品欧美在线|
久久国产精品99精品国产|
亚洲欧美怡红院|
黄色成人免费观看|
欧美1区3d|
欧美激情在线播放|
亚洲伊人第一页|
亚洲在线一区二区三区|
国产日韩欧美一区二区三区四区
|
欧美成人精品在线播放|
亚洲开发第一视频在线播放|
日韩一级精品视频在线观看|
国产精品久久99|
久久久久国产一区二区三区四区
|
欧美日韩免费精品|
亚洲欧美日韩天堂|
欧美在线看片|
91久久国产综合久久91精品网站|
亚洲区欧美区|
国产精品乱码久久久久久|
久久精品一本|
欧美 日韩 国产 一区|
在线视频中文亚洲|
亚洲免费在线精品一区|
在线播放视频一区|
99re热这里只有精品免费视频|
欧美视频日韩|
久久本道综合色狠狠五月|
久久久久欧美精品|
aaa亚洲精品一二三区|
亚洲一区二三|
亚洲高清免费视频|
中国女人久久久|
狠狠色狠狠色综合日日tαg|
亚洲国产专区校园欧美|
国产老肥熟一区二区三区|
嫩草影视亚洲|
日韩一级精品视频在线观看|
国产精品视频|
欧美电影电视剧在线观看|
欧美亚男人的天堂|
久久一本综合频道|
欧美日韩免费观看中文|
久久久久国内|
欧美日韩精品一区二区|
久久久精品一品道一区|
欧美人妖另类|
久久尤物视频|
欧美性一二三区|
另类激情亚洲|
欧美日韩一区二区免费视频|
久久综合伊人77777麻豆|
欧美日韩免费网站|
免费影视亚洲|
国产精品久久久久久久久久久久久|
另类春色校园亚洲|
欧美日韩亚洲另类|
嫩草影视亚洲|
国产欧美一区二区三区在线看蜜臀
|
最近看过的日韩成人|
亚洲午夜精品网|
亚洲欧洲日本国产|
欧美一二三区在线观看|
99视频有精品|
久久综合狠狠|
欧美怡红院视频|
欧美日韩亚洲不卡|
亚洲成人直播|
国产日韩欧美在线一区|
亚洲精选在线观看|
亚洲电影免费观看高清完整版在线
|
你懂的国产精品|
国产亚洲a∨片在线观看|
av不卡免费看|
亚洲三级影院|
久久亚洲精品一区二区|
久久狠狠亚洲综合|
国产精品免费福利|
亚洲日本中文字幕区|
亚洲高清在线视频|
欧美淫片网站|
欧美一区二区三区喷汁尤物|
欧美日韩成人在线|
亚洲国产成人在线|
在线精品一区二区|
久久av在线|
欧美一区二区视频网站|
欧美先锋影音|
亚洲免费观看高清在线观看|
91久久国产自产拍夜夜嗨|
久久久久久久999|
久久国内精品自在自线400部|
国产精品久久久久久久久免费桃花
|
久久综合亚洲社区|
国产一区二区在线观看免费播放|
亚洲与欧洲av电影|
午夜精品久久久久99热蜜桃导演|
欧美日韩黄色大片|
亚洲人成在线播放网站岛国|
亚洲精品日韩一|
欧美成人午夜影院|
亚洲大片精品永久免费|
亚洲国产综合91精品麻豆|
久久久亚洲高清|
美女日韩在线中文字幕|
精品白丝av|
久久久久国色av免费观看性色|
久久免费少妇高潮久久精品99|
国产香蕉久久精品综合网|
性欧美激情精品|
久久久久国产精品www|
国产在线高清精品|
久久精品视频免费|
蜜桃久久精品一区二区|
有码中文亚洲精品|
免费av成人在线|
91久久亚洲|
中国成人在线视频|
国产精品免费在线|
香蕉av福利精品导航|
久久精品亚洲|
在线播放中文一区|
欧美福利视频在线|
亚洲国产成人精品久久|
一区二区久久久久久|
欧美四级伦理在线|
亚洲摸下面视频|
久久男人资源视频|
亚洲激情午夜|
欧美日韩国产精品自在自线|
宅男噜噜噜66一区二区66|
欧美一区二区三区在线|
韩国一区二区在线观看|
久久亚洲国产精品日日av夜夜|
欧美国产一区视频在线观看|
99在线精品观看|
国产精品色午夜在线观看|
欧美一级二区|
欧美国产日韩精品免费观看|
一区二区三区**美女毛片
|
亚洲精品一区二区三|
亚洲影院在线|
国产主播精品|
免费人成网站在线观看欧美高清|
最新国产成人av网站网址麻豆
|
一区二区不卡在线视频 午夜欧美不卡在
|
亚洲国产91|
欧美日韩国产三区|
亚洲一区中文字幕在线观看|
久久久999精品免费|
亚洲第一网站|
欧美日韩在线免费视频|
欧美亚洲自偷自偷|
亚洲大黄网站|
亚洲欧美久久久|
一区免费在线|
欧美日韩国内自拍|
香蕉亚洲视频|
亚洲国产日韩在线|
欧美一级专区|
亚洲国产成人不卡|
国产精品第三页|
久久手机免费观看|
日韩视频一区二区在线观看
|
欧美日一区二区三区在线观看国产免|
亚洲欧美美女|
欧美国产精品劲爆|
午夜精品www|
亚洲国产精品成人一区二区
|
久久激情综合|
99国产精品视频免费观看|
久久精品一区四区|
一区二区精品|
一区二区在线观看视频|
欧美日韩亚洲一区在线观看|
久久国产欧美日韩精品|
日韩特黄影片|
蜜桃精品一区二区三区
|
午夜亚洲福利在线老司机|
亚洲大胆在线|
久久精品卡一|
中文高清一区|
亚洲国产精品一区在线观看不卡|
国产精品久久网|
欧美成人免费在线|
欧美一区二区三区视频在线观看|