• 终于走到最后一个部分了。先回顾下自己在图论部分学习到的知识点,然后将最后4道题目做完。
  • 一位校友的文章,提到了大名鼎鼎的johnbill,bennie[后者虽然不知道是谁,但非常佩服],真的很佩服他们,赞!编程真是拿耐力,智力和精力来换的工作.虽然很弱,但我不会放弃自己的努力,无论在何时何地,也不会给自己任何的借口."往者不可谏,来者犹可追"!
  • 图论和搜索以及前面的算法思想比较,知识点要系统一些:
1,图的连通性问题:H路,E路,以及相应的回路,连通图的割顶和桥,平面图的基本性质。[这个部分我感觉最头痛,变化比较大,而且思路不容易转化为代码,根本上说还是自己代码熟练和思维的问题,不能将一些算法转化为代码,并且快速实现。当然,这要靠勤奋和扎实的工作训练,更多的是战胜自己在编码中的畏难心理。]
2,图的生成树模型:Prim和Krushkal算法,以及动态树[这个要注意,不过暂时先放下],比较变态的最小度生成树和最优比率生成树[后者的思路不错,可以借鉴,前者有一个动规的思路在里面,可以在以后再强化]
3,图的最短路模型:无负流的贪心模型dijkstra算法,以及bellman-ford和ford-warshal算法,主要是个动规思路。在此基础上衍生的差分约束系统问题,以及广义的标号修正算法,多元标号修正算法。[动规是核心]
4,网络流模型问题:Dicnic算法和最高预流算法[FIFO,注意循环队列的使用],最大流最小割应用,以及最小费用最大流算法[连续最短路,消圈算法]。
5,二分图模型问题:匈牙利算法[DFS和HK算法实现],最大匹配和最小覆盖的一致性定理,带权顶标修正的KM算法。
后面两者主要是建模问题,自己在有的时候建模思路还是不是很清晰,而且在一些细节问题上容易粗心[比如边数估算,最大流忘记*2,二分匹配忘记算特殊点]。剩下的基本都是编码中的问题,和思路其实还没有很大关系。
犯的最大的错误,是在预流推进时把算法框架写错了,使得有些顶点的预流没有为零,又没有加assert,结果搞得天昏地转。自己比较高兴得是,在做一个题目时,用了一个动态的调整方法。
 
最大的收获是养成了一个估算的习惯,代码腹稿的功力还要加强,这对提高代码速度是很关键的,深有体会。这也是要自己以后工作中也要在时间许可的情况下,多训练自己的这种能力。Jon说的很对,好的程序员在动笔之前要留给自己一个适当的思考时间,在完成之后也要留给自己一个回顾的时间,看是否以自己最明白的方式实现。可惜我还不能做到好的程序员那种水平,向着这个方向努力总是对的。SAP开发的过程中,曾经遇到过SDO的一个转化问题,当时就是思路单一了,当然Andy提醒了我,吓得我一身冷汗,因为那个设计不能通过的话,整个代码就要完全重写,幸好有德国SDO开发组的支持,不然真的就玩完料。
 
具体要求:对于任何一段代码[常识性代码除外],模块功能较多[3-4以上],特别牵涉算法和自己的点子时候
  • 要先将思路在纸上整理出来,形成一个基本流程。
  • 对于细节的设计,加上标注,多问自己几个怎么样:有几种实现方式,各自的优劣,编程细节的比较[模块之间变量是否耦合过大,等等]。
  • 花5-8分钟回顾,看是否能有完整的腹稿,随后再动笔[总的时间看功能要求,但思考的时间不宜少于20%]。
  • 在正规开发中,注意在函数上标称算法的实用范围,默认参数以及参数验证,在永真式多使用断言。
废话多了!还是踏踏实实地努力是正道。还有最重要的,不要在不适当的地方钻牛角尖,尤其在实际工作中。
  • 图论的综合题
