ACMboy

  C++博客 :: 首页 :: 联系 :: 聚合  :: 管理
  4 Posts :: 0 Stories :: 0 Comments :: 0 Trackbacks

常用链接

留言簿

我参与的团队

搜索

  •  

最新评论

阅读排行榜

评论排行榜

2010年4月12日 #

城市规划

时间限制(普通/Java):1000MS/3000MS          运行内存限制:65536KByte
总提交:153            测试通过:46

描述

NanJing准备开发一片荒地,目前已经规划好了一些居民点,还要建设道路。由于经费问题,现在想在保持任意两点间的距离最短的前提下,用尽可能少的经费把这些点连接起来。需要注意的是并不是任意两个居民点间都能直接相连。现在给出两两居民点间的花费,当然了,花费和路径长度成正比~

 

输入

第一行是个N<=100,表示N个居民点。

下面是个N*N的矩阵,第i行第j列,表示ij的花费,可能有负数,表示两地不相连。保证有解。

 

输出

输出一行为总花费。

 

样例输入

3
0 2 1
2 0 3
1 3 0

样例输出

3

QQ:765391213

  #include <stdio.h>
#include 
<string.h>
const int MAXN=100;
const int MAXINT=10001;
int n,dis[MAXN][MAXN],flag[MAXN][MAXN];
int main()
{
    scanf(
"%d",&n);
    
int k,i,j,temp;
    
for(i=0;i<n;i++)
        
for(j=0;j<n;j++)
        
{
            scanf(
"%d",&dis[i][j]);
            
if(dis[i][j]<0)
                dis[i][j]
=MAXINT;
        }

        
for(i=0;i<n;i++)
            
for(j=0;j<n;j++)
                flag[i][j]
=1;
            
for(k=0;k<n;k++)
                
for(i=0;i<n;i++)
                
{
                    
if(i==k) continue;
                    
for(j=0;j<n;j++)
                    
{
                        
if(k==j)continue;
                        temp
=dis[k][j]+dis[i][k];
                        
if(temp<=dis[i][j]){
                            flag[i][j]
=0;
                            dis[i][j]
=temp;
                        }

                    }

                }

                
int ans=0;
                
for(i=0;i<n;i++)for(j=i+1;j<n;j++)
                    
if(flag[i][j]) ans+=dis[i][j];
                    printf(
"%d\n",ans);
                    
return 0;
}
posted @ 2010-04-12 12:19 EG-HUA 阅读(193) | 评论 (0)编辑 收藏

2010年4月9日 #

                                                               越大越聪明吗?
                 这是一道动态规划题目,这里只提供个人代码:

#include <iostream>
struct elephone
{
    
int weight,iq,num;
}
;
int k,s[1001],max=0,vis[1001],S[1001],dp[1001][1001];
elephone a[
1000];

void dpf(int i,int j)
{
    
int &ans=dp[i][j];
    
if(ans!=-1return;
    ans
=1;
    s[j]
=a[i].num+1;
    
if(j>max) {for(int q=1;q<=j;q++) S[q]=s[q];max=j;}
    
for(int p=0;p<k;p++)
    
{
        
if(!vis[p]&&a[p].weight>a[i].weight&&a[p].iq<a[i].iq)
        
{
            vis[p]
=1;
            dpf(p,j
+1);
            vis[p]
=0;
        }

    }

}

int main()
{
    
int i=0;
    memset(dp,
-1,sizeof(dp));
    memset(vis,
0,sizeof(vis));
    
while(scanf("%d%d",&a[i].weight,&a[i].iq)==2)
    
{
        a[i].num
=i;
        
++i;
    }

    k
=i;
    
for(int q=0;q<k;q++)
    
{
    vis[q]
=1;
    dpf(q,
1);
    vis[q]
=0;
    }

    printf(
"%d\n",max);
    
for(int r=1;r<=max;r++)
        printf(
"%d\n",S[r]);
    
return 0;
}





         
posted @ 2010-04-09 13:58 EG-HUA 阅读(76) | 评论 (0)编辑 收藏

    一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市(假设出发时油箱时空的)。给定两个城市之间的距离D1、汽车油箱的容量C(以升为单位)、每升汽油能行驶的距离D2、出发点每升汽油价格P和沿途加油站数N(N可以为零),油站i离出发点的距离Di、每升汽油价格Pi(i=1,2,……,N)。

计算结果四舍五入至小数点后两位。

如果无法到达目的地,则输出“No Solution”。

样例:

Input

D1=275.6 C=11.9      D2=27.4     P=2.8   N=2

油站号I

离出发点的距离Di

每升汽油价格Pi

1

102.0

2.9

2

220.0

2.2

Output

26.95(该数据表示最小费用)

代码:

#include <iostream>
int main()
{
    
double rest=0,need,p[12],s,c,t,d[12];
    
int n;
    scanf(
"%lf%lf%lf%lf%d",&s,&c,&t,&p[0],&n);
    
for(int i=1;i<=n;i++)
        scanf(
"%lf%lf",&d[i],&p[i]);
    d[
0]=0;
    d[n
+1]=s;
    
int k=0,j=0,min=0,min2=0,back=0;
    
double cost=0;
    
while(k<=n)
  
{
        j
=k;
        
while(d[j+1]-d[k]<=c*t&&j<=n)
      
{
            j
++;
            
if(min==0&&p[j]<p[k]) min=j;
            
if(min2==0||p[j]<p[min2]) min2=j;
        }

        
if(j==k)
      
{
            printf(
"No Solution\n");
            
return 0;
        }

        
if(!min)
      
{
            need
=c-rest;
            cost
+=need*p[k];
            rest
=c-(d[min2]-d[k])/t;
            k
=min2;
        }

        
else
        
{
            need
=(d[min]-d[k])/t-rest;
            
if(need<0)
                need
=0;
            cost
+=need*p[k];
            rest
=0;
            k
=min;
        }

        min
=min2=0;
    }

    printf(
"%.2lf\n",cost);
    
return 0;
}
posted @ 2010-04-09 13:48 EG-HUA 阅读(809) | 评论 (0)编辑 收藏

2010年4月6日 #

                                          金明的预算方案

                                             
金明今天很开心,家里购置的新房就要领钥匙了,新房里有一间金明自己专用的