论坛 › 【编程】编程圣殿 › 7.23 题目

sheep426 发表于 2005-7-22 21:32

7.23 题目

http://acm.zju.edu.cn/show_problem.php?pid=1453
http://acm.zju.edu.cn/show_problem.php?pid=1406
http://acm.zju.edu.cn/show_problem.php?pid=1492
http://acm.zju.edu.cn/show_problem.php?pid=1449
http://acm.zju.edu.cn/show_problem.php?pid=1496
http://acm.zju.edu.cn/show_problem.php?pid=1431
http://acm.zju.edu.cn/show_problem.php?pid=1526
http://acm.zju.edu.cn/show_problem.php?pid=1514
http://acm.zju.edu.cn/show_problem.php?pid=1577

[ Last edited by sheep426 on 2005-7-23 at 14:36 ]

小康 发表于 2005-7-22 23:22

1492是网络流中的最大强流通子图,不知道除了网络流算法还能不能有其他算法

sheep426 发表于 2005-7-22 23:48

顶，凸包问题

sheep426 发表于 2005-7-23 10:24

还有动态规划。。。。。。。

小康 发表于 2005-7-24 11:56

1406是典型的最小生成树
最小生成树的定义相对抽象,我这里简单介绍下.
这道题的解,就是用N条变,把这些定点都连接起来,就OK了.
理论上就是最小生成树.
这道题的解放,从某一个点开始,把这点置为"已知"点,假设为集合A,每次都这样,找出一个端点在集合A中,另一个端点不在集合A中的所有线段中最小的一条,假设这条最小的线段的不在集合A的端点为x,把x放入集合A中,继续这样的搜索.知道所有的点都在集合A中了.
还有其他算法,大家有空看看.代码如下:

#include<stdio.h>
int main()
{
        int map;
        int num,check;
        int i,j,k,n,l,min;
        char u,v;
        freopen("in.txt","r",stdin);

        while(scanf("%d",&n),n)
        {
                for (i=0;i<n;i++) for (j=0;j<n;j++) map=0;
                for (i=1;i<n;i++)
                {                       
                        scanf("%c",&v);
                        scanf("%c",&v);
                        scanf("%d",&k);
                        for (j=0;j<k;j++)
                        {
                                scanf("%c",&u);
                                scanf("%c",&u);
                                scanf("%d",&l);
                                map=l;
                                map=l;
                        }
                }
                for (i=0;i<n;i++) check=1;
                check=0;               
                num=0;
                min=0;
                for (i=1;i<n;i++)
                {
                        l=10000000;
                        u=0;
                        for (j=0;j<i;j++)
                        {
                                for (k=0;k<n;k++) if(check && map]>0 && map]<l)
                                {
                                        u=k;
                                        l=map];
                                }
                        }
                        num=u;
                        check=0;
                        min+=l;
                }
                printf("%d\n",min);


        }
        return 0;

}

小康 发表于 2005-7-24 12:00

1453是凸包问题.
http://zh1110.nease.net/AI/PZ.htm 这里有介绍凸包
http://www.gameres.com/Articles/Program/Abstract/Geometry.htm 计算集合的概念
我做做看

小康 发表于 2005-7-24 14:52

1453 A了.
做法为,从最小面的点开始,寻找与该点的线段最"顺时钟的点",接着从该"最顺时钟"的点继续查找,直到找到最开始的点.代码如下

#include<stdio.h>
#include<string.h>
#include<math.h>
int main()
{
int i,j,n,maxx,mini,xx,xx2;
double x1,x2,y1,y2;
int x,y,check;
double k,min,mink;
freopen("in.txt","r",stdin);
while(scanf("%d",&n),n)
   {
           maxx=0;
           //读树
           for (i=0;i<n;i++)
           {
                   scanf("%d %d",&x,&y);
                   if(y<y)maxx=i;
           }          
           if(n==1)
           {
                   printf("0.00\n");
                   continue;
           }
           //从最低的点开始搜索
           j=maxx;
           min=0;
           if(j==0) mini=1;else mini=0;
           x2=x-x;
           y2=y-y;
           do
           {                  
                   y2=0;
                   x2=0;
                   //搜索所有的点
                   for (i=0;i<n;i++) if(i!=j)
                   {
                           x1=x-x;
                           y1=y-y;
                           //寻找最"损失重"的向量,这里用到了计算几何关于向量的定义
                           //http://www.gameres.com/Articles/Program/Abstract/Geometry.htm#凸包的概念
                           if(x1*y2-x2*y1>=0)
                           {
                                   mini=i;
                                   x2=x1;
                                   y2=y1;
                           }
                   }                  
                   min=min+sqrt((double)(y-y)*(y-y)+(x-x)*(x-x));
                   j=mini;
               //check=1;

           }while(j!=maxx);
           printf("%0.2f\n",min);
          
          
   }
return 0;
}

[ Last edited by 小康 on 2005-7-24 at 14:53 ]

查看完整版本: 7.23 题目