算法分析:首先任何的有效列线和行线均存在一个交点k,最多的卫士对应于交点最多。如果把列看作X集,行看作Y集,那么一个匹配就对应一个k点。最多的卫士就是最大匹配数。问题划分为如何求列线段和行线段,可以分别按行和列扫描一次(O(nm)),同时对X集和Y集予以计数即可(只是要注意ctid和rtid的计数时要做到连续增长),同时记录每个X集和Y集点的长度[这个我想多了,可以直接删掉的];然后再进行一次扫描,每个合法的guards安放点必然具备一个行号和另一个列号,构二分图将此点的坐标记录到es[eid].inter中,再进行HK算法进行二分。书上说要求连通块求解,其实不用,这样已经可以搞定了。
 
代码实现如下:
#include <iostream>
#include <fstream>
using namespace std;
const int MAXN=40000, MAXE=40000;
typedef struct Edge{
    int i, j, next, inter;
}Edge;
Edge es[MAXE];
int eid, cid[MAXN], rid[MAXN], first[MAXE], distX[MAXE], distY[MAXE], linkX[MAXE], linkY[MAXE];
int m, n, tsize, ctid, rtid, maxc, maxr, lenc[MAXN], lenr[MAXN], queue[MAXN], matchX[MAXE];
char map[MAXN];
//declaration
void clr();
void addEdge(int i, int j, int intersect);
int HK();
bool HK_dfs(int v);
bool HK_bfs();
//implementation
void clr(){
    eid=0, ctid=0, rtid=0, maxc=-1, maxr=-1;
    memset((void*)first, 0xff, sizeof(first)),
    memset((void*)cid, 0xff, sizeof(cid)),
    memset((void*)rid, 0xff, sizeof(rid)),
    memset((void*)lenc, 0, sizeof(lenc)),
    memset((void*)lenr, 0, sizeof(lenr));
}
void addEdge(int i, int j, int intersect){
    es[eid].i=i, es[eid].j=j, es[eid].inter=intersect;
    es[eid].next=first[i], first[i]=eid; eid++;
}
//HK algorithm for bio-partite
int HK(){
    memset((void*)linkX, 0xff, sizeof(linkX)),
    memset((void*)linkY, 0xff, sizeof(linkY));
    int res(0);
    while(HK_bfs()){
        for(int i=0; i<maxr+1; i++){
            if(linkX[i]==-1&&HK_dfs(i)) res++;
        }
    }
    return res;
}
bool HK_bfs(){
    int top=0, size=0; bool found=false;
    for(int i=0; i<maxr+1; i++){
        if(linkX[i]==-1) queue[size++]=i;
        distX[i]=0;
    }
    memset((void*)distY, 0, sizeof(distY));
    for(;top<size;top++){
        int v=queue[top];
        for(int ed=first[v]; ed!=-1; ed=es[ed].next){
            if(!distY[es[ed].j]){
                distY[es[ed].j]=distX[v]+1;
                if(linkY[es[ed].j]==-1) found=true;
                else distX[linkY[es[ed].j]]=distY[es[ed].j]+1, queue[size++]=linkY[es[ed].j];
            }
        }
    }
    return found;
}
bool HK_dfs(int v){
    for(int ed=first[v]; ed!=-1; ed=es[ed].next){
        if(distY[es[ed].j]==distX[v]+1){
            distY[es[ed].j]=0;
            if(linkY[es[ed].j]==-1||HK_dfs(linkY[es[ed].j])){
                linkX[v]=es[ed].j, linkY[es[ed].j]=v; matchX[v]=ed; return true;
            }
        }
    }
    return false;
}
#define fbase
int main()
{
#ifdef fbase
    ifstream in("input.txt");
    if(!in) return EXIT_FAILURE;
    cin.rdbuf(in.rdbuf());
#endif
    //implementation
    cin>>m>>n, tsize=m*n, clr();
    int tmp;
    for(int i=0; i<tsize; i++) cin>>tmp, map[i]=tmp;
    bool used=false;//if the tag has been used, to ensure the continual tag.
    //scan for row
    for(int i=0; i<tsize; i++){
        if(map[i]==2||(i>=n&&i%n==0))
            if(i!=0&&used) rtid++, used=false;
        if(map[i]!=2){
            rid[i]=rtid, used=true, lenr[rtid]++;
            if(maxr<rtid) maxr=rtid;
        }
    }
    //scan for column
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            int xy=i+j*n;
            if(map[xy]==2||(i>0&&j==0))
                if(xy!=0&&used) ctid++, used=false;
            if(map[xy]!=2){
                cid[xy]=ctid, used=true, lenc[ctid]++;
                if(maxc<ctid) maxc=ctid;
            }
        }
    }
    //X set is 0…maxr, Y set is 0…maxcm, non-sysmetric bio-partite.
    //construct bio-partite.
    for(int i=0; i<tsize; i++){
        if(rid[i]!=-1&&cid[i]!=-1){
            if(lenr[rid[i]]>0&&lenc[cid[i]]>0&&map[i]==0){//for row and column
                addEdge(rid[i], cid[i], i);
            }
        }
    }
    cout<<HK()<<endl;
    for(int i=0; i<maxr+1; i++){
        if(linkX[i]!=-1){
            int x=es[matchX[i]].inter/n, y=es[matchX[i]].inter%n;
            cout<<x+1<<" "<<y+1<<endl;
        }
    }
