7.23 题目

sheep426

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 ]

小康

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

sheep426

顶，凸包问题

sheep426

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

小康

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

#include<stdio.h>
int main()
{
        int map[101][101];
        int num[101],check[101];
        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[j]=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[v-65][u-65]=l;
                                map[u-65][v-65]=l;
                        }
                }
                for (i=0;i<n;i++) check=1;
                check[0]=0;               
                num[0]=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[k] && map[num[j]][k]>0 && map[num[j]][k]<l)
                                {
                                        u=k;
                                        l=map[num[j]][k];
                                }
                        }
                        num=u;
                        check=0;
                        min+=l;
                }
                printf(\"%d\\n\",min);


        }
        return 0;

}

小康

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

小康

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[110],y[110],check[5];
  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])  maxx=i;
           }          
           if(n==1)
           {
                   printf(\"0.00\\n\");
                   continue;
           }
           //从最低的点开始搜索
           j=maxx;
           min=0;
           if(j==0) mini=1;else mini=0;
           x2=x[mini]-x[j];
           y2=y[mini]-y[j];
           do
           {                  
                   y2=0;
                   x2=0;
                   //搜索所有的点
                   for (i=0;i<n;i++) if(i!=j)
                   {
                           x1=x-x[j];
                           y1=y-y[j];
                           //寻找最\"损失重\"的向量,这里用到了计算几何关于向量的定义
                           //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[mini]-y[j])*(y[mini]-y[j])+(x[mini]-x[j])*(x[mini]-x[j]));
                   j=mini;
                 //  check[j]=1;

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

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