亚洲一区二区欧美,国产精品h在线观看,欧美精品一区二

关于

蜗牛 — Sat, 29 Nov 2008 15:42:00 GMT

一    ACM      如果说把ACM比作一位恋人，那么我们��是前世五百�ơ的回眸�Q�才换来今生的一�ơ擦肩而过了�?
     暑假�Q�去了趟�q�州实习�Q�回来后��到学校开始省赛的集训。从八月十日号到现在�Q�我在不分白天黑夜的敲题�Q�学��法。《算法导论》已被我借了快一�q�了�?
     一路走来，感慨颇多�Q�有心酸�Q�也有快乐�?/span>
     有时会因为提交一个题目，从早上一直WA��C��午，饿了�Q�就那样挺着�Q�不AC不�Ş休�?
     省赛之前�Q�学校还有几个队员有的时候交��一下，而现在就只有我的伙伴也只有百度和��h��?
     省赛�Q�早已预见的�l�果�Q�我要的只是的进步�?
     见识�q�很多牛人，学习了很多的��法�Q�也敲过上万行的代码�?
     在湖大的�|�站上敲�?50道题目，后来��p�{北大的POJ了。我的打��是敲完�q�个学期�Q�至��要�?00以上�Q�挤�q?000�?
     在算法的��h��里，我这��小的蜗牛，也只有一天一天的努力往上爬�Q�不知道何时才能看到那些灿烂的阳光�?
     也许�Q�阳光早已洒落在�q�程里了�?
     有时候会惻I��如果我早一�Ҏ��触ACM,今天会不会牛以来呢？如果我在一所重点大学�Q�我的ACM生��又会怎样呢？如果……�?
     可是生活没有如果�Q�刚开始相恋，我就要毕业了�?
     有些遗憾�Q�但也不悔，在我有生之年�Q��ؓ之奋斗过�?

�?nbsp; 生活       11月，有些人的影子开始模�p�。就�q�样吧，让生�zȝ��水把那些往事都带走�?
     很少��M��课，估计每节译և�勤的同学不会��过两位数�?
     但我很珍惜这�D�|��后的学校生活�Q�可以舒服的睡觉�Q�可以自��q��敲题�Q�可以轻杄��写字�Q�可以不��那些关于经��危��带来的��׃��危机�Q�可以放肆的像个孩子�?
     臛_��在没有毕业之前我�q�是一个学生，但很快就不是了�?
     走入�C�会�Q�工作，我就要承担�v一份责��M��。亲��q��爸爸妈妈�Q��ؓ了我苦了大半辈子。我要努力挣钱，让我们的日子�q�的好点�?
     朋友们，�q�段联系��了�Q�其实我也不惌��栗��?
     天冷了，整天一个�h对这电脑�Q�有�Ҏ��回家了�?
      生活很简单，每天睡到九点起床�Q�忙�z�M��下卫生，��开电脑�Q�在北大的题��里遨游了，无边无际�?
     中午�Q�匆忙的吃个快餐。��杯咖啡，打开�H�帘�Q�晒会儿太阳�Q��l�做题�?
     晚上的时候，跑到学校食堂吃顿饭。然后在夜幕下，一个�h游荡�?
     我很喜欢��L��场，那些�I�旷与寂寥，是狂�Ƣ过后一个�h悲伤。听着�q�播里《旋木》，王菲的空灵与�U��a�?
     极目�q�眺�Q�北方的天空有两颗闪亮的星星�Q�不知道他们隔了有多�q�，有没有见证过所谓的永恒�?
     回来后，�l�箋敲题�q�午夜�?

�?nbsp; ��奇      一个�h的时候，思想会很�z�跃�Q�也惌��很多的问题�?
     ��Z��么我会来到这个星球上�Q��ƈ且是�q�不来，晚不来，偏偏在这个时候来了呢�Q?
     在我没来到这个世界来之前的那么多�q�_��世界是个什么样子呢�Q�历史上那么多的人，他们都死了，到底他们有过怎样的生�z�？
     是什么力量��生了生命�Q�怎么��有了我�Q?太神奇了�Q?wbr>
     未来会变成什么样子呢�Q�一癑ֹ��Q�一千年�Q�到时候我们都不在了�?
     一惛_��我们都会死，��׃��很悲伤，那些无可奈何的悲伤�?
     以前从来惌��的问题，随着��L��奶奶的去世，久久的会在心里缠�l�着�?
     悲伤�Q�是因�ؓ��x��着失去�?
     也许�Q�活着��׃��仅只是�ؓ了活着而活着�Q�一场游戏一场梦�Q�管那么多干嘛呢�Q?nbsp;
     有梦��做�Q�有酒就醉，痛痛快快的在�q�个世界��C��遭吧�?wbr>

�?nbsp; 打算      打算找个人，好好的谈一场恋爱�?
     妈妈的生日快��C��Q�准备给她老�h安��一份礼物�?
     打算着再敲两个月题�Q�努力的向牛看齐�Q�不要那么菜��p��?
     老姐�l�婚了，打算到北京去看看他们�?
     打算着明年毕业实习�Q�毕业设计，扑ַ�作�?
     打算不要��L��疲劳战术了，得好好的�ȝ��一下��n体�?
     打算调整好生物钟�Q�十二点以前一定上床睡觉�?
     打算着选个阛_��灿烂的日子，好好的出去走走玩玩。这些天天气很好�Q�但一直舍不得�Q�时间很不够用�?
     打算好好的敲题，好好的学习，好好的生�z�，好好的待生命中遇到的每一个�h�?
     现在打算着马上关电脑上床睡觉�?wbr>

蜗牛 2008-11-29 23:42 发表评论

POJ 1083 C++ �Q�水题）

蜗牛 — Sat, 29 Nov 2008 13:33:00 GMT

//水题也搞了好久，郁闷
//关键是在于区间篏计的时候一个偶数基数的问题
#include
#include
using namespace std;
int main()
{ int test,n,i,j;
  int s[200],t[200],used[200];
  freopen("in.txt","r",stdin);
  freopen("out.txt","w",stdout);
  scanf("%d",&test);
  while(test--)
       { scanf("%d",&n);
         memset(used,0,sizeof(used));
         for(i=0;i
              scanf("%d%d",&s[i],&t[i]);
         for(i=0;i
              {  if(s[i]>t[i])
                   swap(s[i],t[i]);
                 if(s[i]%2==0)
                    s[i]--;
                  s[i]=s[i]/2;
                 if(t[i]%2==0)
                   t[i]--;
                 t[i]=t[i]/2;
               for(j=s[i];j<=t[i];j++)
                     used[j]++;
              }
           sort(used,used+200);
           printf("%d\n",used[199]*10);
   }
return 0;
}

蜗牛 2008-11-29 21:33 发表评论

POJ 3041 C++ �Q�图论）

蜗牛 — Sat, 29 Nov 2008 07:37:00 GMT

//最�q�专用Ford_Fulkerson 和hungary水到手��Y
//最��割定理是一个二分图中很重要的定理－�Q�－一个二分图中的最大匹配数�{�于�q�个图中的最��点覆盖数�?wbr>
//最��点覆盖�Q�假如选了一个点��q��当于覆盖了以它�ؓ端点的所有边�Q�你需要选择最��的�Ҏ��覆盖所有的�?
#include
using namespace std;
int n,m,res;
int l[500],r[500],map[500][500],used[500];
bool path(int u)
{int v;
for(v=0;v
     if(map[u][v] && !used[v])
       {used[v]=1;
        if(r[v]==-1 || path(r[v]))
           {  l[u]=v;
              r[v]=u;
              return true;
           }
       }
   return false;
}
void solve()
{ int i;
  memset(l,-1,sizeof(l));
  memset(r,-1,sizeof(r));
  for(i=0;i
       if(l[i]==-1)
           {  memset(used,0,sizeof(used));
              if(path(i))
                  res++;
           }

}
int main()
{ int i,a,b;
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
while((scanf("%d%d",&n,&m))!=EOF)
       { memset(map,0,sizeof(map));
         for(i=0;i
             { scanf("%d%d",&a,&b);
               map[a-1][b-1]=1;
              }
           res=0;
           solve();
           cout<
         }
   return 0;
}

蜗牛 2008-11-29 15:37 发表评论

POJ 1496 C++ �Q�图论）

蜗牛 — Sat, 29 Nov 2008 05:08:00 GMT

//匈牙利算法实��C��分图的最大匹配，较最大流实现来的��单些
//特点不需要徏模，原理�q�是朴素最大流原理�Q�寻扑֢��q��\径用DFS,如找��C��条增�q��\径，沿�\边取�?wbr>

#include
using namespace std;
int n,m,res;
int l[300],r[300],map[300][300],used[300];

bool path(int u)
{int v;
for(v=0;v
     if(map[u][v] && !used[v])
       {used[v]=1;
        if(r[v]==-1 || path(r[v]))
           {  l[u]=v;
              r[v]=u;
              return true;
           }
       }
   return false;
}

void solve()
{ int i;
  memset(l,-1,sizeof(l));
  memset(r,-1,sizeof(r));
  for(i=0;i
       if(l[i]==-1)
           {  memset(used,0,sizeof(used));
              if(path(i))
                 res++;
            }

}

int main()
{ int Case,i,j,k,temp;
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
  scanf("%d",&Case);
  while(Case--)
       { memset(map,0,sizeof(map));
         scanf("%d%d",&n,&m);
         for(i=0;i
             { scanf("%d",&k);
               for(j=0;j
                   {scanf("%d",&temp);
                    map[i][temp-1]=1;
                   }
               }
           res=0;
           solve();
           if(res==n)
              printf("YES\n");
           else
             printf("NO\n");
         }
   return 0;
}

什么是二分图，什么是二分囄��最大匹配，�q�些定义我就不讲了，�|�上随便都找得到。二分图的最大匹配有两种求法�Q�第一�U�是最大流�Q�我在此假设读者已有网�l�流的知识）�Q�第二种��是我现在要讲的匈牙利算法。这个算法说白了��是最大流的算法，但是它跟据二分图匚w��q�个问题的特点，把最大流��法做了��化，提高了效率。匈牙利��法其实很简单，但是�|�上搜不��C��么说得清楚的文章。所以我军_��要写一下�?br>最大流��法的核心问题就是找增广路径�Q�augment path�Q�。匈牙利��法也不例外�Q�它的基本模式就是：

初始时最大匹配�ؓ�I?br>while 扑־�到增�q��\�?br>    do 把增�q��\径加入到最大匹配中�?wbr>
可见和最大流��法是一��L��。但是这里的增广路径��有它一定的�Ҏ��性，下面我来分析一下�?br>�Q�注�Q�匈牙利��法虽然�Ҏ��上是最大流��法�Q�但是它不需要徏�|�络模型�Q�所以图中不再需要源点和汇点�Q�仅仅是一个二分图。每条边也不需要有方向。）

�? �?
�?是我�l�出的二分图中的一个匹配：�Q?�Q?�Q�和�Q?�Q?�Q�。图2��是在这个匹配的基础上找到的一条增�q��\径：3->6->2->5->1->4�?wbr>我们借由它来描述一下二分图中的增广路径的性质�Q?br>
(1)有奇数条辏V�?br>(2)��L��在二分图的左半边�Q�终点在叛_��辏V�?br>(3)路径上的点一定是一个在左半边，一个在叛_��边，交替出现。（其实二分囄��性质��决定了�q�一点，因�ؓ二分囑֐�一边的点之间没有边相连�Q�不要忘记哦。）
(4)整条路径上没有重复的炏V�?br>(5)��L��和终炚w��是目前还没有配对的点�Q�而其它所有点都是已经配好对的。（如图1、图2所�C�，�Q?�Q?�Q�和�Q?�Q?�Q�在�?中是两对已经配好对的点；而�v�?和终�?目前�q�没有与其它炚w��寏V��）
(6)路径上的所有第奇数条边都不在原匚w��中，所有第偶数条边都出现在原匹配中。（如图1、图2所�C�，原有的匹配是�Q?�Q?�Q�和�Q?�Q?�Q�，�q�两条配匹的边在�?�l�出的增�q��\径中分边是第2和第4条边。而增�q��\径的�W?�?�?条边都没有出现在�?�l�出的匹配中。）
(7)最后，也是最重要的一条，把增�q��\径上的所有第奇数条边加入到原匚w��中去�Q��ƈ把增�q��\径中的所有第偶数条边从原匚w��中删除（�q�个操作�U�Cؓ增广路径�?wbr>取反�Q�，则新的匹配数��比原匹配数增加�?个。（如图2所�C�，新的匚w��是所有蓝色的边，而所有红色的边则从原匚w��中删除。则新的匚w��Cؓ3。）

不难想通，在最初始�Ӟ��q�没有�Q何匹配时�Q�图1中的两条灰色的边本��n也是增广路径。因此在�q�张二分图中��L��最大配匹的�q�程可能如下�Q?br>
(1)扑ֈ�增广路径1->5�Q�把它取反，则匹配数增加�?�?br>(2)扑ֈ�增广路径2->6�Q�把它取反，则匹配数增加�?�?br>(3)扑ֈ�增广路径3->6->2->5->1->4�Q�把它取反，则匹配数增加�?�?br>(4)再也找不到增�q��\径，�l�束�?br>
当然�Q�这只是一�U�可能的��程。也可能有别的找增广路径的顺序，或者找��C��同的增广路径�Q�最�l�的匚w��Ҏ��也可能不一栗��但是最大匹配数一定都是相同的�?br>
对于增广路径�q�可以用一个递归的方法来描述。这个描�q�C��一定最准确�Q�但是它揭示了寻扑֢��q��\径的一般方法：
“从点A出发的增�q��\�?#8221;一定首先连向一个在原匹配中没有与点A配对的点B。如果点B在原匚w��中没有与��M��炚w��对，则它��是�q�条增广路径的终点；反之�Q�如果点B已与点C配对�Q�那么这条增�q��\径就是从A到B�Q�再从B到C�Q�再加上“从点C出发的增�q��\�?#8221;。�ƈ且，�q�条从C出发的增�q��\径中不能与前半部分的增广路径有重复的炏V�?br>
比如�?中，我们要寻找一条从3出发的增�q��\径，要做以下3步：
(1)首先�?出发�Q�它能连到的点只�?�Q��?在图1中已�l�与2配对�Q�所以目前的增广路径��是3->6->2再加上从2出发的增�q��\径�?br>(2)�?出发�Q�它能连到的不与前半部分路径重复的点只有5�Q�而且5��实在原匚w��中没有与2配对。所以从2�q�到5。但5在图1中已�l�与1配对�Q�所以目前的增广路径�?->6->2->5->1再加上从1出发的增�q��\径�?br>(3)�?出发�Q�能�q�到的不与自已配对�ƈ且不与前半部分�\径重复的点只�?。因�?在图1中没有与��M��炚w��对，所以它��是�l�点。所以最�l�的增广路径�?->6->2->5->1->4�?br>
但是严格地说�Q�以上过�E�中�?出发的增�q��\径（2->5->1->4�Q�和�?出发的增�q��\径（1->4�Q��ƈ不是真正的增�q��\径。因为它们不�W�合前面讲过的增�q��\径的�W?条性质�Q�它们的��L��都是已经配过对的炏V��我们在�q�里�U�它们�ؓ“增广路径”只是��Z��方便说明整个搜寻的过�E�。而这两条路径本��n只能��是两个不�ؓ外界所知的子过�E�的�q�回�l�果�?br>昄��Q�从上面的例子可以看出，搜寻增广路径的方法就是DFS�Q�可以写成一个递归函数。当�Ӟ��用BFS也完全可以实现�?br>
��x��Q�理论基��部䆾讲完了。但是要完成匈牙利算法，�q�需要一个重要的定理�Q?br>
如果从一个点A出发�Q�没有找到增�q��\径，那么无论再从别的点出发找到多��增�q��\径来改变现在的匹配，从A出发都永�q�找不到增广路径�?br>
要用文字来证明这个定理很�J�，话很难说�Q�要么我�q�得多画一张图�Q�我在此��q��了。其实你自己��d��个图�Q�试图�D两个反例�Q�这个定理不难想通的。（�l�个提示。如果你试图举个反例来说明在扑ֈ�了别的增�q��\径�ƈ改变了现有的匚w��后，从A出发��p��扑ֈ�增广路径。那么，在这�U�情况下�Q�肯定在扑ֈ�别的增广路径之前�Q�就能从A出发扑ֈ�增广路径。这��׃��假设矛盾了。）
有了�q�个定理�Q�匈牙利��法��成形了。如下：
初始时最大匹配�ؓ�I?br>for 二分囑ַ�半边的每个点i
    do 从点i出发��L��增广路径。如果找刎ͼ�则把它取反（卛_��加了��M��匚w��敎ͼ��?wbr>

如果二分囄��左半边一共有n个点�Q�那么最多找n条增�q��\径。如果图中共有m条边�Q�那么每找一条增�q��\径（DFS或BFS�Q�时最多把所有边遍历一遍，所花时间也��是m。所以�ȝ��旉��大概��是O�Q�n * m�Q��?br>

蜗牛 2008-11-29 13:08 发表评论

POJ 3020 C++ �Q�图论）

蜗牛 — Sat, 29 Nov 2008 03:06:00 GMT

//用算法导��Z��上最大流做的二分囑֌�配，所以内存耗的比较大，因�ؓ需要队列来存储增广路径
//一个数�l�没有初始化�Q�wrong了N��?wbr>
//很多人都是用匈牙利算法做的，偶也准备学学传说中的匈牙利算�?wbr>
#include
using namespace std;
int h,w,flag,res,node;
int arr[500][500],map[50][20];
int q[10000],pre[10000],used[500];
int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};
int path(int s)  //��L��增广路径
{ int u,head,tail,temp,i,j;
  head=tail=0;
  q[tail++]=s;
  used[s]=1;
  while(head
       { temp=tail;
         for(i=head;i
             {    u=q[i];
                  if(u==1)
                     return 1;
                  for(j=0;j
                     if(used[j]==0 && arr[u][j]>0)
                        {pre[j]=u;
                         used[j]=1;
                         q[tail++]=j;
                         }
              }
          head=temp;
       }
  return 0;
}

void  ford_fulkerson() //修改增光路径上边的残留容量，记录匚w��的结�?br>{ int i,j,u,v,min,x,y;
  min=INT_MAX;
  u=pre[1];
  v=1;
  while(u>=0)
       {if(arr[u][v]
             min=arr[u][v];
            v=u;
            u=pre[u];
       }

  u=pre[1];
  v=1;
  while(u>=0)
       {   arr[u][v]=arr[u][v]-min;
           arr[v][u]=arr[v][u]+min;
           v=u;
           u=pre[u];
        }
   res=res+min;
}

int main()
{int i,j,k,Case,x,y;
char c;
       freopen("in.txt","r",stdin);
       freopen("out.txt","w",stdout);
         scanf("%d",&Case);
       while(Case--)
          { flag=0;
            res=0;
            node=2;
          scanf("%d%d",&h,&w);
          memset(map,0,sizeof(map));
          memset(used,0,sizeof(used));
          memset(arr,0,sizeof(arr));
          for(i=0;i
              {getchar();
               for(j=0;j
                  { scanf("%c",&c);
                    if(c=='*')
                      map[i][j]=node++;
                   }
               }
           for(i=0;i
              for(j=0;j
                  { if(map[i][j] && !used[map[i][j]])
                       {  arr[0][map[i][j]]=1;
                          used[map[i][j]]=1;
                          for(k=0;k<4;k++)
                             { x=i+dx[k];
                               y=j+dy[k];
                               if(x>=0 && x=0 && y
                               {arr[map[i][j]][map[x][y]]=1;
                                arr[map[x][y]][1]=1;
                                used[map[x][y]]=1;
                               }
                             }
                       }
                  }
           while(!flag)
             { memset(used,0,sizeof(used));
               memset(pre,-1,sizeof(pre));
               if(path(0))
                  ford_fulkerson();
                else
                  flag=1;
              }
    printf("%d\n",node-2-res);
  }
   return 0;
}

蜗牛 2008-11-29 11:06 发表评论

POJ 1087 C++ �Q�图论）

蜗牛 — Fri, 28 Nov 2008 06:06:00 GMT

//题目太难懂了�Q�徏模比较困�?wbr>
//很多人把它做成二分图匚w��
//但貌似用最大流也能求出�?br>#include
#include
#include
using namespace std;
int nr,np,na,flag,res,node;
int arr[402][402];
int q[1000],pre[1000],used[402];
map PR;

int path(int s)
{ int u,head,tail,temp,i,j;
head=tail=0;
q[tail++]=s;
used[s]=1;
while(head       { temp=tail;
         for(i=head;i             {    u=q[i];
                  if(u==1)
                     return 1;
                  for(j=0;j                     if(used[j]==0 && arr[u][j]>0)
                        {pre[j]=u;
                         used[j]=1;
                         q[tail++]=j;
                         }
              }
          head=temp;
       }
return 0;
}

void ford_fulkerson()
{ int i,j,u,v,min,x,y;
min=INT_MAX;
u=pre[1];
v=1;
while(u>=0)
       {if(arr[u][v]             min=arr[u][v];
            v=u;
            u=pre[u];
       }

u=pre[1];
v=1;
while(u>=0)
       {   arr[u][v]=arr[u][v]-min;
           arr[v][u]=arr[v][u]+min;
           v=u;
           u=pre[u];
        }
   res=res+min;
}

int main()
{int u,v,w,i,j;
char str1[25],str2[25];
       freopen("in.txt","r",stdin);
       freopen("out.txt","w",stdout);
         scanf("%d",&nr);
          flag=0;
          res=0;
          node=2;
          for(i=0;i             { scanf("%s",str1);
               if(!PR[str1])
                   PR[str1]=node++;
               arr[0][PR[str1]]++;
             }

         scanf("%d",&np);
         for(i=0;i             { scanf("%s%s",str1,str2);
                 if(!PR[str2])
                    PR[str2]=node++;
                arr[PR[str2]][1]++;
             }

         scanf("%d",&na);
         for(i=0;i             {   scanf("%s%s",str1,str2);
                 if(!PR[str1])
                    PR[str1]=node++;
                  if(!PR[str2])
                    PR[str2]=node++;
                  arr[PR[str2]][PR[str1]]=INT_MAX;
              }

         while(!flag)
             { memset(used,0,sizeof(used));
               memset(pre,-1,sizeof(pre));
               if(path(0))
                  ford_fulkerson();
                else
                  flag=1;
              }
   printf("%d\n",np-res);
   return 0;
}

蜗牛 2008-11-28 14:06 发表评论

POJ 1459 C++ �Q�图论）

蜗牛 — Thu, 27 Nov 2008 09:42:00 GMT

一�Q�Ford和Fulkerson�q�加��法.

　　基本思�\�Q�把各条弧上单位��量的费用看成某�U�长�?用求解最短�\问题的方法确定一条自V1至Vn的最短�\;在将�q�条最短�\作�ؓ可扩充�\,用求解最大流问题的方法将其上的流量增��x��大可能�?而这条最短�\上的��量增加�?其上各条弧的单位��量的费用要重新��定,如此多次�q�代,最�l�得到最��费用最大流.

　　�q�加��法�Q?br>
　　1) �l�定目标��量F�?#8734;,�l�定最��费用的初始可行��?0

　　2) 若V(f)=F,停止,f为最��费用流;否则�?3).

　　3) 构�?相应的新的费用有向图W(fij),在W(fij)��L��Vs到Vt的最��费用有向�\P(最短�\),沿P增加��f的流量直到F,�?2);若不存在从Vs到Vt的最��费用的有向路P,停止.f��是最��费用最大流.

　　具体解题步骤�Q?br>
　　讑֛�中双�U�所�C��\径�ؓ最短�\径，费用有向图�ؓW�Q�fij�Q�．

　　在图(a)中给出零��?f,在图(b)中找到最��费用有向�\,修改�?a)中的可行��?δ=min{4,3,5}=3,得图(c),再做�?c)的调整容量图,再构造相应的新的最��费用有向�\得图(d), 修改�?c)中的可行��? δ=min{1,1,2,2}=1,得图(e),以此�c�L��,一直得到图(h),在图(h)中以无最��费用有向�\,停止,�l�计��?

　　�?h)�?最��费�?1*4+3*3+2*4+4*1+1*1+4*2+1*1+3*1=38

　　�?g)�?最大流=5

　　最大流问题仅注意网�l�流的流通能力，没有考虑��通的费用。实际上费用因素是很重要的。例如在交通运输问题中�Q�往往要求在完成运输�Q务的前提下，��L��一个��总运输费用最省的�q�输�Ҏ��Q�这��是最��费用流问题。如果只考虑单位货物的运输费用，那么�q�个问题��变成最短�\问题。由此可见，最短�\问题是最��费用流问题的基��。现已有一�p�d��求最短�\的成功方法。最��费用流(或最��费用最大流)问题 �Q�可以交替��用求解最大流和最短�\两种�Ҏ��Q�通过�q�代得到解决�?br>

//老老实实看了一天的书，�l�于敲出了第一个关于网�l�流的程�?wbr style="LINE-HEIGHT: 1.3em">
//庆祝��的零的�H�破
#include
using namespace std;
int n,np,nc,m,flag,res;
int arr[110][110];
int q[10000],pre[10000],used[110];

int path(int s)
{ int u,head,tail,temp,i,j;
head=tail=0;
q[tail++]=s;
used[s]=1;
while(head       { temp=tail;
         for(i=head;i             {    u=q[i];
                  if(u==n+1)
                     return 1;
                  for(j=0;j<=n+1;j++)
                     if(!used[j] && arr[u][j]>0)
                        {pre[j]=u;
                         used[j]=1;
                         q[tail++]=j;
                         }
              }
          head=temp;
       }
return 0;
}

void ford_fulkerson()
{ int i,j,u,v,min;
min=INT_MAX;

u=pre[n+1];
v=n+1;
while(u>=0)
       {if(arr[u][v]             min=arr[u][v];
           v=u;
           u=pre[u];

       }

u=pre[n+1];
v=n+1;
while(u>=0)
       {   arr[u][v]=arr[u][v]-min;
           arr[v][u]=arr[v][u]+min;
           v=u;
           u=pre[u];
        }
   res=res+min;
}

int main()
{int u,v,w,i,j;
       freopen("in.txt","r",stdin);
       freopen("out.txt","w",stdout);
while((scanf("%d%d%d%d",&n,&np,&nc,&m))!=EOF)
       { flag=0;
          res=0;
          memset(arr,0,sizeof(arr));
           for(i=0;i             { while(getchar()!='(');
               scanf("%d,%d)%d",&u,&v,&w);
               arr[u][v]=w;
             }
           for(i=0;i             { while(getchar()!='(');
                scanf("%d)%d",&v,&w);
                arr[n][v]=w;
              }

            for(i=0;i             { while(getchar()!='(');
               scanf("%d)%d",&u,&w);
               arr[u][n+1]=w;
              }

           while(!flag)
             { memset(used,0,sizeof(used));
               memset(pre,-1,sizeof(pre));
               if(path(n))
                  ford_fulkerson();
                else
                  flag=1;
              }
    printf("%d\n",res);
}
   return 0;
}

蜗牛 2008-11-27 17:42 发表评论

POJ 1094 C++ �Q�图论）

蜗牛 — Wed, 26 Nov 2008 16:22:00 GMT

//用DFS�q�行拓扑排序�Q�超�?�Q�只能重�?wbr>
#include"stdio.h"
#include"string.h"
#include"stdlib.h"

int map[26][26],v[26],used[26],flag,n,total;
char str[27];
void sort(int i,int m)
{ int k;
if(total==n)
     {  flag=2;
          return ;
      }
for(k=0;k
      { if(map[i][k]==0)
           continue;
       if(v[k])
          { flag=1;
             return ;
           }
       str[m]=k+65;
       total++;
       v[k]=1;
       sort(k,m+1);
       if(flag)
          return ;
       v[k]=0;
       total--;
      }
}

int main()
{int row,i,j,a,b,k,l;
char s[4];
   freopen("in.txt","r",stdin);
   freopen("out.txt","w",stdout);
while(1)
  { scanf("%d%d",&n,&row);
     if(n==0 && row==0)
        break;

     flag=0;
     memset(map,0,sizeof(map));
     memset(used,0,sizeof(used));
     for(k=1;k<=row;k++)
         { scanf("%s",s);
          if(!flag)
           {memset(v,0,sizeof(v));
            a=s[0]-65;
            b=s[2]-65;
            used[a]=1;
            used[b]=1;
            map[a][b]=1;
            for(i=0;i
               {  if(used[i]==0)
                     break;
                    total=1;
                    v[i]=1;
                    str[0]=i+65;
                    sort(i,1);
                    v[i]=0;
               }

             if(flag==1)
              printf("Inconsistency found after %d relations.\n",k);
             else if(flag==2)
               {printf("Sorted sequence determined after %d relations: ",k);
                       for(i=0;i
                          printf("%c",str[i]);
                         printf(".\n");
                         flag=1;
               }
          }
     }

   if(!flag)
      printf("Sorted sequence cannot be determined.\n");

   }

return 0;
}

// 改用floyd_warshall��法才过
#include"stdio.h"
#include"string.h"
#include"stdlib.h"
typedef struct Node{
        int d;
        char c;
}Node;
int map[26][26],used[26],flag,n;
Node node[26];

int cmp(const void *a, const void *b)
{ return (*(Node *)a).d-(*(Node *)b).d;
}

void check()
{int i,j;
for(i=0;i
     { if(used[i]==0)
           return ;
       for(j=0;j
           if(map[i][j])
             node[j].d++;
     }
   qsort(node,n,sizeof(Node),cmp);
    for(i=0;i
        if(node[i].d!=i)
           return ;
        flag=2;
}
int main()
{int row,i,j,a,b,k,h;
char s[4];
   freopen("in.txt","r",stdin);
   freopen("out.txt","w",stdout);
while(1)
  { scanf("%d%d",&n,&row);
     if(n==0 && row==0)
        break;
     flag=0;
     memset(map,0,sizeof(map));
     for(h=1;h<=row;h++)
         { scanf("%s",s);
           if(!flag)
           {a=s[0]-65;
            b=s[2]-65;
            used[a]=1;
            used[b]=1;
            for(i=0;i
                {node[i].d=0;
                 node[i].c=i+65;
                 }
         if(map[b][a]==1 || a==b)
             { printf("Inconsistency found after %d relations.\n",h);
               flag=1;
             }
          else
               map[a][b]=1;
          for(k=0;k<26;++k)
                for(i=0;i<26;++i)
                   for(j=0;j<26;++j)
                     map[i][j]=(map[i][j]||(map[i][k]&&map[k][j]));

        if(!flag)
            check();
        if(flag==2)
             {printf("Sorted sequence determined after %d relations: ",h);
                  for(i=0;i
                      printf("%c",node[i].c);
                     printf(".\n");

             }
          }
     }

   if(!flag)
      printf("Sorted sequence cannot be determined.\n");

   }

return 0;
}

蜗牛 2008-11-27 00:22 发表评论

POJ 1062 Java �Q�图论）

蜗牛 — Wed, 26 Nov 2008 16:20:00 GMT

//仿照别�h的思想敲得,之前不是很了解dijkstra�Q�做�q�这题后有些理解
//1,��当前未�U�_��最短�\的符合要求的距离最短结点纳入最短�\;
//2,��所有与当前�U�_��的结�Ҏ��兌��q�且未被�U�_��最短�\的结�Ҏ��短距��进行更新�?
//图论中另一个求最��生成树的的�l�典��法Prim��法与Dij�q�程极其�c�M��Q�都是贪心思想�?
//只是一个是寚w��点的选择�Q�另外一个是对边的选择�?

import java.util.*;
public class Main
{ public static int[][] e;
   public static int[]  dis;
   public static int[] used;
   public static int[] level;
   public static int n,m;
   public static void main(String[] args){
    Scanner cin = new Scanner(System.in);
    int  x,t;
    e = new int[101][101];
    dis = new int[101];
    used =  new int[101];
    level = new int[101];
          m=cin.nextInt();
          n=cin.nextInt();
           for(int i=1;i<=n;i++)
             {   e[0][i]=cin.nextInt();
                 level[i]=cin.nextInt();
                  x=cin.nextInt();
                for(int j=0;j
                { t=cin.nextInt();
                  e[t][i]=cin.nextInt();
                }
             }
           solve();
}

public static void solve()
{ int max,result;
  result=e[0][1];
  for(int i=1;i<=n;i++)
     { max=level[i];
       for(int j=1;j<=n;j++)
        if(level[j]>max || level[j]
         used[j]=1;//不符�?
        else
         used[j]=0; //�W�合
       dijkstra();
       if(result>dis[1]) //比较每次所求的费用
         result=dis[1];
}
System.out.println(result);
}
public static void dijkstra()
{ int min,temp,k;
  for(int i=1;i<=n;i++)
   dis[i]=e[0][i];
  for(int i=1;i<=n;i++)
     { min=0x7FFFFFFF;
       k=0;
       for(int j=1;j<=n;j++)//扑և�代�h最��的�?
         if(used[j]==0 && dis[j]
          {min=dis[j];
              k=j;
          }
       if(k==0)
        break;
       used[k]=1;
       for(int j=1;j<=n;j++)//更新其节点的�?
        if(used[j]==0 && e[k][j]>0 && min+e[k][j]
         dis[j]=min+e[k][j];
    }
   }
}

蜗牛 2008-11-27 00:20 发表评论

POJ 1125 C++ �Q�图论）

蜗牛 — Wed, 26 Nov 2008 16:19:00 GMT

//别�h五分钟能敲出来的题，我却做了五个��时�Q�差距大的吓�?wbr>
//一眼就可以看出来用folyd_warshell,我却用dijkstra�Q�调试了N�?wbr>
//首先引进一个辅助向量d[i]表示当前所扑ֈ�的从��L�� v到每个终点的最短�\径的长度.
它的初态�ؓ:若从v到vi有狐,则d[i]为弧上的�?否则d[i]为inifity.昄��?nbsp;
//一条最短�\径或者是�?s,x),或者是中间只经�q�s的顶点而最后到��N��点x的�\�?所�?wbr>
//d[x]=min{d[x],d[s]+arcs[s][x]}

#include
using namespace std;
int used[101],map[101][101],d[101],n,flag,max1,max2,v;
void solve(int i)
{ int j,k,min,v0,v1;
  for(j=1;j<=n;j++)
      {  used[j]=0;
         if(map[i][j]==0)
            d[j]=1000000000;
         else
            d[j]=map[i][j];
      }

     used[i]=1;
      while(1)
      { min=1000000000;
        v0=0;
        for(j=1;j<=n;j++)
            { if(used[j]==0 && d[j]
                 {min=d[j];
                   v0=j;
                  }
            }
       if(v0==0)
           break;
       used[v0]=1;
       for(j=1;j<=n;j++)
           {if(used[j]==0 &&  map[v0][j] && min+map[v0][j]
                d[j]=min+map[v0][j];
           }
     }

   max1=0;
  for(k=1;k<=n;k++)
       { if(k==i)
           continue;
         if(d[k]>max1)
           {max1=d[k];
            v1=i;
           }
        }

    if(max1
       {     flag=1;
             v=v1;
             max2=max1;
       }
}

int main()
{ int m,i,j,a,b;
       freopen("in.txt","r",stdin);
       freopen("out.txt","w",stdout);
   while(cin>>n,n!=0)
       {  memset(map,0,sizeof(map));

          flag=0;
          for(i=1;i<=n;i++)
              { cin>>m;
               for(j=1;j<=m;j++)
                   { cin>>a>>b;
                     map[i][a]=b;
                   }
              }
      max2=1000000000;
      v=0;
      for(i=1;i<=n;i++)
            solve(i);
      if(n==1)
          {  flag=1;
              v=1;
              max2=0;
           }
       if(flag)
          cout<
       else
          cout<<"disjoint"<

        }

    return 0;
}

蜗牛 2008-11-27 00:19 发表评论

POJ 2253 C++ �Q�图论）

蜗牛 — Wed, 26 Nov 2008 16:17:00 GMT

//前几天的题，别�h都用floyd_warshall,我就用dijkstra;
//而这个题很多人都用dijkstra,我就用floyd_warshall;
//两个字，flody的代码敲��h��是��单，但效率比较的低，复杂度是(n^3)

#include
#include
#include
using namespace std;
int main()
{ int n,Case,i,j,k;
  int x[201],y[201];
  int map[201][201];
  freopen("in.txt","r",stdin);
  freopen("out.txt","w",stdout);
  Case=1;
  while(scanf("%d",&n),n!=0)
       {    memset(map,0,sizeof(map));
            for(i=1;i<=n;i++)
              scanf("%d%d",&x[i],&y[i]);
             for( i=1;i<=n;i++)
               for( j=i+1;j<=n;j++)
                   { map[i][j]=abs((x[j]-x[i])*(x[j]-x[i])+(y[j]-y[i])*(y[j]-y[i]));
                     map[j][i]=map[i][j];
                    }
          for( k=1;k<=n;k++)
              for( i=1;i<=n;i++)
                  for( j=i+1;j<=n;j++)
                      { if(map[i][k] && map[k][j] && map[i][k]                           { if(map[i][k]>map[k][j])
                                map[i][j]=map[i][k];
                             else
                                map[i][j]=map[k][j];
                           }

                            map[j][i]=map[i][j];
                       }
        printf("Scenario #%d\n",Case++);
        printf("Frog Distance = %.3lf\n\n",sqrt(map[1][2]*1.0));
   }

   return 0;
}

蜗牛 2008-11-27 00:17 发表评论

POJ 2240 C++ �Q�图论）

蜗牛 — Wed, 26 Nov 2008 16:16:00 GMT

//今天�W�二�ơ用floyd_warshall,敲的手有点��Y
#include
#include
using namespace std;
int main()
{  int n,m,flag,Case;
   double temp,array[31][31];
   char s1[100],s2[100],str[31][100];
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    Case=1;
   while(scanf("%d",&n),n!=0)
        {  flag=0;
           memset(array,0,sizeof(array));
           for(int i=1;i<=n;i++)
               scanf("%s",str[i]);
           scanf("%d",&m);
           for(int i=1;i<=m;i++)
               {int k,j;
                scanf("%s%lf%s",s1,&temp,s2);
                for(int h=1;h<=n;h++)
                    { if(!strcmp(str[h],s1))
                          k=h;
                      if(!strcmp(str[h],s2))
                          j=h;
                    }
                     array[k][j]=temp;
               }

           for( int k=1;k<=n;k++)
              for( int i=1;i<=n;i++)
                  for(int j=1;j<=n;j++)
                      if(array[i][j]
                          array[i][j]= array[i][k]*array[k][j];

           for( int i=1;i<=n;i++)
                if(array[i][i]>1)
                   { flag=1;
                     break;
                    }

              if(flag)
                 printf("Case %d: Yes\n",Case++);
              else
                 printf("Case %d: No\n",Case++);
  }
  return 0;
}

蜗牛 2008-11-27 00:16 发表评论

POJ 1860 C++ �Q�图论）

蜗牛 — Wed, 26 Nov 2008 16:15:00 GMT

//知道了什么是bellman_ford;
//一定要坚持下去
#include
#define eps 1e-8
using namespace std;
typedef struct E{
int v,u;
double r,c;
};
int n,m,s,num;
double money,d[101];
E e[201];
bool  bellman()
{ int flag;
  memset(d,0,sizeof(d));
  d[s]=money;
  while(d[s]<=money+eps)
      { flag=0;
        for(int i=0;i
            if(d[e[i].v]+eps<(d[e[i].u]-e[i].c) * e[i].r)
              { d[e[i].v]=(d[e[i].u]-e[i].c)*e[i].r;
                flag=1;
               }

           if(!flag)
                 return d[s]>money+eps;
         }
     return true;
}

int main()
{int V,U;
double cv,rv,cu,ru;
   freopen("in.txt","r",stdin);
   freopen("out.txt","w",stdout);
  while((scanf("%d%d%d%lf",&n,&m,&s,&money))!=EOF)
     {num=0;
     for(int i=1;i<=m;i++)
          {scanf("%d%d%lf%lf%lf%lf",&U,&V,&rv,&cv,&ru,&cu);
            e[num].v=V;
            e[num].u=U;
            e[num].r=rv;
            e[num++].c=cv;
            e[num].v=U;
            e[num].u=V;
            e[num].r=ru;
            e[num++].c=cu;
           }
       if(bellman())
          printf("YES\n");
       else
          printf("NO\n");
      }

      return 0;
}

蜗牛 2008-11-27 00:15 发表评论

POJ 1789 C++ �Q�图论）

蜗牛 — Wed, 26 Nov 2008 16:13:00 GMT

//题目意思难�?
//其实��是求最��生成树�Q�用�l�典的prim��法
#include
using namespace std;
int  array[2001][2001],total;
int  used[2001],dis[2001];
char truck[2001][8];
void prim(int n)
{ int v,min;
  for(int i=1;i<=n;i++)
      {used[i]=0;
       dis[i]=array[1][i];
       }
       used[1]=1;
      while(true)
        {  min=INT_MAX;
            v=0;
            for(int i=1;i<=n;i++)
               if(!used[i] && dis[i]
                 { min=dis[i];
                   v=i;
                  }
            if(v==0)
               break;
           total=total+min;
           used[v]=1; //加入S集合
           for(int j =1;j<=n;j++)
               if(!used[j] && dis[j]>array[v][j]) //更新最��权边的�?wbr>
                   dis[j]=array[v][j];
        }
  }

int main()
{int n,sum;
      freopen("in.txt","r",stdin);
      freopen("out.txt","w",stdout);
while(scanf("%d",&n),n!=0)
      {for(int i=1;i<=n;i++)
           scanf("%s",truck[i]);
        memset(array,0,sizeof(array));
        for(int i=1;i<=n;i++)
             for(int j=1;j<=n;j++)
               { if(i==j || array[i][j])
                    continue;
                  sum=0;
                  for(int k=0;k<7;k++)
                      if(truck[i][k]!=truck[j][k])
                         sum++;
                   array[i][j]=sum;
                   array[j][i]=sum;
                }
      total=0;
      prim(n);
      printf("The highest possible quality is 1/%d.\n",total);

  }
  return 0;
}

蜗牛 2008-11-27 00:13 发表评论

POJ 1258 C++ �Q�图论）

蜗牛 — Wed, 26 Nov 2008 16:11:00 GMT

//汗，模板真的很爽
//只是�E�稍改了一下前一题的代码�Q�最��生成树问题
#include
using namespace std;
int  array[101][101],total;
int  used[101],dis[101];
void prim(int n)
{ int v,min;
  for(int i=1;i<=n;i++)
      {used[i]=0;
       dis[i]=array[1][i];
       }
       used[1]=1;
      while(true)
        {  min=INT_MAX;
            v=0;
            for(int i=1;i<=n;i++)
               if(!used[i] && dis[i]
                 { min=dis[i];
                   v=i;
                  }
            if(v==0)
               break;
           total=total+min;
           used[v]=1;
           for(int j =1;j<=n;j++)
               if(!used[j] && dis[j]>array[v][j])
                  dis[j]=array[v][j];
        }
  }

int main()
{int n,sum;
      freopen("in.txt","r",stdin);
      freopen("out.txt","w",stdout);
while((scanf("%d",&n))!=EOF)
      {for(int i=1;i<=n;i++)
           for(int j=1;j<=n;j++)
               scanf("%d",&array[i][j]);
      total=0;
      prim(n);
      printf("%d\n",total);
}

  return 0;
}

蜗牛 2008-11-27 00:11 发表评论

POJ 2485 C++ �Q�图论）

蜗牛 — Wed, 26 Nov 2008 16:09:00 GMT

//faint ,太汗了，今天上午用prim水到手��Y
#include
using namespace std;
int  array[501][501],total;
int  used[501],dis[501];
void prim(int n)
{ int v,min;
  for(int i=1;i<=n;i++)
      {used[i]=0;
       dis[i]=array[1][i];
       }
       used[1]=1;
      while(true)
        {  min=INT_MAX;
            v=0;
            for(int i=1;i<=n;i++)
               if(!used[i] && dis[i]
                 { min=dis[i];
                   v=i;
                  }
            if(v==0)
               break;
           if(min>total)
           total=min;
           used[v]=1;
           for(int j =1;j<=n;j++)
               if(!used[j] && dis[j]>array[v][j])
                  dis[j]=array[v][j];
        }
  }

int main()
{int m,n,sum;
      freopen("in.txt","r",stdin);
      freopen("out.txt","w",stdout);
      scanf("%d",&m);
     while(m--)
      { scanf("%d",&n);
        for(int i=1;i<=n;i++)
           for(int j=1;j<=n;j++)
               scanf("%d",&array[i][j]);
      total=0;
      prim(n);
      printf("%d\n",total);
}

  return 0;
}

蜗牛 2008-11-27 00:09 发表评论

POJ 3295 C++ �Q�图论）

蜗牛 — Wed, 26 Nov 2008 16:07:00 GMT

#include
using namespace std;
typedef struct Node
{ int u,v,t;
}Node;
Node e[25000];
int n,m,w,en;
bool bellmanford()
{ bool flag;
int dis[1001];
for(int i=0;i      { flag=false;
        for(int j=0;j           if(dis[e[j].v]>dis[e[j].u]+e[j].t)
               {dis[e[j].v]=dis[e[j].u]+e[j].t;
                 flag=true;
                 }
           if(!flag)
              break;
        }
    for(int i=0;i        if( dis[e[i].v]>dis[e[i].u]+e[i].t)
                return true;

    return false;
}

int main()
{int Case ,u,v,t;
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
scanf("%d",&Case);
while(Case--)
      { scanf("%d%d%d",&n,&m,&w);
        en=0;
        for(int i=1;i<=m;i++)
            { scanf("%d%d%d",&u,&v,&t);
               e[en].u=u;
               e[en].v=v;
               e[en++].t=t;
               e[en].u=v;
               e[en].v=u;
               e[en++].t=t;
             }
         for(int i=1;i<=w;i++)
            { scanf("%d%d%d",&u,&v,&t);
               e[en].u=u;
               e[en].v=v;
               e[en++].t=-t;
            }

          if(bellmanford())
             puts("YES");
         else
             puts("NO");
   }
   return 0;
}

Bellman-Ford ��法及其优化

Bellman-Ford ��法及其优化

Bellman-Ford��法与另一个非常著名的Dijkstra��法一��P��用于求解单源�Ҏ��短�\径问题�?/span>Bellman-ford��法除了可求解边权均非负的问题外�Q�还可以解决存在负权边的问题�Q�意义是什么，好好思考）�Q��?/span>Dijkstra��法只能处理�Ҏ��非负的问题，因此 Bellman-Ford��法的适用面要�q�泛一些。但是，原始�?/span>Bellman-Ford��法旉��复杂度�ؓ O�Q?/span>VE�Q?/span>,�?/span>Dijkstra��法的时间复杂度高，所以常常被众多的大学算法教�U�书所忽略�Q�就�q�经典的《算法导论》也只介�l�了基本�?/span>Bellman-Ford��法�Q�在国内常见的基本信息学奥赛教材中也均未提及�Q�因此该��法的知名度与被掌握度都不如Dijkstra��法。事实上�Q�有多种形式�?/span>Bellman-Ford��法的优化实现。这些优化实现在旉��效率上得到相当提升，例如�q�一两年被热捧的SPFA�Q?/span>Shortest-Path Faster Algoithm 更快的最短�\径算法）��法的时间效率甚至由�?/span>Dijkstra��法�Q�因此成��Z��息学奥赛选手�l�常讨论的话题。然而，限于资料匮乏�Q�有�?/span>Bellman-Ford��法的诸多问题常常困扰奥赛选手。如�Q�该��法值得掌握么？怎样用编�E�语�a�具体实现�Q�有哪些优化�Q�与SPFA��法有关�p�M��Q�本文试囑֯�Bellman-Ford��法做一个比较全面的介绍。给出几�U�实现程序，从理论和实测两方面分析他们的旉��复杂度，供大家在备战省选和后箋�?/span>noi时参考�?/span>

Bellman-Ford��法思想

Bellman-Ford��法能在更普遍的情况下（存在负权边）解决单源�Ҏ��短�\径问题。对于给定的带权�Q�有向或无向�Q�图 G=�Q?/span>V,E�Q�，其源点�ؓs�Q�加权函�?/span> w�?/span> 辚w�� E 的映��。对�?/span>G�q�行Bellman-Ford��法的结果是一个布��|��表明图中是否存在着一个从源点s可达的负权回路�?/span>若不存在�q�样的回路，��法��给��Z��源点s�?/span> �?/span>G的�Q意顶�?/span>v的最短�\�?/span>d[v]�?/span>

Bellman-Ford��法��程分�ؓ三个阶段�Q?/span>

�Q?�Q?span style="FONT: 7pt Times New Roman"> 初始化：��除源点外的所有顶点的最短距��M��计�?/span> d[v] ←+∞, d[s] ←0;

�Q?�Q?span style="FONT: 7pt Times New Roman"> �q�代求解�Q�反复对辚w��E中的每条边进行松弛操作，使得��点集V中的每个��点v的最短距��M��计值逐步��D��其最短距��；�Q�运行|v|-1�ơ）

�Q?�Q?span style="FONT: 7pt Times New Roman"> ��验负权回路：判断辚w��E中的每一条边的两个端�Ҏ��否收敛。如果存在未收敛的顶点，则算法返�?/span>false�Q�表明问题无解；否则��法�q�回true�Q��ƈ且从源点可达的顶�?/span>v的最短距��M��存在 d[v]中�?/span>

��法描述如下�Q?/span>

Bellman-Ford(G,w,s) �Q?/span>boolean //�?/span>G �Q�边�?/span> 函数 w �Q?/span>s为源�?/span>

1 for each vertex v ∈ V�Q�G�Q?do //初始�?span style="mso-spacerun: yes"> 1阶段

2 d[v] ←+∞

3 d[s] ←0; //1阶段�l�束

4 for i=1 to |v|-1 do //2阶段开始，双重循环�?/span>

5 for each edge�Q�u,v�Q?∈E(G) do //辚w��数组要用刎ͼ��I��D每条辏V�?/span>

6 If d[v]> d[u]+ w(u,v) then //村ּ�判断

7 d[v]=d[u]+w(u,v) //村ּ�操作 2阶段�l�束

8 for each edge�Q�u,v�Q?∈E(G) do

9 If d[v]> d[u]+ w(u,v) then

10 Exit false

11 Exit true

下面�l�出描述性证明：

首先指出�Q�图的�Q意一条最短�\径既不能包含负权回�\�Q�也不会包含正权回�\�Q�因此它最多包�?/span>|v|-1条边�?/span>

其次�Q�从源点s可达的所有顶点如�?/span> 存在最短�\径，则这些最短�\径构成一个以s为根的最短�\径树�?/span>Bellman-Ford��法的�P代松弛操作，实际上就是按��点距离s的层�ơ，逐层生成�q�棵最短�\径树的过�E��?/span>

在对每条边进�?span>1遍松弛的时候，生成了从s出发�Q�层�ơ至多�ؓ1的那些树枝。也��是��_��扑ֈ�了与s臛_��?条边相联的那些顶点的最短�\径；�Ҏ��条边�q�行�W?遍松弛的时候，生成了第2层次的树枝，��是说找��C��l�过2条边相连的那些顶点的最短�\�?#8230;…。因为最短�\径最多只包含|v|-1 条边�Q�所以，只需要��@环|v|-1 �ơ�?/span>

每实施一�ơ松弛操作，最短�\径树上就会有一层顶点达到其最短距��，此后�q�层��点的最短距��d��就会一直保持不变，不再受后�l�松弛操作的影响。（但是�Q�每�ơ还要判断松弛，�q�里��费了大量的旉��Q�怎么优化�Q�单�U�的优化是否可行�Q�）

如果没有负权回�\�Q�由于最短�\径树的高度最多只能是|v|-1�Q�所以最多经�q�|v|-1遍松弛操作后�Q�所有从s可达的顶点必��求出最短距��R��如�?d[v]仍保�?+∞�Q�则表明从s到v不可达�?/span>

如果有负权回路，那么�W?span> |v|-1 遍松弛操作仍然会成功�Q�这�Ӟ��负权回�\上的��点不会收敛�?/span>

例如对于上图�Q�边上方框中的数字代表权��|��点A,B,C之间存在负权回�\。S是源点，��点中数字表�C��行Bellman-Ford��法后各点的最短距��M��计倹{�?/span>

此时d[a]的��gؓ1�Q�大于d[c]+w(c,a)的�?2�Q�由此d[a]可以村ּ��?2�Q�然后d[b]又可以松弛�ؓ-5,d[c]又可以松弛�ؓ-7.下一个周期，d[a]又可以更��Cؓ更小的��|��q�个�q�程永远不会�l�止。因此，在�P代求解最短�\径阶�D늻�束后�Q�可以通过��验边集E的每条边(u,v)是否满��关系�?span style="mso-spacerun: yes"> d[v]> d[u]+ w(u,v) 来判断是否存在负权回路�?br>

二、基�?/span> Bellman-Ford ��法�?/span> pascal实现�?/span>

�?/span> bellmanford.pas 文�g�?/span>

三、基本算法之上的优化�?/span>

分析 Bellman-Ford��法�Q�不隄��出，外层循环�Q��P代次敎ͼ�|v|-1实际上取得是上限。由上面对算法正��性的证明可知�Q�需要的�q�代遍数�{�于最短�\径树的高度。如果不存在负权回�\�Q��^均情况下的最短�\径树的高度应该远�q�小�?/span> |v|-1�Q�在此情况下�Q�多余最短�\径树高的�q�代遍数��是旉��上的��费�Q�由此，可以依次来实施优化�?/span>

从细节上分析�Q�如果在某一遍�P代中�Q�算法描�q�C��W?/span>7行的村ּ�操作未执行，说明该遍�q�代所有的辚w��没有被松弛。可以证明（怎么证明�Q�）�Q�至此后�Q�边集中所有的辚w��不需要再被松弛，从而可以提前结束�P代过�E�。这��P��优化的措施就非常��单了�?/span>

讑֮�一个布��型标志变量 relaxed�Q�初��gؓfalse。在内层循环中，仅当有边被成功松弛时�Q�将 relaxed 讄��?/span>true。如果没有边被松弛，则提前结束外层��@环。这一改进可以极大的减��外层��@环的�q�代�ơ数。优化后�?/span> bellman-ford函数如下�?/span>

function bellmanford(s:longint):boolean;

begin

for i:=1 to nv do

d[i]:=max;

d[s]:=0;

for i:=1 to nv-1 do

begin

relaxed:=false;

for j:=1 TO ne do

if(d[edges[j].s]<>max) and (d[edges[j].e]>d[edges[j].s]+edges[j].w)

then begin

d[edges[j].e]:=d[edges[j].s]+edges[j].w ;

relaxed:=true;

end;

if not relaxed then break;

end;

for i:=1 to ne do

if d[edges[j].e]>d[edges[j].s]+edges[j].w then exit(false);

exit(true);

end;

�q�样看似�q�_��的优化，会有怎样的效果呢�Q�有研究表明�Q�对于随机生成数据的�q�_��情况�Q�时间复杂度的估��公式�ؓ

1.13|E| if |E|<|V|

0.95*|E|*lg|V| if |E|>|V|

优化后的��法在处理有负权回�\的测试数据时�Q�由于每�ơ都会有边被村ּ��Q�所�?/span>relaxed每次都会被置�?/span>true�Q�因而不可能提前�l�止外层循环。这对应了最坏情况，其时间复杂度仍旧�?/span>O(VE)�?/span>

优化后的��法的时间复杂度已经和用二叉堆优化的Dijkstra��法相近了，而编码的复杂�E�度�q�比后者低。加�?/span>Bellman-Ford��法能处理各�U�边值权情况下的最短�\径问题，因而还是非�怼��U�的�?/span>Usaco3.2.6 的程序见bellmanford_1.pas

四�?/span>SPFA ��法

SPFA是目前相当优�U�的求最短�\径的��法�Q�值得我们掌握�?/span>

SPFA�?/span>Bellman-Ford��法优化的关键之处在于意识到�Q?span style="COLOR: #ff6600">只有那些在前一遍松弛中改变了距��M��计值的点，才可能引起他们的��L��点的距离估计值的改变�?/span>因此�Q�用一个先�q�先出的队列来存放被成功村ּ�的顶炏V��初始时�Q�源�?/span>s入队。当队列不�ؓ�I�时�Q�取出对首顶点，对它的邻接点�q�行村ּ�。如果某个邻接点村ּ�成功�Q�且该邻接点不在队列中，则将其入队。经�q�有限次的松弛操作后�Q�队列将为空�Q�算法结束�?/span>SPFA��法的实玎ͼ�需要用��C��个先�q�先出的队列 queue 和一个指�C�顶�Ҏ��否在队列中的标记数组 mark。�ؓ了方便查找某个顶点的��L��点，��N��用��界表存储�?/span>

�E�序存储�?/span> spfa.pas中。以usaco 3.2.6 试题2��Z��。用��L��表写的程序�?/span>

需要注意的是：仅当图不存在负权回�\�Ӟ��SPFA能正常工作。如果图存在负权回�\�Q�由于负权回路上的顶�Ҏ��法收敛，��L��点在入队和出队往�q�，队列无法为空�Q�这�U�情况下SPFA无法正常�l�束�?/span>

关于SPFA的时间复杂度�Q�不好准��估计，一般认为是 O�Q?/span>kE�Q�，k是常�?/span>

五、时间效率实��?/span>

上述介绍�?/span>Bellman-Ford��法及两�U�的优化�Q�只是在理论上分析了旉��复杂度，用实际的数据��试�Q�会有什么结果呢�Q��ؓ此，我们选择 usaco 3.2.6�?/span>

Spfa的时间效率还是很高的。�ƈ�?/span>spfa的编�E�复杂度要比Dijksta+heap优化要好的多�?/span>

六、结�?/span>

�l�过优化Bellman-Ford��法是非�怼�化的求单源最短�\径的��法�Q?/span>SPFA旉��效率要优于第一�U�优化�Ş式，但第一�U�优化�Ş式的�~�码复杂度低�?/span>SPFA。两�U�优化�Ş式的�~�程复杂度都低于Dijkstra��法。如果在判断是否存在负权回�\�Q�推荐��用第一�U�优化�Ş式，否则推荐使用SPFA�?/span>

蜗牛 2008-11-27 00:07 发表评论

蜗牛 — Tue, 25 Nov 2008 17:13:00 GMT

#include
using namespace std;
int n,next[1000008];
char s[1000008];
void Get_next()
{int j,k;
j=1;
k=0;
next[1]=0;
while(j<=n+1)
       { if(k==0 || s[j]==s[k])
            { j++;
              k++;
              next[j]=k;
             }
          else
             k=next[k];
         }
}
int main()
{ int i,cnt,k;
   freopen("in.txt","r",stdin);
   freopen("out.txt","w",stdout);
   k=1;
  while(scanf("%d\n",&n),n!=0)
         { for(i=1;i<=n;i++)
                s[i]=getchar();
           s[i]='#';
           Get_next();
           printf("Test case #%d\n",k++);
           for(i=2;i<=n;i++)
                if(i%(i+1-next[i+1])==0)
                    { cnt=i/(i+1-next[i+1]);
                      if(cnt!=1)
                      printf("%d %d\n",i,cnt);
                     }

        printf("\n");
     }
   return 0;
}

该题的题意是�q�样的，�l�若�q�个字符�Ԍ��判断该字�W�串的前n位最多重复了几次�Q�比如，�l�ababab�Q�结果是�?位重复了2�ơ，�?位重复了3�ơ，忽略重复一�ơ的情况.现在我们��注意力攑֜�一个给定的字符串重复了多少�ơ，然后做一个��@环就可以求出所有的�l�果�?wbr>
我们要根据kmp��法中的next函数来解册��个问题，以ababab��Z��加以说明�Q?wbr>
String�Q�ababab
Next�Q?0112345
�q�里�Ҏ��后面的需要多计算了一位next倹{�?wbr>
我们用ababab即作��Z��串有作�ؓ模式串来�q�行匚w��Q�假讑֌�配到�W?为时不匹配了(下标�?开�?�Q�要�Ҏ��next[7](=5)的值��l�匹配：
ababab*
ababab&
ababab*
ababab
�q�样�Q�我们用�Q�length+1�Q?next[length+1]��是字符串向右移动的位数�Q�在该例中�ؓ7-5=2.然后用�ȝ��长度除以�q�个向右�U�d��的位敎ͼ�如果能除��的话，�l�果��是重复的次敎ͼ�否则重复的次��Cؓ1

蜗牛 2008-11-26 01:13 发表评论

蜗牛 — Tue, 25 Nov 2008 17:08:00 GMT

#include
#include
using namespace std;
int n,next[400008],result[400008];;
char s[400008],t[400008];
void Get_next()
{int j,k;
j=1;
k=0;
next[1]=0;
while(j<=n+1)
       { if(k==0 || s[j]==s[k])
            { j++;
              k++;
              next[j]=k;
             }
          else
             k=next[k];
         }
}
int main()
{ int i,k;
   freopen("in.txt","r",stdin);
   freopen("out.txt","w",stdout);
   while(scanf("%s",t)!=EOF)
         {n=strlen(t);
          for(i=1;i<=n;i++)
                s[i]=t[i-1];

           s[i]='#';
           Get_next();
           k=0;
           result[k++]=n+1;
           i=n+1;
           while(i!=1)
                { if(next[i]!=1)
                     result[k++]=next[i];
                  i=next[i];
                 }

          for(i=k-1;i>0;i--)
              printf("%d ",result[i]-1);

         printf("%d\n",result[i]-1);
     }

   return 0;
}

蜗牛 2008-11-26 01:08 发表评论

POJ 1694 C++ �Q�排序）

蜗牛 — Tue, 25 Nov 2008 17:01:00 GMT

//不会�Ԍ��是偶看过别�h的结题报告后敲的�Q�学习下
#include
#include
using namespace std;
typedef struct Node
{ int label;
   int cnt;
   int leaf[200];
};
Node tree[200];
int solve(int i)
{   int  stone[200],result,temp;
    if(tree[i].cnt==0)
       return 1;
     for(int j=0;j
         stone[j]=solve(tree[i].leaf[j]);

     sort(stone,stone+tree[i].cnt);
     result=stone[tree[i].cnt-1];
     temp=result-1;
     for(int k=tree[i].cnt-2;k>=0;k--)
        { if(temp-stone[k]>=0)
             temp--;
           else
             {result=result+stone[k]-temp;
              temp=stone[k]-1;
              }
         }

       return result;
}
int main()
{ int n,m;
  freopen("in.txt","r",stdin);
  freopen("out.txt","w",stdout);
  scanf("%d",&n);
  while(n--)
       { scanf("%d",&m);
         for(int i=1;i<=m;i++)
             {  scanf("%d%d",&tree[i].label,&tree[i].cnt);
                for(int j=0;j
                   scanf("%d",&tree[i].leaf[j]);
              }
         printf("%d\n",solve(1));
       }

   return 0;
}

蜗牛 2008-11-26 01:01 发表评论

亚洲一区二区欧美,国产精品h在线观看,欧美精品一区二

关于

POJ 1083 C++ �Q�水题）

POJ 3041 C++ �Q�图论）

POJ 1496 C++ �Q�图论）

POJ 3020 C++ �Q�图论）

POJ 1087 C++ �Q�图论）

POJ 1459 C++ �Q�图论）

POJ 1094 C++ �Q�图论）

POJ 1062 Java �Q�图论）

POJ 1125 C++ �Q�图论）

POJ 2253 C++ �Q�图论）

POJ 2240 C++ �Q�图论）

POJ 1860 C++ �Q�图论）

POJ 1789 C++ �Q�图论）

POJ 1258 C++ �Q�图论）

POJ 2485 C++ �Q�图论）

POJ 3295 C++ �Q�图论）

Bellman-Ford���法思想

Bellman-Ford���法���程分�ؓ三个阶段�Q?/span>

二、基�?/span> Bellman-Ford ���法�?/span> pascal实现�?/span>

三、基本算法之上的优化�?/span>

五、时间效率实��?/span>

六、结�?/span>

POJ 1694 C++ �Q�排序）

Bellman-Ford��法思想

Bellman-Ford��法��程分�ؓ三个阶段�Q?/span>

二、基�?/span> Bellman-Ford ��法�?/span> pascal实现�?/span>