#ifdef fbase
    in.close();
#endif
    return 0;
}
#undef fbase
PS:下午看了下默认程序关联的注册表项,以及ErrorProvider的WPF实现。可以做个东西,把这里搞定之后。
这是一道难题,能提炼出来模型很不容易,因为设计的太隐晦了。看了书上的解答,LRJ是这样分析的:对于每一个内存区域j,有k个程序其运行时间分别为t1, t2, t3…tk,那么所有程序的回滚时间为k*t1+(k-1)*t2+(k-2)t3+…+tk,这样对于每个程序k而言,可以唯一的对应常数p=k[在序列中的倒数序号],将所有的这样回滚时间加和起来,就可以得到所有程序的回滚时间,也就很容易得到其平均值
建模而言,可以将n个程序作为X集,将(j,p)视为j个内存区域里面的倒数p个序列以此作为Y集,这样建立了一个二分模型,求得答案就是二分的最小权匹配。KM算法翻个负号即可。还有一点实现上的问题:我们要求得t[i,j]即i程序在内存j中的消耗时间,这是一个典型的二分查找代码,只是要注意题目上说的是每个程序的内存不会大于最大的内存块。在代码二分的时候,可以将l,r都不满足的情况下,把时间赋值为INT_MAX,当然根据题目的描述,这是一个dummy impelementation.
最后要注意的是ACM/ICPC live archive的库是Maco条件下的,所以在iostream里面没有引用INT_MAX,INT_MIN,以及memory.h头文件,需要自己显式加入和定义。白白遭了4个Compliation Error.
下面附代码和运行时间:[PS这道题目确实难,尤其在决赛环境下,很佩服那些神人]
6 3.193 844 orlando22 C++ 2009-05-15 03:27:19 408522   (H1)
#include <stdio.h>
#include <memory.h>
#include <iostream>
//world final 2238 – Fixed Partition Memory Management
using namespace std;
const int MAXM=10, MAXN=50, MAXX=50, MAXY=500, MAXE=25000, MAXK=11,KMAX=(1<<30)-1,KMIN=-(1<<30);
//data structure
typedef struct Edge{
 int i, j, next, w;
}Edge;
typedef struct SK{
 int s, t;
}SK;
Edge es[MAXE];
int ssize[MAXM],seg[MAXN], t[MAXN][MAXM], st[MAXN];
SK segt[MAXN][MAXK];
int eid, yid, m, n, k, firstX[MAXX], linkX[MAXX], linkY[MAXY], mX[MAXX],lx[MAXX], ry[MAXY], kmax=(1<<30)-1;
int tid[MAXN];
bool lix[MAXX], riy[MAXY];
void clr();
void addEdge(int i, int j, int w);
int KM();
bool find(int v);
void adjust();
void clr(){
 eid=0, yid=0, memset((void*)firstX, 0xff, sizeof(firstX));
}
void addEdge(int i, int j, int w){
 es[eid].i=i, es[eid].j=j, es[eid].w=w;
 es[eid].next=firstX[i], firstX[i]=eid; eid++;
}
int KM(){
 memset((void*)linkX, 0xff, sizeof(linkX)),
  memset((void*)linkY, 0xff, sizeof(linkY));
 int maxx;
 for(int i=0; i<n; i++){
  maxx=KMIN;
  for(int ed=firstX[i]; ed!=-1; ed=es[ed].next){
   if(es[ed].w>maxx) maxx=es[ed].w;
  }
  lx[i]=maxx;
 }
 memset((void*)ry, 0, sizeof(ry));
 for(int i=0; i<n; i++){
  memset((void*)lix, 0, sizeof(lix)), memset((void*)riy, 0, sizeof(riy));
  while(!find(i)){
   adjust();
   memset((void*)lix, 0, sizeof(lix)), memset((void*)riy, 0, sizeof(riy));
  }
 }
 int tw=0;
 for(int i=0; i<n; i++){
  tw+=es[mX[i]].w;
 }
 return tw;
}
bool find(int v){
 lix[v]=true;
 for(int ed=firstX[v]; ed!=-1; ed=es[ed].next){
  if(!riy[es[ed].j]&&lx[v]+ry[es[ed].j]==es[ed].w){
   riy[es[ed].j]=true;
   if(linkY[es[ed].j]==-1||find(linkY[es[ed].j])){
    linkX[v]=es[ed].j, linkY[es[ed].j]=v, mX[v]=ed; return true;
   }
  }
 }
 return false;
}
void adjust(){
 int minx=kmax;
 for(int i=0; i<n; i++){
  if(lix[i]){
   for(int ed=firstX[i]; ed!=-1; ed=es[ed].next){
    if(!riy[es[ed].j]){
     if(minx>lx[i]+ry[es[ed].j]-es[ed].w) minx=lx[i]+ry[es[ed].j]-es[ed].w;
    }
   }
  }
 }
 for(int i=0; i<n; i++){
  if(lix[i]) lx[i]-=minx;
 }
 for(int i=0; i<yid; i++){
  if(riy[i]) ry[i]+=minx;
 }
}
int main()
{
 int ncase=1;
 while(cin>>m>>n&&m&&n){
  for(int i=0; i<m; i++) cin>>ssize[i];
  for(int i=0; i<n; i++){
   cin>>k;
   for(int j=0; j<k; j++) cin>>segt[i][j].s>>segt[i][j].t;
   seg[i]=k-1;
  }
  int l, r, mid;
  for(int i=0; i<n; i++){//一个二分查找算法
   for(int j=0; j<m; j++){
    l=0, r=seg[i];
    while(l+1<r){
     mid=l+(r-l)/2;
     if(ssize[j]<segt[i][mid].s) r=mid;
     else l=mid;
    }
    if(segt[i][r].s<=ssize[j]) t[i][j]=segt[i][r].t;
    else{
     if(segt[i][l].s<=ssize[j]) t[i][j]=segt[i][l].t;
     else t[i][j]=KMAX/MAXN;
    }
   }
  }
  clr();
  for(int i=0; i<n; i++){
   for(int j=0; j<m; j++){
    for(int p=0; p<n; p++){
     int y=j+p*m;
     addEdge(i, y, -t[i][j]*(p+1));
    }
   }
  }
  yid=n*m;
  int minT=-KM(), time;//最小权匹配问题
  for(int i=0; i<m; i++){//下面的代码只能说实现,不能说很好,对于每一个i内存区,保留一个tid的数组来存正向的数据。
   memset((void*)tid, 0xff, sizeof(tid));
   int tot=0;
   for(int j=0; j<n; j++){
    if(linkX[j]!=-1&&linkX[j]%m==i) tot++;
   }
   for(int j=0; j<n; j++){
    if(linkX[j]!=-1&&linkX[j]%m==i) tid[tot-1-linkX[j]/m]=j;//倒序转正序
   }
   time=0;
   for(int j=0; j<n; j++){
    if(tid[j]==-1) break;
    st[tid[j]]=time, time+=t[tid[j]][i];
   }
  }
  printf("Case %d\n", ncase), ncase++;
  printf("Average turnaround time = %.2f\n", (double)minT/(double)n);
  for(int i=0; i<n; i++){
   printf("Program %d runs in region %d from %d to %d\n",
    i+1, linkX[i]%m+1, st[i], st[i]+t[i][linkX[i]%m]);
  }
  printf("\n");
 }
 return 0;
}
 
