为生存而奔跑

   :: 首页 :: 联系 :: 聚合  :: 管理
  271 Posts :: 0 Stories :: 58 Comments :: 0 Trackbacks

留言簿(5)

我参与的团队

搜索

  •  

积分与排名

  • 积分 - 268366
  • 排名 - 83

最新评论

阅读排行榜

评论排行榜

http://202.120.80.191/problem.php?problemid=2614

#include <iostream>
#include 
<algorithm>
#include 
<vector>
#include 
<string>
using namespace std;
const int maxn=110;
int g[maxn][maxn],pre[maxn];
int maxbetween[maxn][maxn];
int x[maxn],y[maxn];
int n;
int ans;
void init()
{
    
for(int i=0;i<n;i++)
    {
        g[i][i]
=0;
        
for(int j=i+1;j<n;j++)
            g[i][j]
=g[j][i]=abs(x[i]-x[j])+abs(y[i]-y[j]);
    }
}
int prim(int u)
{
    
int ans=0;
    
int k,smin;
    
int dist[maxn];
    
bool visit[maxn];
    memset(maxbetween,
0,sizeof(maxbetween));
    
for(int i=0;i<n;i++)
    {
        dist[i]
=g[u][i];
        visit[i]
=0;
        pre[i]
=u;
    }
    visit[u]
=1;
    pre[u]
=-1;
    
for(int i=1;i<n;i++)
    {
        k
=-1;
        smin
=INT_MAX;
        
for(int j=0;j<n;j++)
            
if(!visit[j] && dist[j]<smin)
            {
                k
=j;
                smin
=dist[j];
            }
        
//if(k==-1) continue;
        
        
for(int j=0;j<n;j++)
            
if(visit[j])
                maxbetween[j][k]
=maxbetween[k][j]=max(maxbetween[j][pre[k]],smin);
        
        ans
+=smin;
        visit[k]
=1;

        
for(int j=0;j<n;j++)
            
if(!visit[j] && g[k][j]<dist[j])
            {
                dist[j]
=g[k][j];
                pre[j]
=k;
            }
    }
    
return ans;
}
int unique()
{
    
int res=INT_MAX;
    
for(int i=0;i<n;i++)
        
for(int j=0;j<n;j++)
            
if(i!=&& i!=pre[j] && j!=pre[i] )
                res
=min(res,ans-maxbetween[i][j]+g[i][j]);
    
return res;
}
int main()
{
    
while(scanf("%d",&n)!=EOF)
    {
        
for(int i=0;i<n;i++)
            scanf(
"%d%d",&x[i],&y[i]);
        init();
        ans
=prim(0);
        printf(
"%d\n%s\n",ans,unique()==ans?"Yes":"No");
    }
}

posted on 2009-10-05 19:49 baby-fly 阅读(490) 评论(0)  编辑 收藏 引用 所属分类: Algorithm

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理