一道难题,贡献了5个WA,2个RE,卡住了。先写下思路,附当前的代码实现和运行时间,跳到下道题目,等有思路了,再回来搞定吧。
转化一下:Golden Solider是不用考虑的,因为他无论如何是一定能到一个目的地的。假设2K个red,green中有p中可以到达目的地,而剩下的2K-p无法移动,则肯定要对2K-p进行转化,也就是对换。假设2K-P为偶数,那么等价于一对red,green兵类型互换;若为奇数,则可以看作剩下的那个落单的兵和一个到达目的地的兵类型互换。所以模型转化为:red/green走到无法移动时,可以回到上一次使用魔法时的可达位置,再进行扩展。在实现时,可以由每一个兵从当前位置出发达到所有可达点,假设这些可达点的四周还有未踏点[必然是一次魔法之后,四周的点就可以被踏完,因为位置高度要么高,要么低,只有两种情况],则以此为下一次出发点用一次魔法,再扩展直到所有目标点均在达到。设w[j][i]为序号为i的兵到达序号j的目标点所需最少魔法数,那么直接用一个BFS扩展即可求出
然后就是一个限制度的二分最大匹配了,X集是兵集合,Y集是目标点,为了达到限制度的目的,将重要性为r的一个目标点,分为r个点[可以仿照前向星来求],这样最多只有r个兵能和目标点匹配上,假设最大匹配为p’,则p’>=2K-P即可。[gold可以用p次来将2k个兵转化到目的地,使用p次魔法后,若有匹配则剩下兵可达]
 
7131863 10418 Hyper Toy Soldiers Wrong answer C++ 0.144 2009-05-16 12:01:46
 
当前郁闷的状态WA,百思不得其解:[估计只过了几个测试用例]
#include <iostream>
#include <fstream>
using namespace std;
const int MAXT=101, MAXM=100, MAXN=100, MAXMAP=10000, MINK=-(1<<30);
enum Stype{red=1, green=-1};//red : low to high, green : high to low.
typedef struct Sloc{
 int x, y; Stype type;
}Sloc;
typedef struct Node{
 int x, y;
}Node;
Sloc ssc[MAXT]; Node tsq[MAXT];
char map[MAXM][MAXN];//height of each location
int m, n, vk, t, w[MAXT][MAXT], tid[MAXM][MAXN];
Node stack1[MAXMAP];//for path for no-expanded nodes.
int d[MAXM][MAXN];//dis DP table
int dx[4]={-1,0,1,0}, dy[4]={0,1,0,-1}, rid[MAXT+4];
int* reid=rid+1;
//bio-partite graph logic
const int MAXX=101, MAXY=11000, MAXE=1100000;
typedef struct Edge{
 int i, j, w, next;
}Edge;
Edge es[MAXE];
int eid, xid, yid, firstX[MAXX], distX[MAXX], distY[MAXY], linkX[MAXX], linkY[MAXY], queue[MAXX];
//declaration
void calw();
void addEdge(int i, int j, int w);
int HK(const int& w);
bool HK_bfs(const int& w);
bool HK_dfs(int v);
//implementation, refer to A* algorithm
void calw(){
 memset((void*)w, 0xff, sizeof(w));
 Node vn, cs; Stype ctype;
 int magic, ttid, stop, ssize, validstart, left;
 for(int i=0; i<2*vk; i++){
  memset((void*)d, 0xff, sizeof(d));
  ctype=ssc[i].type; magic=0, ttid=0, ssize=0, validstart=0;
  if(tid[ssc[i].x][ssc[i].y]!=-1&&w[tid[ssc[i].x][ssc[i].y]][i]==-1) w[tid[ssc[i].x][ssc[i].y]][i]=0, ttid++;
  d[ssc[i].x][ssc[i].y]=0;//DP level
  stack1[ssize].x=ssc[i].x, stack1[ssize++].y=ssc[i].y;
  while(ttid<t){
   stop=validstart;//back to the previous valid top.
   while(stop<ssize&&ttid<t){//for current BFS
    vn=stack1[stop++]; left=0;
    for(int j=0; j<4&&ttid<t; j++){
     int x1=vn.x+dx[j], y1=vn.y+dy[j];
     if(x1>-1&&x1<m&&y1>-1&&y1<n&&d[x1][y1]==-1){
      if(ctype==red&&map[x1][y1]>=map[vn.x][vn.y]||(ctype==green&&map[x1][y1]<=map[vn.x][vn.y])){
       if(tid[x1][y1]!=-1&&w[tid[x1][y1]][i]==-1){//here : bugs
        w[tid[x1][y1]][i]=magic, ttid++;
        if(ttid==t) break;
       }
       d[x1][y1]=magic, cs.x=x1, cs.y=y1;
       bool exists=false;
       for(int p=0; p<4; p++){
        int x2=cs.x+dx[p], y2=cs.y+dy[p];
        if(x2>-1&&x2<m&&y2>-1&&y2<n&&d[x2][y2]==-1) exists=true;
       }
       if(exists) stack1[ssize++]=cs;
      }
      else left++;
     }
    }
    //don’t need to use stack1[stop-1] any more
    if(left==0){
     Node temp=stack1[stop-1]; stack1[stop-1]=stack1[validstart], stack1[validstart]=temp;
     validstart++;
    }
   }//while, stop when all of dots on the same level have been visited.
   magic++, ctype=(Stype)-ctype;
  }
  ssize=0;
 }
}
void addEdge(int i, int j, int w){
 es[eid].i=i, es[eid].j=j, es[eid].w=w;
 es[eid].next=firstX[i], firstX[i]=eid; eid++;
}
int HK(const int& w){
 memset((void*)linkX, 0xff, sizeof(linkX)),
  memset((void*)linkY, 0xff, sizeof(linkY));
 int res(0);
 while(HK_bfs(w)){
  for(int i=0; i<xid; i++)
   if(linkX[i]==-1&&HK_dfs(i)) res++;
 }
 return res;
}
bool HK_bfs(const int& w){
 int top=0, size=0; bool found=false;
 for(int i=0; i<xid; i++){
  if(linkX[i]==-1) queue[size++]=i;
  distX[i]=0;
 }
 memset((void*)distY, 0, sizeof(distY));
 for(;top<size; top++){
  int v=queue[top];
  for(int ed=firstX[v]; ed!=-1; ed=es[ed].next){
   if(es[ed].w<=w){//for current question
    if(!distY[es[ed].j]){
     distY[es[ed].j]=distX[v]+1;
     if(linkY[es[ed].j]==-1) found=true;
     else distX[linkY[es[ed].j]]=distY[es[ed].j]+1, queue[size++]=linkY[es[ed].j];
    }
   }
  }
 }
 return found;
}
bool HK_dfs(int v){
 for(int ed=firstX[v]; ed!=-1; ed=es[ed].next){
  if(distY[es[ed].j]==distX[v]+1){
   distY[es[ed].j]=0;
   if(linkY[es[ed].j]==-1||HK_dfs(es[ed].j)){
    linkX[v]=es[ed].j, linkY[es[ed].j]=v; return true;
   }
  }
 }
 return false;
}
#define fbase
int main()
{
#ifdef fbase
 ifstream in("input.txt");
 if(!in) return EXIT_FAILURE;
 cin.rdbuf(in.rdbuf());
#endif
 //implementation
 int ncase, x, y, cap;
 cin>>ncase;
 while(ncase–){
  //read configuration from map.
  memset((void*)tid, 0xff, sizeof(tid)), memset((void*)rid, 0, sizeof(rid));
  cin>>m>>n>>vk>>t;
  for(int i=0; i<vk; i++) cin>>ssc[i].x>>ssc[i].y, ssc[i].type=red, ssc[i].x–,ssc[i].y–;
  for(int i=0; i<vk; i++) cin>>ssc[i+vk].x>>ssc[i+vk].y, ssc[i+vk].type=green, ssc[i+vk].x–,ssc[i+vk].y–;
  cin>>x>>y;//ignore golden solider
  for(int i=0; i<t; i++){
   cin>>tsq[i].x>>tsq[i].y>>cap, tsq[i].x–, tsq[i].y–;
   tid[tsq[i].x][tsq[i].y]=i, reid[i]=reid[i-1]+cap;//reid[i-1]…reid[i]-1 for i’s node;
  }
  for(int i=0; i<m; i++){
   for(int j=0; j<n; j++) cin>>x, map[i][j]=x;
  }
  //calculate w[i][j], i is solider’s id, j is tsq’s id.
  calw();
  //set-up bio-partite
  memset((void*)firstX, 0xff, sizeof(firstX)), eid=0;
  xid=2*vk, yid=reid[t-1];
  for(int i=0; i<xid; i++){
   for(int j=0; j<t; j++){
    for(int yd=reid[j-1]; yd<reid[j]; yd++){//for index of Y’s set
     addEdge(i, yd, w[j][i]);//default is false
    }
   }
  }
  int p=0, match=HK(p);
  while(match<2*vk-p)
   match=HK(++p);
  if(p>2*vk) p=2*vk;
  cout<<p<<endl;
 }
#ifdef fbase
 in.close();
#endif
 return 0;
}
#undef fbase
很不甘心WA,晚上把BFS的那块重新写了,满怀希望的跑,结果还是WA。我彻底崩溃了,一天半的时间改一个写了30分钟的程序,换了5个版本,都是WA。最后这个版本还是有问题,Toy7.in的时候,差了3个匹配数,前面的4,6各少一个,实在想不通。把修改的新层次遍历的代码放在下面吧,下道题目,我死都要过掉!
 
void calw(){
 memset((void*)w, 0xff, sizeof(w));
 Node vn, cs; Stype ctype;
 int magic, ttid, stop, ssize, validstart, left, pre;
 for(int i=0; i<2*vk; i++){
  memset((void*)d, 0xff, sizeof(d));
  ctype=ssc[i].type; magic=0, ttid=0, ssize=0, validstart=0, pre=0;
  if(tid[ssc[i].x][ssc[i].y]!=-1&&w[tid[ssc[i].x][ssc[i].y]][i]==-1) w[tid[ssc[i].x][ssc[i].y]][i]=0, ttid++;
  d[ssc[i].x][ssc[i].y]=0;//DP level
  stack1[ssize].x=ssc[i].x, stack1[ssize++].y=ssc[i].y;
  while(ttid<t){
   stop=pre, pre=(magic==0?0:ssize);//back to the previous valid top.
   while(stop<ssize&&ttid<t){//for current BFS
    vn=stack1[stop++], left=0;
    for(int j=0; j<4&&ttid<t; j++){
     int x1=vn.x+dx[j], y1=vn.y+dy[j];
     if(x1>-1&&x1<m&&y1>-1&&y1<n&&d[x1][y1]==-1){
      if(ctype==red&&map[x1][y1]>=map[vn.x][vn.y]||(ctype==green&&map[x1][y1]<=map[vn.x][vn.y])){
       if(tid[x1][y1]!=-1&&w[tid[ssc[i].x][ssc[i].y]][i]==-1){//here : bugs
        w[tid[x1][y1]][i]=magic, ttid++;
        if(ttid==t) break;
       }
       d[x1][y1]=magic, cs.x=x1, cs.y=y1;
       bool exists=false;
       for(int p=0; p<4; p++){
        int x2=cs.x+dx[p], y2=cs.y+dy[p];
        if(x2>-1&&x2<m&&y2>-1&&y2<n&&d[x2][y2]==-1) exists=true;
       }
       if(exists) stack1[ssize++]=cs;
      }
      else left++;
     }
    }
    //don’t need to use stack1[stop-1] any more
    if(left==0&&stop-1>pre){
     swap(stack1[stop-1], stack1[pre++]);
    }
   }//while, stop when all of dots on the same level have been visited.
   magic++, ctype=(Stype)-ctype;
  }
 }
}

Advertisements