断了很长时间的网,整理下思路

Leave a comment

  • 断了将近3天的网络,郁闷了,手头有些生疏了!
  • 今天的目标:1,DP优化模型的总结,把这几天写的程序梳理下。2,Lucene应用:索引和搜索处理部分。3,抓脑壳改简历。
  • DP的题目列表和实现:
1,Musketeers [OI 1998/1999]:IRJ的思路,将每一个人拆为两点,只要自己与自己遇到就行了,遇到条件是Meet[i,k]&&Meet[k,j],其中i要打败k,或者k要被j打败。
#include <iostream>
#include <fstream>
using namespace std;
const int MAXN=101;
int n;
bool v[MAXN][MAXN], dp[MAXN][MAXN];
#define fbase
int main()
{
#ifdef fbase
    ifstream in("MUS1.in");
    if(!in) return EXIT_FAILURE;
    cin.rdbuf(in.rdbuf());
#endif
    //implementation
    cin>>n;
    int x, y;
    char c;//for ending of input file.
    cin.get(c);//for endl
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++)
            cin.get(c), v[i][j]=c-‘0’;
        cin.get(c);//for endl
    }
    memset((void*)dp, 0, sizeof(dp));
    //for each status, bottom to up.
    for(int len=1; len<n+1; len++){//take care of order
        for(int i=0; i<n; i++){
            if(len==1) dp[i][(i+1)%n]=true;
            else{
                y=(i+len)%n;
                for(int pl=1; pl<len; pl++){
                    x=(i+pl)%n;
                    if(dp[i][x]&&dp[x][y]&&(v[i][x]||v[y][x])){
                        dp[i][y]=true;
                        break;
                    }
                }
            }
        }
    }
    for(int i=0; i<n; i++){
        if(dp[i][i]) cout<<i+1<<endl;
    }
#ifdef fbase
    in.close();
#endif
    return 0;
}
#undef fbase
2,DDR White,书上的方程是对的,但不可用,因为这道题比较阴的是没有预先给大小,数组不可用,所以可以用滚动数组,从前面的状态滚到后面的状态,每次只需要k-1,k的两个位即可。
动规方程:d[i,j,k]->update(d[i,cstep,k+1], d[cstep,k+1]);[前向递推,将k+1全部初始化为INT_MAX,然后更新,注意k-1为INT_MAX时,不可用]
#include <iostream>
#include <fstream>
using namespace std;
const int MAXN=5, MAXK=(1<<31)-1;
int dp[MAXN][MAXN][2];
//declaration
int dptrial(int l, int r, int k, int cstep);
int inline effort(int s, int e);
//implementation
int dptrial(int l, int r, int k, int cstep){
    int tmp, min=MAXK;
    if(dp[l][r][(k-1)&0x1]!=MAXK){
        tmp=dp[l][r][(k-1)&0x1]+effort(l, cstep);
        if(dp[cstep][r][k&0x1]>tmp) dp[cstep][r][k&0x1]=tmp;
        if(min>tmp) min=tmp;
        tmp=dp[l][r][(k-1)&0x1]+effort(r, cstep);
        if(dp[l][cstep][k&0x1]>tmp) dp[l][cstep][k&0x1]=tmp;
        if(min>tmp) min=tmp;
    }
    return min;
}
int inline effort(int s, int e){//要画下哈。
    if(s==e) return 1;
    if(s==0) return 2;
    if(((s-1+3)&0x3)+1==e||(s&0x3)+1==e) return 3;
    if(((s-1+6)&0x3)+1==e||((s-1+2)&0x3)==e) return 4;
}
#define fbase
int main()
{
#ifdef fbase
    ifstream in("input.txt");
    if(!in) return EXIT_FAILURE;
    cin.rdbuf(in.rdbuf());
#endif
    //implementation
    int x, min, tmp, i;
    while(cin>>x&&x){
        i=1, min=MAXK;
        //scrolling array
        for(int l=0; l<MAXN; l++)
            for(int r=0; r<MAXN; r++) dp[l][r][0]=0, dp[l][r][1]=MAXK;
        tmp=dptrial(0, 0, i, x);
        if(min>tmp) min=tmp;
        while(cin>>x&&x){
            i++;
            for(int l=0; l<MAXN; l++)
                for(int r=0; r<MAXN; r++) dp[l][r][i&0x1]=MAXK;//scrolling start
            min=MAXK;
            for(int l=0; l<MAXN; l++)
                for(int r=0; r<MAXN; r++){
                    tmp=dptrial(l, r, i, x);
                    if(min>tmp) min=tmp;
                }
        }
        cout<<min<<endl;
    }
#ifdef fbase
    in.close();
#endif
    return 0;
}
#undef fbase
3,1390 Blocks:蛮经典的,思路巧妙,先把颜色相同的合并,然后f[i,j,k]=max{f[i,j-1,0]+(len[j]+k)^2, f[i,p,k+len[j]]+f[p+1,j-1,0]}.一步优化,把pre[1…ctid]表示为每个颜色块的前一个相同颜色块,用数组链表即可。可惜代码还是慢,不说了。

Source Code

Problem: 1390 User: orlando22
Memory: 32100K Time: 1344MS
Language: C++ Result: Accepted
  • Source Code
    #include <iostream>
    
    //pku 1390 Blocks
    using namespace std;
    
    const int MAXN=201;
    int color[MAXN], len[MAXN], dp[MAXN][MAXN][MAXN], ctid=0, pre[MAXN], first[MAXN];
    
    //declaration
    int dptrial(int i, int j, int k);
    
    //implementation
    int dptrial(int i, int j, int k){
        if(dp[i][j][k]!=-1) return dp[i][j][k];
        int tmp=INT_MIN, value1, value2;
        value1=dptrial(i, j-1, 0)+(len[j]+k)*(len[j]+k);
        if(value1>tmp) tmp=value1;
        for(int p=pre[j]; p!=0&&p>=i; p=pre[p]){
            value1=dptrial(i, p, k+len[j]), value2=dptrial(p+1, j-1, 0);
            if(value1+value2>tmp) tmp=value1+value2;
        }
        dp[i][j][k]=tmp;
        return tmp;
    }
    
    int main()
    {
        //implementation
        int ncase=1, nt, n, cpid, c;
        cin>>nt;
        for(;ncase<=nt;ncase++){
            memset((void*)color, 0, sizeof(color)), memset((void*)len, 0, sizeof(color)),
            memset((void*)pre, 0, sizeof(pre)),//each previous color of block
            memset((void*)first, 0, sizeof(first)),//for current color list
            memset((void*)dp, 0xff, sizeof(dp));
            for(int i=1; i<MAXN; i++){
                for(int j=0; j<MAXN; j++) dp[i][i-1][j]=0;
            }
            cin>>n; ctid=0, cpid=0;
            for(int i=0; i<n; i++){//color is for 1..n
                cin>>c;
                if(cpid!=c) color[++ctid]=c, len[ctid]++, cpid=c, pre[ctid]=first[c], first[c]=ctid;
                else len[ctid]++;
            }
            cout<<"Case "<<ncase<<": "<<dptrial(1, ctid, 0)<<endl;
        }
        return 0;
    }
详细分析黑书上有,不过是DP里面再用DP套了一层。代码如下:
#include <iostream>
#include <fstream>
using namespace std;
const int MAXN=51, MAXM=301, MAXT=18100;
int st[MAXM], tt[MAXM], next[MAXM], sp[MAXN], first[MAXN],
    w[MAXT][MAXM], f[MAXN][MAXT], dt[MAXT][MAXM], n, m, ans, ct;
//declaration
int toSec(int time);
void format(int time);
//implementation
int toSec(int time){
    int sec=time%100; time/=100;
    int min=time%100; time/=100;
    return (time-6)*3600+min*60+sec;
}
void format(int time){
    int tmp=time/3600;//tmp
    if(tmp+6<10) cout<<0;
    cout<<tmp+6;
    time-=tmp*3600;
    tmp=time/60;
    if(tmp<10) cout<<0;
    cout<<tmp;
    time-=tmp*60;
    if(time<10) cout<<0;
    cout<<time<<endl;
}
#define fbase
int main()
{
#ifdef fbase
    ifstream in("input.txt");
    if(!in) return EXIT_FAILURE;
    cin.rdbuf(in.rdbuf());
#endif
    //implementation
    int t;
    cin>>n>>m;
    memset((void*)first, 0xff, sizeof(first));
    for(int i=1; i<m+1; i++){
        cin>>sp[i]>>st[i]>>t; st[i]=toSec(st[i]);
        tt[i]=st[i]+t;
        next[i]=first[sp[i]];
        first[sp[i]]=i;
    }
    memset((void*)f, 0, sizeof(f));
    f[1][0]=0;
    for(int i=2; i<n+1; i++){
        memset((void*)w, 0, sizeof(w));
        for(int t=300*(i-2); t<=600*(i-2); t++){//for each starting time of i-1 gate
            memset((void*)dt, 0, sizeof(dt));
            for(int tmp=first[i-1]; tmp!=-1; tmp=next[tmp]){
                if(t<=st[tmp]&&tt[tmp]<=t+300) w[t][0]++;
                else{
                    if(st[tmp]<=t&&0<tt[tmp]-t&&tt[tmp]-t<=300) dt[t][tt[tmp]-t]–;
                    if(st[tmp]>=t&&0<=tt[tmp]-t&&tt[tmp]-t<=300) dt[t][tt[tmp]-t]++;
                }
            }
            for(int j=1; j<MAXM; j++) w[t][j]=w[t][j-1]+dt[t][j-1];//dt
        }
        for(int t=300*(i-1); t<=600*(i-1); t++){
            for(int tk=300; tk<=600; tk++){
                if(t-tk>=0) f[i][t]=max(f[i][t], f[i-1][t-tk]+w[t-tk][tk-300]);
                else break;
            }
        }
    }
    ans=-1, ct=-1;
    for(int i=300*n; i<=600*n; i++){
        if(f[n][i]>ans) ans=f[n][i], ct=i;
    }
    cout<<ans<<endl;
    format(ct);
#ifdef fbase
    in.close();
#endif
    return 0;
}
#undef fbase
时间转化有点麻烦,其他的处理一般
5,Building Game[NOI 97]:这道题目也是很经典的,前向递推和后向递推不对称。
算法分析:LRJ分析如下,由于第k堆的编号大于第k+1堆编号,不是很自然,所以等价的反一下。状态i为当前的柱子数,a为当前最大的已用积木编号,b为当前最顶层的积木编号,k是当前最顶层的积木顶面编号[0,1,2].但状态要有所选择,(i,a,b,k)若是当前已经获得柱子总长度,那么我们只有用前向动规打表到最后的(m,n,1…n,0,1,2)然后再做一次O(N^2)的比较。确实很烦,而且动规方程不好写。
而后向动规,则表示(i,a,b,k)是当前还能获得积木高度,前面一个枚举k,即可。而且动规方程可以顺利写出:
d(i, a, b, k)=
1,若新起一堆,则d(i+1,a+1, a+1, k’)+height(a+1, k’).[注意i<m==>i+1<=m]
2,若在当前堆上加一个,则d(i, a+1, a+1, k’),注意k’面一定要被k面包含
3,弃用,则d(i, a+1, b, k)。没有条件控制。
还是可能存在稀疏状态,因为有一个面包含问题,所以,用记忆化搜索如下:
#include <iostream>
#include <fstream>
using namespace std;
const int MAXM=101, MAXN=101, MAXK=3;
int d[MAXM][MAXN][MAXN][MAXK], n, m;
typedef struct Stick{
    int a, b, c;
}Stick;
Stick st[MAXN];
//declaration
int dptrial(int i, int a, int b, int k);
int inline height(int k, int id);
bool inline cover(int id1, int k1, int id2, int k2);
//implementation
int dptrial(int i, int a, int b, int k){
    if(d[i][a][b][k]!=-1) return d[i][a][b][k];
    if(a==n){d[i][a][b][k]=0; return 0;}
    //split
    int tmp=INT_MIN, c;
    if(i<m){//add another stick sepearately情况1
        for(int kl=0; kl<MAXK; kl++){
            c=dptrial(i+1, a+1, a+1, kl)+height(kl, a+1);
            if(c>tmp) tmp=c;
        }
    }
    for(int kl=0; kl<MAXK; kl++){//compare the size情况2
        if(cover(b, k, a+1, kl)){
            c=dptrial(i, a+1, a+1, kl)+height(kl, a+1);
            if(c>tmp) tmp=c;
        }
    }
    c=dptrial(i, a+1, b, k);//情况3
    if(c>tmp) tmp=c;
    d[i][a][b][k]=tmp;
    return tmp;
}
int inline height(int k, int id){
    if(k==0) return st[id].c;
    if(k==1) return st[id].b;
    if(k==2) return st[id].a;
}
bool inline cover(int id1, int k1, int id2, int k2){//id1 is under id2注意面要包含
    if(k1==0){//a,b
        if(k2==0)
            return (st[id1].a>=st[id2].a&&st[id1].b>=st[id2].b)||(st[id1].a>=st[id2].b&&st[id1].b>=st[id2].a);
        if(k2==1)
            return (st[id1].a>=st[id2].a&&st[id1].b>=st[id2].c)||(st[id1].a>=st[id2].c&&st[id1].b>=st[id2].a);
        if(k2==2)
            return (st[id1].a>=st[id2].c&&st[id1].b>=st[id2].b)||(st[id1].a>=st[id2].b&&st[id1].b>=st[id2].c);
    }
    if(k1==1){//a,c
        if(k2==0)
            return (st[id1].a>=st[id2].a&&st[id1].c>=st[id2].b)||(st[id1].a>=st[id2].b&&st[id1].c>=st[id2].a);
        if(k2==1)
            return (st[id1].a>=st[id2].a&&st[id1].c>=st[id2].c)||(st[id1].a>=st[id2].c&&st[id1].c>=st[id2].a);
        if(k2==2)
            return (st[id1].a>=st[id2].c&&st[id1].c>=st[id2].b)||(st[id1].a>=st[id2].b&&st[id1].c>=st[id2].c);
    }
    if(k1==2){//c, b
        if(k2==0)
            return (st[id1].c>=st[id2].a&&st[id1].b>=st[id2].b)||(st[id1].c>=st[id2].b&&st[id1].b>=st[id2].a);
        if(k2==1)
            return (st[id1].c>=st[id2].a&&st[id1].b>=st[id2].c)||(st[id1].c>=st[id2].c&&st[id1].b>=st[id2].a);
        if(k2==2)
            return (st[id1].c>=st[id2].c&&st[id1].b>=st[id2].b)||(st[id1].c>=st[id2].b&&st[id1].b>=st[id2].c);
    }
}
#define fbase
int main()
{
#ifdef fbase
    ifstream in("input.txt");
    if(!in) return EXIT_FAILURE;
    cin.rdbuf(in.rdbuf());
#endif
    //implementation
    memset((void*)d, 0xff, sizeof(d));
    cin>>n>>m;
    for(int i=1; i<=n; i++) cin>>st[i].a>>st[i].b>>st[i].c;
    int max=INT_MIN, tmp;
    for(int i=0; i<MAXK; i++){
        tmp=dptrial(1, 1, 1, i)+height(i, 1);//高度加和问题
        if(tmp>max) max=tmp;
    }
    cout<<max<<endl;
#ifdef fbase
    in.close();
#endif
    return 0;
}
#undef fbase
  • DP的优化模型总结:
  • 一道很有趣的面试题目,网易有道的一道题目。
打印如下形式的矩阵;
n=5:
1  2  9  10 25
4  3  8  11 24
5  6  7  12 23
16 15 14 13 22
17 18 19 20 21
手画还可以但是要编码,似乎不是很好搞。
在纸上画了下,发现路径有如下规律:只看增量,x,y坐标的变化
(0,0)//不符合就手动写了
(0,1)->(1,0)->(0,-1) l=1
(1,0)->(0,1)->(0,1)->(-1,0)->(-1,0) l=2
(0,1)->(1,0)->(1,0)->(1,0)->(0,-1)->(0,-1)->(0,-1) l=3
原来是这样的,从(0,0)开始,以(dx=0,dy=1)为起始增量,设置一个开始点,然后交换之走一个l长,再恢复并将1变为-1,走一个l长。
代码很简练,只是写的时候忘记l++了,还是写到for里面去吧。只是怎么去掉那个打表项,好像可以用console的输入处理来做,win32里面倒有API。
#include <stdlib.h>
#include <iostream>
using namespace std;
const int MAXN=10;
int a[MAXN][MAXN], n=10;
int _tmain(int argc, _TCHAR* argv[])
{
 int x=0, y=0, l=1, dx=0, dy=1, c=1;
 a[0][0]=c++;
 for(;c<=n*n;swap(dx, dy), l++){
  a[x=x+dx][y=y+dy]=c++;
  for(int i=0; i<l; i++) a[x=x+dy][y=y+dx]=c++;
  for(int i=0; i<l; i++){
   if(dx==0) a[x=x+dx][y=y-dy]=c++;
   if(dy==0) a[x=x-dx][y=y+dy]=c++;
  }
 }
 for(int i=0; i<n; i++){
  for(int j=0; j<n; j++) cout<<a[i][j]<<" ";
  cout<<endl;
 }
 system("pause");
 return 0;
}

总结在线搜索相关的基础算法

Leave a comment

  • 今天的目标有两个:一把搜索相关的基础算法,整理白纸编程并完整实现;二切掉DP的三道水题;三恢复下口语和智力测试。
  • 和袁源聊了一下,一是讨论这道题目,二是讨论一些关于工作的事情。题目的讨论让人多有感慨的,袁源的思路还是相当的严谨,这个是要值得自己学习的。工作上的事情,谢谢点虫虫,代毅的关心,兄弟很感激,也会好好规划自己的未来的;袁源说,其实你也可以考虑去一些起步规模不大的公司,但一定要保证自己就是要做核心的事情,有了经验的积累之后很多事情就水到渠成了,先尽全力去能人众多的公司,为自己定的方向找个好老师,好好锻炼吧!涓涓细流,终汇成海,自己虽然起步晚,天资不足,但还可以靠勤奋和踏实找到自己的位置的!加油!
  • 刚刚老谢同学问了一道动规的题目,还是迅速切掉吧,夜长梦多。下面是发给他的分析和代码实现,可以用字典树优化的,不难就是了。
1,动规方程分析:
和刚才的思路一样,最原始的动规方程式d[i,j]=min{d[i, k-1]+d[k,j]},d[i,j]表示从i到j的数字索引位置包含的最少词个数。[忘记加这个了,呵呵!最优子结构嘛,编程的时候先就去想字典的结构了,还是要注意的。其实这里没写,关键在于如何存储转化字典用vector<int>还是其他的,再扫下题目的输入,就有答案了。]
再进一步,由于我们可以从0的位置开始,那么这个方程就可以简化为d[i]=1+min{d[j]},j>i,表示从i到j-1的位置匹配了一个单词。这样动规就变成线型了。
2,关键的问题在于:如何匹配词和将词转化为字典,观察到要输出这些词,换言之,必须要保存原始的词,同时也要计算出转化为数字的词
所以存储上可以用一个vector<int> words来做每一个数字开头的字典,然后vector<string> org_words[MAXN];存储原来对应的词,至于动规取到的词,我们可以
用一个数组来保存决策值。
3,如何实现动规,可以用至底向上,但是,刚才提到了这个状态是稀疏的,也就是每一个数字开头不一定能匹配到值,所以好的办法是记忆搜索。可惜的是,这道题目的运行表现差强人意了,我郁闷!瓜了,运行的结果和CEOI的答案不一样,想了5分钟,结果是special judge,差点一口血吐到屏幕了。

Source Code

Problem: 1732 User: orlando22
Memory: 2040K Time: 157MS
Language: C++ Result: Accepted
  • Source Code
    #include <iostream>
    #include <string>
    #include <vector>
    
    using namespace std;
    
    //dictionary check
    const int dicSize=26, MAXNUM=100, MAXN=10;
    char dic[dicSize]={'2', '2', '2', '3', '3', '3', '4', '4', '1', '1', '5', '5', '6', '6', '0',
                '7', '0', '7', '7', '8', '8', '8', '9', '9', '9', '0'};
    vector<string> words[MAXN];
    vector<string> org_words[MAXN];
    string tword;//for target word for string
    int dp[MAXNUM];
    string ins[MAXNUM];
    
    //declaration
    string ToNumStr(string temp);
    int calShort(int index);
    
    //impelemenation
    string ToNumStr(string temp){
        string tw;
        for(int i=0; i<temp.size(); i++) tw.push_back(dic[temp[i]-'a']);
        return tw;
    }
    int calShort(int index){
        if(index==tword.size()) return 0;//upper boundary
        if(dp[index]!=-1) return dp[index];
        //enum for all words of tword[index]
        int ret=INT_MAX, t=tword[index]-'0';
        for(int i=0; i<words[t].size(); i++){
            bool match=true;
            int k=index, tid=0;
            for(;k<tword.size()&&tid<words[t][i].size(); k++, tid++){
                if(tword[k]!=words[t][i][tid]){
                    match=false; break;
                }
            }
            if(match&&k<=tword.size()&&tid==words[t][i].size()){//all length has been used by tid.写些垃圾代码,边界值老子
                int next=calShort(index+words[t][i].size());
                if(next!=INT_MAX&&next+1<ret){
                    ret=next+1, ins[index]=org_words[t][i];
                }
            }
        }
        dp[index]=ret;
        return ret;
    }
    
    int main()
    {
        //implementation
        int diclen, result; string temp, trword;
        cin>>tword>>diclen;
        for(int i=0; i<diclen; i++){
            cin>>temp, trword=ToNumStr(temp);
            words[trword[0]-'0'].push_back(trword),
            org_words[trword[0]-'0'].push_back(temp);//must store the orignal string
        }
        //DP table
        memset((void*)dp, 0xff, sizeof(dp));
        result=calShort(0);
        if(result==INT_MAX) cout<<"No solution."<<endl;
        else{
            int num=0;
            for(int j=0; j<tword.size(); j=j+ins[j].size(), num++){
                if(num==0) cout<<ins[j];
                else cout<<" "<<ins[j];
            }
            cout<<endl;
        }
        return 0;
    }
  • 从基础的排序实现到基础的搜索算法:题目的抽象原型是BOP的K个最大的数,第一次看写程序的时候觉得那些方法完全没有内在联系,什么东西嘛。再回头都实现一遍[搜索部分留到写软件的时候实现,先提代码实现框架吧]大多数东西是BOP上的衍生思考,没有原创性。^_^|||
Q:假如给你一堆数,怎么求出最大的K个?
应该反思的是,数在哪里?有多大[每个数的字节长度,总数组的规模],求的过程需要多长时间,空间。数的输入规模和输出规模多大。一切都不知道,那只有把(N,K)作为参数做一个递增的分析了。
  • 1,假设N<10^9,那么一个程序的bss段里面应该是能放下的,不妨从内部排序开始分析。

    先假设K~N,那么可以用最简单的思路比较排序嘛,下面实现了比较排序里面的快排,归并和堆排。提醒自己还是要小心,基础的咚咚要一点都不能含糊。

    //inneral sorting algorithm
    template<class Type>
    void qsort(int l, int r, Type* arr){
        while(l<r){
            int p=l, q=r+1;
            while(true){
                while(++p<r&&arr[p]<arr[l]);
                while(--q>l&&arr[q]>arr[l]);
                if(p>=q) break;
                swap(arr[p], arr[q]);//previous bug
            }
            if(l!=q) swap(arr[q], arr[l]);
            qsort(l, q-1, arr);
            l=q+1;
        }
    }

    //merge sort algorithm
    int b[9];
    template<class Type>
    void mergesort(int l, int r, Type* arr){
        if(l<r){
            int mid=l+((r-l)>>1), p=l, q=mid+1, k=l;
            mergesort(l, mid, arr), mergesort(q, r, arr);
            while(p<=mid||q<=r){
                if(p<=mid&&(q>r||arr[p]<=arr[q])) b[k++]=arr[p++];
                else b[k++]=arr[q++];
            }
            for(int i=l; i<=r; i++) arr[i]=b[i];//where is it b?
        }
    }

    //heap-sort algorithm : selective algorithm.
    template<class Type>
    void heapadjust(int current, int heapEnd, Type* arr){
        int child=(current<<1)+1;
        Type tmp=arr[current];
        while(child<=heapEnd){
            if(child+1<=heapEnd&&arr[child]<arr[child+1]) child++;
            if(tmp<arr[child]||tmp==arr[child]) break;
            swap(arr[current], arr[child]);
            current=child, child=(child<<1)+1;
        }
    }
    template<class Type>
    void heapsort(int size, Type* arr){
        for(int i=(size>>1); i>=0; i--) heapadjust(i, size-1, arr);
        for(int i=size-1; i>0; i--){
            swap(arr[0], arr[i]);
            heapadjust(0, i-1, arr);
        }
    }

    先全部排序,然后把K个输出即可,时间复杂度为O(NlogN)。由于K~N,所以在比较决策树的模型之下,已经是比较好的一种算法了。

  • [当然,可以来个逆向思维,K~N那么N-K~0,那么这个问题就可以转化为求N-K个最小数的模型,复杂度是可以改进的。但这里是总结思路,主要看算法的实现技巧,不钻牛角尖料。]
    2,对于K<<N的情况下,可以只取前面的最大K个。等下没说过前K个一定排序,所以首先想到的是中位数处理问题的算法。求出K大的即可
    • 对于内排而言,可以直接写出求k大数的快排,实现代码如下,O(N*logK)

    //k’s sorting algorithm
    template<class Type>
    void ksort(int l, int r, const int& k, Type* arr){//min-k
        if(l<r){
            int p=l, q=r+1;
            while(true){
                while(++p>r&&arr[p]<arr[l]);//remember the boundary check.
                while(–q>l&&arr[q]>arr[l]);
                if(p>=q) break;
                swap(arr[p], arr[q]);
            }
            if(l!=q) swap(arr[l], arr[q]);
            if(q-l+1==k) return;
            else if(q-l+1<k) ksort(q+1, r, k-(q-l+1), arr);
            else ksort(l, q-1, k, arr);
        }
    }

    • 下一个方法是开始我没想通的,觉得BOP的神牛们简直太强了,神来之笔呀。仔细分析下,其实是有来源的,这是一种参数搜索的思路,在一些DP和搜索的算法实现中,由于参数范围过大,导致盲目搜索代价太高,所以我们利用其函数单调性[抄书问题是个典型]来在不同的范围求解以求最终逼近真实值。这个问题的真实值是具备单调性的,原始的我们可以猜想k大的数为最小数,然后统计出个数,再一步一步来,进一步二分可解。只是要先求出K大的数,再过一遍N数[是N数么?其实不是只需要[目标区间]的所有值,这样就可能从内排突破到外派,强呀,佩服]。下面是代码实现,复杂度为O(Nlog(|Vmax-Vmin|/delta)).

    //declaration
    void ksearch(int size, const int& k, int* arr);
    void MinMax(int l, int r, int* arr, int& Vmax, int& Vmin);
    int count(int size, int* arr, int Vmid);
    //parameter search
    void ksearch(int size, const int& k, int* arr){
        double delta=.5;
        int Vmax, Vmin, Vmid;
        MinMax(0, size-1, arr, Vmax, Vmin);
        while(Vmax-Vmin>delta){
            Vmid=Vmin+(Vmax-Vmin)/2;
            //here is the bottle neck of algorithm.
            if(count(size, arr, Vmid)>=k) Vmin=Vmid;
            else Vmax=Vmid;
        }
        Vmax=floor(Vmax);
        for(int i=0; i<size; i++){
            if(arr[i]>=Vmax) cout<<arr[i]<<" ";
        }
        cout<<endl;
    }
    void MinMax(int l, int r, int* arr, int& Vmax, int& Vmin){//用了个瓜兮兮的分治
        if(l+1<=r){
            if(arr[l]<=arr[r]) Vmax=arr[r], Vmin=arr[l];
            else Vmax=arr[l], Vmin=arr[r];
            return;
        }
        int mid=l+((r-l)>>1), k1, k2;
        MinMax(l, mid, arr, Vmax, Vmin), MinMax(mid+1, r, arr, k1, k2);
        if(Vmax<k1) Vmax=k1;
        if(Vmin>k2) Vmin=k2;
    }
    int count(int size, int* arr, int Vmid){
        int count=0;
        for(int i=0; i<size; i++) if(arr[i]>=Vmid) count++;
        return count;
    }

    • 大顶堆算法,呵呵,好耍!这个算法就可以彻底将内排在可能情况下(K内存可存)扩展到外排。过一遍数组,一边过一边建堆,大顶堆即为所求。O(NlogK)

    //minheap algorithm.
    template<class Type>
    void filterup(int current, Type* arr){
        int parent=(current-1)/2; Type tmp=arr[current];
        while(parent>=0){
            if(arr[parent]<=arr[current]) break;
            swap(arr[parent], arr[current]);
            current=parent, current=(current-1)/2;
        }
    }
    template<class Type>
    void filterdown(int current, int heapEnd, Type* arr){
        int child=(current<<1)+1; Type tmp=arr[current];
        while(child<=heapEnd){
            if(child+1<=heapEnd&&arr[child+1]<arr[child]) child++;
            if(tmp<arr[child]||tmp==arr[child]) break;
            swap(arr[child], arr[current]);
            current=child, child=(child<<1)+1;
        }
    }

    #define fbase
    int main()
    {
    #ifdef fbase
        ifstream in("in1.txt");
        if(!in) return EXIT_FAILURE;
        cin.rdbuf(in.rdbuf());
    #endif

        //implementation, inneral sorting. O(NlogK)
        int u;
        while(!in.eof()&&cin>>u){
            if(lsize<MAXK){
                list[lsize++]=u, filterup(lsize-1, list);//maintain minheap
            }
            else if(u>list[0]){
                list[0]=u, filterdown(0, MAXK-1, list);
            }
        }
        for(int i=0; i<MAXK; i++) cout<<list[i]<<" ";
        cout<<endl;

    #ifdef fbase
        in.close();
    #endif
        return 0;
    }
    #undef fbase

    • 然后就是线形排序的处理了,计数排序的实现如下:注意可以省去Copy数组的。好,看代码

    const int MAXN=20, MAXM=40;
    int t[MAXN], ct[MAXM], b[MAXN];
    //counting sort
    void csort(int size, int* arr){
        for(int i=0; i<size; i++) ct[arr[i]]++;//clr ct in advance.
        for(int i=1; i<MAXM; i++) ct[i]+=ct[i-1];
        //suppose there are tareget array
        //s1 : for(int i=0; i<size; i++) b[ct[arr[i]]-1]=arr[i], ct[arr[i]]–;//can we ignore such b[0…size] array or not?
        //s2 : forward-star
        for(int i=MAXM-1; i>=1; i–){
            for(int j=ct[i]-1; j>=ct[i-1]; j–) arr[j]=i;
        }
        for(int i=0; i<ct[0]; i++) arr[i]=0;
    }

    完了么?但作者在最后莫名其妙的写了一个桶排[分段后面用链表连起来,在链头维护下元素范围和大小],好奇怪,而且似乎欲言又止。

    3,扩展的外沿==在线搜索的基础算法雏形

  • 扩展1,求N个数中不同的k数。
    思路一:在内排许可下,可以先用insertsort去重,然后再套用上面的快排或者参数搜索。[但这个局限性太大,只能内排,设N->无穷,就肯定没戏]
    思路二:外排扫描一次文件,求出其数值区间;然后使用桶排分块,插入数据,维护一个K数的可用区间范围,然后进行插入,这样就可以避免重复。条件:在K内存可放的情况下
    思路三:其实是最先想到的,大顶堆算法,加一个K的比较,假如再加一个挨球的改进进去,不是我想的。Jon有个人为二分的算法,在大顶堆内记录其1/2区间范围,
  • 就可以将判重的查找强行降到O(logK). 想了下,写了个快排的实现,结果发现有点忘记考虑了,除平衡位置外,其他数据的重复不可用。
    思路四:大顶堆算法,做一个try-rollback的操作,这个思路相当妙。值得让人拍案,不敢贪功,袁源的思路,但值得一写。
     
    所以,这条路貌似不行,或许是我有点笨吧。
     
  • 至于k到m的,思路二三都可用。
  • 扩展3的问题:就是一个搜索的基本算法问题了,原始的思路就是思路二,学名叫HYBRID Scheme;再多线程条件的改进算法,叫做Codir。不敢说是自己想的,见参考资料:BalalaBa
  • 扩展4的问题:可以提炼为一个模型,单查询多机存储的调度问题[自己改的名字,瓜求得很]:因为对于一个query的查询结果已经不可能在一台机器下存下了,但用户又需要快速的反应,起码一秒吧,如果是我的话,100MS没反应,我肯定就要锤墙了。那就用多台机器把query的返回结果放入各自的内存系统,然后用调度算法来取出其最大的K个。这里作者是提示不要钻牛角尖吧,将多个机器的K个或者。9K个精确页面进行合并求出其最大的K个,最经典的是多路归并的败者树[达平和老谢的最爱],或者k路归并的经典算法,其实大顶堆也在可取之类。只是如作者所说,应该要多个连续堆来处理吧。
  • 扩展5的问题:我已经无力解答了[确实经验不够],因为关键字的相似度如何推算出文档的相关度,确实不知道,但可以这样看,假设我们能获取到前K个文档,然后呢,下一个查询关键字和当前关键字很接近[相似度公式],我们就可以求出其相似度,进而用相似度求出其文档权重,但这个文档权重是估计值,应该还要加上估计公式,这样大概就能求出其准确程度,我们提供这个K个文档最精确的子集作为下一次查询的备选集。很多地方没想清楚,首先公式不好设计,其次是搜索的模型还和这些东西相关.瞎说的,烧烤而已。
  • 想写个小软件跑下抓取和桶排了!手痒的很。上面的扩展分析自己写的,应该很有多错误,希望假设有的朋友觉得有错,一定要给我指出来哈,最好能分析下!先谢谢了!

    图论的综合题

    Leave a comment

    4,10630 – Millennium Ceremony,图论的压轴题吧!很多东西在里面。

    关键知识点:外向树,欧拉回路的构造,完美匹配,以及改造的图存储.沿用书上的分析,加上一些自己的证明[书上有些地方没有完全写透,应该是留给写程序的人思考的].

    算法分析:

    • chris 和chrit的路径必然都是一条完整的欧拉回路,换言之,我们需要构造这样的一条欧拉回路.但更重要的是要求同层rops颜色相间,所以要先设法构造出满足这个条件的欧拉回路.很容易知道chris[或者chrit]的变色边必然是连通的,且0层的入度为0,其他所有点的入度为1,那么这是一个以0层祭坛为根的外向树.假设我们能构造出这条外向树,并且在此基础上构造出含这条外向树的欧拉回路.那么,对于chris以及chrit可以求出其路径了
    • 外向树的构造法:从祭坛引出1,3,5…m-1等出边到第一层[并且将2,4,6,8…m等设置为入边,开始稀里糊涂的写程序,结果仔细一看度不平衡,俄,又迷信LRJ了],再在两个内层i,i+1之间求一次完美匹配[如何证明?每个柱子都有k个连接边到上层,换言之,X集的每个顶点出度均为k,而Y集的每个顶点入度也为k,且对于X集和Y集而言,彼此序号必然对等,m为偶数,而k个层间ropes连接的两个端点奇偶一致],X集的每一个顶点引出一个有向边到Y集的对端,由此Y集的每一个奇数点必然都被占据.OK,那么如此匹配的结果就是1…n层的所有奇数点均入度为1,然后再从n层的随机点引一条边到n+1层的圣火炬,外向树就构造完毕了.
    • 基于外向树的欧拉回路:在外向树边的基础上,添边形成全边的欧拉回路,第一类边:从2,4,m到祭坛0的入边,以及从1,3,5,…m-1到火炬的入边,从火炬到2,4,6…m的出边;第二类边:同层连接边,从2i->(2i+1)%m的连接边[每个柱子出入平衡];第三类边:层间连接边,对每个节点的剩余k-1条边进行奇偶完美匹配[奇数为出边,偶数为入边].
    • 带限制的欧拉回路算法:直接用欧拉回路算法求解,只是要保证变色边是x->y中,使得若y是第一次到达,x->y是外向树的变色边.
    • 路径递推:得到了chris的路线之后,只需要把他到达的每个点向“右”旋转一个单位,就可以得到chrit的路线。什么意思?将路径平移转化到下一个间边即可。
    • 无解的情况:什么时候无解呢?没想清楚,因为按照构造法,m是偶数,k是奇数,这样一定能保证欧拉回路是存在的,而外向树的构造肯定是存在的.疑惑中,只有先烧烤一下了.

    附一个外向树生成示意:

    算法实现分析:

  • E路的两个简单实现:[不含验证逻辑,验证很简单,从一点出发DFS或者直接用es来做并查集,同时记录每点的入度和出度,入度出度不同,直接跳出;不连通,直接跳出]
  • 1, 圈套算法的一个简化版本[USCAO上摘录]
    //circuit is a global array
    void find_euler_circuit(){
        circuit_pos=0;
        find_circuit(node 1);
    }
    //nextnode and visited is a local array,the path will be found in reverse order
    void find_circuit(node i){
      while(hasNeighbors(node i)){//for list all nodes in Euler circuit
           pick a random neighbor node j of node i
           delete_edges(node j, node i);
           find_circuit(node j);
      }
      circuit[circuitpos++]=node i;
    }
     
    2,fleury算法 [离散数学上的代码框架]

    (1).任取v0属于v(G),P0=v0;

    (2) Pi=v0e1v1e2…eivi已经行遍,按下面方法来从E(G)-{e1,e2,…..ei}中任取ei+1 ;

          (a) : ei+1vi相关联:

          (b): 除非无别的边可供行遍,否则ei+1不应该为Gi=G-{e1,e2,….ei}中的桥.[求桥的算法那是相当讨厌的]

    (3): (2)不能再进行时,算法停止.

    可以证明,当算法停止时所得的简单回路Pm=v0e1v1e2….emvm(vm=vo)G中的一条Euler Circuit.

    总结:这种算法的复杂度是o(e*e),

    • 代码实现上的一个技巧:圈套算法USACO的版本,是以入边为基础的,因此在手动构造图的时候,将其边反过来,记录其入边集合,其实还可以优化一下的,可以把外向树的边放在每个入边顶点的最后,这样Euelur路的算法里面都不用交换顶点了.懒了一下.然后就是E路的求法了,由于E路是反向的[dfs递归的顶部是无后继点],最初的顶点是最后访问的,因此在扩展的时候,将外向树的边[每个顶点只有一条]放在最后即可.这样E路代码就可以在10行左右搞定了.
    • 悲惨的WA,UVA的结果是[估计应该是无欧拉路的时候的错误,郁闷,还是没能烧烤过去,再想下罗]

      7136448 10630 Millennium Ceremony Wrong answer C++ 0.416 2009-05-18 15:08:42

    附现在的代码实现:调试了一下,发现了无向树生成的错误和序号计算的错误.
    // MillCeremony.cpp : Defines the entry point for the console application.
    //
    #include "stdafx.h"
    #include <assert.h>
    #include <stdlib.h>
    #include <iostream>
    #include <fstream>
    #include <vector>
    using namespace std;
    const int MAXM=50, MAXN=50, MAXK=9, MAXENS=24000/*max crossing ropes*/, MAXET=25000, MAXMN=2600;
    typedef struct ENode{
        int i, j, next;
    }ENode;
    ENode inext[MAXENS];
    typedef struct Edge{
        int i, j, next;
        bool color, visited;
    }Edge;
    Edge es[MAXET];
    int eid, nid, m, n, k, firstI[MAXMN], firstG[MAXMN];
    //declaration
    void clr();
    void nextInner(int pid, int nid);
    void addREdge(int end, int start, bool color);
    void createEuler();
    void createOutTree();
    void addLeft();
    //perfect match algorithm
    //structure
    int linkX[MAXM+1], linkY[MAXM+1], distX[MAXM+1], distY[MAXM+1], queue[MAXM];
    int HK(int curl);
    bool HK_bfs(int curl);
    bool HK_dfs(int v, int curl);//v->0…m-1
    //EulerCircuirt algorithm
    vector<int> epath;
    void EulerCircuirt(int v);
    //implementation
    void EulerCircuirt(int v){
        for(int ed=firstG[v]; ed!=-1; ed=firstG[v]){//remove entry for each time,倒霉挨打的欧拉路
            if(es[ed].color&&es[ed].next!=-1){//swap(ed=firstG[v], es[ed].next)
                firstG[v]=es[ed].next, es[ed].next=es[firstG[v]].next, es[firstG[v]].next=ed;
                ed=firstG[v];
            }
            if(es[ed].next!=-1)assert(!es[ed].color);
            int tmp=es[ed].j;
            firstG[v]=es[ed].next;//remove the head of circuit
            EulerCircuirt(tmp);
        }
        epath.push_back(v);
    }
    //implementation of HK algorithm
    int HK(int curl){
        memset((void*)linkX, 0xff, sizeof(linkX)),
        memset((void*)linkY, 0xff, sizeof(linkY));
        int res(0);
        while(HK_bfs(curl)){
            for(int i=1; i<=m; i++){
                if(linkX[i]==-1&&HK_dfs(i, curl)) res++;
            }
        }
        //please remove the match edge from inext sets.
        for(int i=1; i<=m; i++){
            int t=linkX[i], from=(curl-1)*m+i, to=curl*m+t;//remove (curl, i)->(curl+1, t)
            int pre=-1, ed=firstI[from];
            for(;ed!=-1; pre=ed, ed=inext[ed].next){
                if(inext[ed].j==to) break;
            }
            assert(inext[ed].j==to);//must exist
            if(pre==-1) firstI[from]=inext[ed].next;
            else inext[ed].next=inext[ed].next;
        }
        return res;
    }
    bool HK_bfs(int curl){
        int top=0, size=0; bool found=false;
        for(int i=1; i<=m; 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=firstI[(curl-1)*m+v]; ed!=-1; ed=inext[ed].next){
                if(!distY[inext[ed].j-curl*m]){
                    distY[inext[ed].j-curl*m]=distX[v]+1;
                    if(linkY[inext[ed].j-curl*m]==-1) found=true;
                    else distX[linkY[inext[ed].j-curl*m]]=distX[v]+2, queue[size++]=linkY[inext[ed].j-curl*m];
                }
            }
        }
        return found;
    }
    bool HK_dfs(int v, int curl){
        for(int ed=firstI[(curl-1)*m+v]; ed!=-1; ed=inext[ed].next){
            if(distY[inext[ed].j-curl*m]==distX[v]+1){
                distY[inext[ed].j-curl*m]=0;
                if(linkY[inext[ed].j-curl*m]==-1||HK_dfs(linkY[inext[ed].j-curl*m], curl)){
                    linkX[v]=inext[ed].j-curl*m, linkY[inext[ed].j-curl*m]=v; return true;
                }
            }
        }
        return false;
    }
    //implementation
    void clr(){
        eid=0, nid=0, memset((void*)firstI, 0xff, sizeof(firstI)),
        memset((void*)firstG, 0xff, sizeof(firstG));
    }
    void nextInner(int p, int n){
        inext[nid].i=p, inext[nid].j=n;
        inext[nid].next=firstI[p], firstI[p]=nid; nid++;
    }
    void addREdge(int end, int start, bool color){//end->start, reverse starting inEdge.
        es[eid].i=start, es[eid].j=end;
        es[eid].visited=false, es[eid].color=color;
        es[eid].next=firstG[start], firstG[start]=eid; eid++;
    }
    void createEuler(){
        createOutTree(), addLeft();//外向树的生成逻辑以及添边生成全边欧拉回路
    }
    void createOutTree(){
        for(int i=1; i<=m; i+=2)
      addREdge(0, i, true);//0->(1, 2i+1)
        addREdge(n*m+1-m, n*m+1, true);//0, (1…m), (nm-m+1…nm), nm+1
        for(int i=1; i<n; i++){//for perfect-match of i layer -> i+1 layer.
            assert(HK(i)==m);//previous level
            for(int j=1; j<=m; j++){
       if(j&0x1){
        addREdge((i-1)*m+j, i*m+linkX[j], true);//must remove edge.
        addREdge((i-1)*m+j, (i-1)*m+j+1, true);//inner ropes. 1->2, 3->4…
       }
       else{//j is even
        addREdge(i*m+linkX[j], (i-1)*m+j, false);//must remove edge.
        addREdge((i-1)*m+j, (i-1)*m+(j+1)%m, false);//inner ropes. 1->2, 3->4…
       }
            }
        }
        for(int j=1; j<=m; j+=2) addREdge((n-1)*m+j, (n-1)*m+j+1, true);//left n layer
     for(int j=2; j<=m; j+=2) addREdge((n-1)*m+j, (n-1)*m+(j+1)%m, false);
    }
    void addLeft(){
        for(int i=2; i<=m; i+=2)
      addREdge(i, 0, false);//(1, i)->0
        for(int i=2; i<=m; i++){//for (n, i)->nm
            if(i&0x1) addREdge((n-1)*m+i, n*m+1, false);
            else addREdge(n*m+1, (n-1)*m+i, false);
        }
        for(int i=1; i<n; i++){//(i,x)->(i+1,linkX[x])
            for(int p=1; p<k; p++){//left k-1 time -> 2*p
                assert(HK(i)==m);
                if(p&0x1){
                    for(int q=1; q<=m; q++) addREdge(i*m+linkX[q], (i-1)*m+q, false);
                }
                else{
                    for(int q=1; q<=m; q++) addREdge((i-1)*m+q , i*m+linkX[q], false);
                }
            }
        }
    }
    #define fbase
    int main()
    {
    #ifdef fbase
        ifstream in("input.txt");
        if(!in) return EXIT_FAILURE;
        cin.rdbuf(in.rdbuf());
    #endif
        //implementation
        int ncase, icase=1, nx, lines, line;
        cin>>ncase;
        for(;icase<=ncase; icase++){
            cin>>n>>m>>k; clr();
            for(int i=1; i<n; i++){//take care of id for inner edge.
                for(int j=1; j<=m; j++){//start with k=0 to m-1, (i, j)
        for(int pk=0; pk<k; pk++){
         cin>>nx;
         nextInner((i-1)*m+j, i*m+nx);
        }
                }
            }
      lines=2*m*(n*k-k+n+2);
            if((m&0x1)==0&&(k&0x1)){
                createEuler();
                epath.clear(), EulerCircuirt(0);
       int x, y;
                cout<<"Case "<<icase<<": Yes"<<endl;
                vector<int>::iterator start=epath.begin(); start++;
       assert(lines/2==epath.size()-1);
                for(;start!=epath.end();start++){
        if(*start==0) cout<<0<<" "<<0<<endl;
        else if(*start==n*m+1) cout<<(n+1)<<" "<<0<<endl;
        else{//*start
         x=(*start-1)/m+1, y=*start-((*start-1)/m)*m;
         cout<<x<<" "<<y<<endl;
        }
                }
       start=epath.begin(), start++;
                for(;start!=epath.end();start++){
        if(*start==0) cout<<0<<" "<<0<<endl;
        else if(*start==n*m+1) cout<<(n+1)<<" "<<0<<endl;
        else{//*start
         x=(*start-1)/m+1, y=*start-((*start-1)/m)*m;
         cout<<x<<" "<<y%m+1<<endl;
        }
       }
            }
            else{
                cout<<"Case "<<icase<<": No"<<endl;
            }
        }
    #ifdef fbase
        in.close();
    #endif
     system("pause");
        return 0;
    }
    #undef fbase
    PS:实在不甘心,最后两道题目写出来结果遭两个WA,郁闷倒了!怎么办?继续研究,还是放弃,相当不甘心.
    一边回顾整理简历保持编码量的同时,再研究下落下的题目吧!数了数.
    图论里面:
    • 4个WA[这道,上道,漆门,水平可见].
    • 1个RLE(the rock).
    • 一道Messenger没有数据没有做,一道超级翻转没有数据没有做.
    搜索里面:
    • L-Game的预处理比较复杂,没有做.
    • Besty DP没有实现.
    • 还有道水题冠军篮球赛[被湖人那么弱的表现气到球了!]
    勉勉强强算把黑书和<实用>的动规,搜索以及图论部分结束了,可以开始整理简历和做BOP review和面试的白纸编程了.有了这些基础,我想应该要轻松多了吧!但代码量不能减少,应该再大一点.这样才能保持好状态.
    I’ll be back soon!

    图论的综合题

    Leave a comment

    • 终于走到最后一个部分了。先回顾下自己在图论部分学习到的知识点,然后将最后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;
      }
     }
    }

    无题

    Leave a comment

    • 二分的残留题目:
    1,Cupid’ puzzle:一个和几何[我最讨厌的类型]相关的题目,带权二分图
    要提下线段的处理:可以用三维方阵来处理,然后分别判断x,y的关系,也可以用距离处理,但距离处理有精度丢失.
    代码实现如下:
    #include <iostream>
    #include <fstream>
    #include <math.h>
    #include <string>
    #include <map>
    using namespace std;
    const int MAXN=30, MAX2N=60, MAXE=900;
    typedef struct Edge{
        int i, j, next, w;
    }Edge;
    typedef struct Point{
        int x, y;
    }Point;
    Edge es[MAXE];
    Point ps[MAX2N];
    int first[MAXN], link[MAXN], lx[MAXN], rx[MAXN], wt[MAXN][MAXN]={0}, dis[MAXN][MAXN]={0};
    bool l[MAXN], r[MAXN];
    int k, n, eid=0; char na[MAXN];
    //declaration
    void addEdge(int ix, int iy, int w);
    inline char* toUpper(char* str);
    void KM();
    bool find(int v);
    void adjust();
    //implementation
    void addEdge(int ix, int iy, int w){
        es[eid].i=ix, es[eid].j=iy, es[eid].w=w;
        es[eid].next=first[ix], first[ix]=eid; eid++;
    }
    inline char* toUpper(char* str){
        int slen=strlen(str);
        char* pstr=str;
        for(int i=0; i<slen; i++) str[i]&=0xdf;
        return pstr;
    }
    void KM(){
        //for lx, and rx vertex point
        memset((void*)lx, 0, sizeof(lx)), memset((void*)rx, 0, sizeof(rx));
        memset((void*)link, 0xff, sizeof(link));
        for(int i=0; i<n; i++){
            int maxx=INT_MIN;
            for(int eid=first[i]; eid!=-1; eid=es[eid].next){
                if(es[eid].w>maxx) maxx=es[eid].w;
            }
            lx[i]=maxx;
        }
        for(int i=0; i<n; i++){
            memset((void*)l, 0, sizeof(l)), memset((void*)r, 0, sizeof(r));
            while(!find(i)){
                adjust();
                memset((void*)l, 0, sizeof(l)), memset((void*)r, 0, sizeof(r));
            }
        }
    }
    bool find(int v){
        l[v]=true;
        for(int eid=first[v]; eid!=-1; eid=es[eid].next){
            if(!r[es[eid].j]&&lx[v]+rx[es[eid].j]==es[eid].w){
                r[es[eid].j]=true;
                if(link[es[eid].j]==-1||find(link[es[eid].j])){
                    link[es[eid].j]=v; return true;
                }
            }
        }
        return false;
    }
    void adjust(){
        int minx=INT_MAX;
        for(int i=0; i<n; i++){
            if(l[i]){
                for(int eid=first[i]; eid!=-1; eid=es[eid].next){
                    if(!r[es[eid].j]) minx=min(minx, lx[i]+rx[es[eid].j]-es[eid].w);
                }
            }
        }
        for(int i=0; i<n; i++){
            if(l[i]) lx[i]=lx[i]-minx;
            if(r[i]) rx[i]=rx[i]+minx;
        }
    }
    #define fbase
    int main()
    {
    #ifdef fbase
        ifstream in("cupid.in8");
        if(!in) return EXIT_FAILURE;
        cin.rdbuf(in.rdbuf());
    #endif
        //implementation
        map<string, int> dic;
        int px, py; bool exist;
        cin>>k>>n;
        for(int i=0; i<(n<<1); i++){
            memset((void*)na, 0, sizeof(na));
            cin>>ps[i].x>>ps[i].y>>na;
            dic[toUpper(na)]=i;
        }
        for(int i=0; i<n; i++){//O(n^2)
            for(int j=n; j<(n<<1); j++)
                dis[i][j]=dis[j][i]=(ps[i].x-ps[j].x)*(ps[i].x-ps[j].x)+(ps[i].y-ps[j].y)*(ps[i].y-ps[j].y);
        }
        memset((void*)first, 0xff, sizeof(first)), eid=0;//clr for graph
        memset((void*)wt, 0, sizeof(wt));
        memset((void*)na, 0, sizeof(na));
        cin>>na;
        do{
            px=dic[toUpper(na)];
            memset((void*)na, 0, sizeof(na));
            cin>>na; py=dic[toUpper(na)];
            cin>>wt[px][py]; wt[py][px]=wt[px][py];
            memset((void*)na, 0, sizeof(na));
            cin>>na;
        }while(strcmp(toUpper(na), "END")!=0);
        //KM algorithm to get sum of w
        int value;
        for(int i=0; i<n; i++){
            for(int j=n; j<2*n; j++){//i->j
                if(dis[i][j]<=k*k){//less than k
                    exist=false;
        for(int p=0; p<2*n; p++){
            if(i!=p&&j!=p){
                            value=ps[i].x*ps[j].y+ps[j].x*ps[p].y+ps[p].x*ps[i].y-ps[p].x*ps[j].y-ps[i].x*ps[p].y-ps[j].x*ps[i].y;
                            if(value==0){
                                if(ps[i].y!=ps[j].y){
                                    if(ps[p].y>ps[i].y&&ps[p].y<ps[j].y) exist=true;
                                    else if(ps[p].y<ps[i].y&&ps[p].y>ps[j].y) exist=true;
                                }
                                else{
                                    if(ps[p].x>ps[i].x&&ps[p].x<ps[j].x) exist=true;
                                    else if(ps[p].x<ps[i].x&&ps[p].x>ps[j].x) exist=true;
                                }
                            }
            }
                    }//for
                    if(!exist) addEdge(i, j-n, wt[i][j]==0?1:wt[i][j]);
                }
            }
        }
        KM();
        int tw=0;
        for(int i=0; i<n; i++){
            if(link[i]!=-1){
                for(int eid=first[link[i]]; eid!=-1; eid=es[eid].next){
                    if(es[eid].j==i) tw+=es[eid].w;
                }
            }
        }
        cout<<tw<<endl;
    #ifdef fbase
        in.close();
    #endif
        return 0;
    }
    #undef fbase
    2,1325 Machine Schedule,最小覆盖问题,HK做掉的[其实简单的匈牙利就行,出来的结果也比较在情理中,结构多了,反而没有dfs的快]
    只是ACM的有些题目确实让人觉得很郁闷,输入描述的莫名其妙.

    Source Code

    Problem: 1325 User: orlando22
    Memory: 300K Time: 32MS
    Language: C++ Result: Accepted

    Source Code

    #include <iostream>
    
    //pku 1325, zju 1364 machine schedule
    using namespace std;
    const int MAXN=101, MAXE=10001;
    typedef struct Edge{
        int i, j, next;
    }Edge;
    Edge es[MAXE];
    int eid=0, firstX[MAXN], linkX[MAXN], linkY[MAXN], distX[MAXN], distY[MAXN], nX, nY, k;
    int queue[MAXN*2];
    
    //declaration
    bool HK_dfs(int u);
    bool HK_bfs();
    void addEdge(int i, int j);
    
    //implementation
    void addEdge(int i, int j){
        es[eid].i=i, es[eid].j=j;
        es[eid].next=firstX[i], firstX[i]=eid; eid++;
    }
    
    //HK algorithgm
    bool HK_bfs(){
        bool found=false;
        int top=0, size=0;
        for(int i=0; i<nX; 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 eid=firstX[v]; eid!=-1; eid=es[eid].next){
                if(!distY[es[eid].j]){
                    distY[es[eid].j]=distX[v]+1;
                    if(linkY[es[eid].j]==-1) found=true;
                    else distX[linkY[es[eid].j]]=distY[es[eid].j]+1, queue[size++]=linkY[es[eid].j];
                }
            }
        }
        return found;
    }
    bool HK_dfs(int v){
        for(int eid=firstX[v]; eid!=-1; eid=es[eid].next){
            if(distY[es[eid].j]==distX[v]+1){
                distY[es[eid].j]=0;
                if(linkY[es[eid].j]==-1||HK_dfs(linkY[es[eid].j])){
                    linkY[es[eid].j]=v, linkX[v]=es[eid].j; return true;
                }
            }
        }
        return false;
    }
    
    int main()
    {
        //implementation
        int x, y, c;
        while(cin>>nX&&nX){
    	cin>>nY>>k;
            memset((void*)firstX, 0xff, sizeof(firstX)),
            memset((void*)linkX, 0xff, sizeof(linkX)),
            memset((void*)linkY, 0xff, sizeof(linkY)), eid=0;
            for(int i=0; i<k; i++){
                cin>>c>>x>>y;
                if(x!=0&&y!=0) addEdge(x, y);
            }
            int res(0);
            while(HK_bfs()){
                for(int i=0; i<nX; i++){
                    if(linkX[i]==-1&&HK_dfs(i)) res++;
                }
            }
            cout<<res<<endl;
        }
        return 0;
    }

    3,UVA 10276 [ZJU 1239] — Hanoi Tower Troubles Again! :还是二分,模型明显,潜在的终止条件有点隐晦:当剩余的无匹配项大于m的柱子数时,可以终止循环。记录其中k[匹配数]+m[柱子数]=n[球数]的最大合理数即可。建图可以使用递归的办法,把当前的n数加到前面的i,并且能使得n+i为完全平方数。注意:二分的MAXNUM大概是m的平方估算既可

    下面是二分的代码实现:但50的时候还是超时,所以可以用公式直接过,当然这是题目的特殊性造成的,二分建图才是关键所在
    #include <iostream>
    #include <math.h>
    //uva 10276, zju 1239
    using namespace std;
    const int MAXN=51, MAXE=2000000, MAXNUM=1400;//搞到1点过,结果发现是MAXNUM开小了
    typedef struct Edge{
     int i, j, next;
    }Edge;
    Edge es[MAXE];
    int eid=0, firstX[MAXNUM], linkX[MAXNUM], linkY[MAXNUM], n, m, distX[MAXNUM], distY[MAXNUM], queue[MAXNUM];
    //declaration
    void clr();
    void addEdge(int i, int j);
    int HK_Match();
    bool HK_bfs();
    bool HK_dfs(int v);
    //implementation
    void clr(){
     eid=0, memset((void*)firstX, 0xff, sizeof(firstX));
    }
    void addEdge(int i, int j){
     es[eid].i=i, es[eid].j=j;
     es[eid].next=firstX[i], firstX[i]=eid; eid++;
    }
    int HK_Match(){
     memset((void*)linkX, 0xff, sizeof(linkX)),memset((void*)linkY, 0xff, sizeof(linkY));
     int res(0);
     while(HK_bfs()){
      for(int i=1; i<=n; 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=1; i<=n; i++){
      if(linkX[i]==-1) queue[size++]=i;
      distX[i]=0;
     }
     memset((void*)distY, 0, sizeof(distY));
     for(;top<size;top++){
      int u=queue[top];
      for(int ed=firstX[u]; ed!=-1; ed=es[ed].next){
       if(!distY[es[ed].j]){
        distY[es[ed].j]=distX[u]+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(linkY[es[ed].j])){
        linkX[v]=es[ed].j, linkY[es[ed].j]=v;
        return true;
       }
      }
     }
     return false;
    }
    int main()
    {
     //implementation
     int ncase, value, preV=0, num=0;
     cin>>ncase;
     while(ncase–){
      cin>>m; preV=0;
      clr();
      for(n=1;;n++){//n->1
       num=0;
       for(int i=1; i<n; i++){
        value=sqrt((double)(n+i));
        if(value*value==n+i){
         addEdge(i, n);
        }
       }
       //to find maxMatch
       value=HK_Match();
       for(int i=1; i<=n; i++){
        if(linkX[i]==-1) num++;
       }
       if(n>m&&num>m) break;
       if(value+m==n) preV=n;
      }
      cout<<preV<<endl;
     }
     return 0;
    }
    公式的实现代码略去,f(n)=floor(n^2/2+n/2-1/2);
     
    4,IPSC 2001 — Magic:题目分析倒是很清楚,写的代码要注意流程处理:
    • DFS的年历回溯,生成C(n, (n+1)/2)的所有组合,然后用一个小的回溯来生成C(n, (n-1)/2)的组合。这里用了一个map来处理看对边是否已经存在,写代码的时候没经过大脑,结果map存在选项的时候直接把yid修改了,还好这是唯一的bugs.相当不应该就是了。
    • 匹配可以迅速搞定,但假设严格按照匹配的原始定义,我就还需要做一个C(n, (n-1)/2)和C(n, (n+1)/2)的比较,n^2.所以在添边的时候把去掉的点放在结构体,然后再匹配中用一个辅助结构来处理匹配边对应的去掉点边的eid索引,然后可以在n内可以搞定了。
    • 困惑:map的时候我是用了一个qsort来保证生成int key的唯一性的,在17的上限条件下,程序还是可以的,有更好的办法么?哪位感兴趣,可以给我提点好的建议哈!先谢!
    • 一点思考:如何用构造法来做呢?数学太差,惭愧中![改天再想]
    下面是完整的程序[IPSC上的思路,上面有构造法的解答]代码太长了,要反思,尤其是DFS判断逻辑的时候。看数据的上限大概是15,弱了!
    #include <iostream>
    #include <fstream>
    #include <vector>
    #include <map>
    //IPSC 2001 Magic, max of N is 17.
    using namespace std;
    const int MAXN=7000, MAXE=49000000, MAXNUM=17;
    typedef struct Edge{
        int i, j, mid, next;
    }Edge;
    Edge es[MAXE];
    vector<int> X[MAXN], Y[MAXN];//clear for each time.
    map<int, int> toES;//for all
    int eid=0, xid=0, yid=0, n, k, num, firstX[MAXN], distX[MAXN], distY[MAXN], linkX[MAXN], linkY[MAXN], queue[MAXN];
    int linkXE[MAXN], linkYE[MAXN];
    int lis[MAXNUM], order[MAXNUM];
    //declaration
    int inline Combine(int n, int m);
    void dfs(int d);//d->0…k-1, k to collect data.
    void clr();
    void addEdge(int i, int j, int mid);
    int HK();
    bool HK_bfs();
    bool HK_dfs(int v);
    int cmp(const void* p1, const void* p2);
    //implementation
    int inline Combine(int n, int m){
        assert(n>=m&&n>0&&m>=0);
        if(m==0) return 1;
        return n/m*Combine(n-1, m-1);
    }
    void clr(){
        eid=0, xid=0, yid=0;
        memset((void*)firstX, 0xff, sizeof(firstX));
        for(int i=0; i<n; i++) lis[i]=i+1;
        for(int i=0; i<MAXN; i++) X[i].clear(), Y[i].clear();
        toES.clear();
    }
    void dfs(int d){//d==k terminate.
        if(d==num){//get out of X, Y vector
            for(int i=0; i<num; i++) X[xid].push_back(lis[i]);
            for(int i=0, key=0, pyid=-1; i<num; i++){//swap lis[k-1] with lis[i]
                key=0;
                if(i!=num-1) lis[i]^=lis[num-1], lis[num-1]^=lis[i], lis[i]^=lis[num-1];
                memcpy((void*)order, (void*)lis, sizeof(int)*(num-1));
                qsort((void*)order, num-1, sizeof(int), cmp);//dummy implementation for hashtable
                for(int j=0; j<num-1; j++) key+=key*10+order[j];
                if(toES.find(key)!=toES.end()){//here : yid can’t be modify, if no-entry has been inserted.
                    pyid=toES[key], addEdge(xid, pyid, lis[num-1]);
                }
                else{
                    toES[key]=yid;//find the toES[key]’s es id.
                    for(int j=0; j<num-1; j++) Y[yid].push_back(order[j]);
                    addEdge(xid, yid, lis[num-1]), yid++;
                }
                //keep eid as mid in inneral logic of addEdge.
                if(i!=num-1) lis[i]^=lis[num-1], lis[num-1]^=lis[i], lis[i]^=lis[num-1];
            }
            xid++;//increase xid..
            return;
        }
        for(int i=d; i<n; i++){
            if(d==0||lis[d-1]<lis[i]){//lis[0…n-1] has no-duplicate elements
                if(d!=i) lis[d]^=lis[i], lis[i]^=lis[d], lis[d]^=lis[i];
                dfs(d+1);
                if(d!=i) lis[d]^=lis[i], lis[i]^=lis[d], lis[d]^=lis[i];
            }
        }
    }
    int cmp(const void* p1, const void* p2){//p1 in the back
        return *((int*)p1)>*((int*)p2);
    }
    void addEdge(int i, int j, int mid){
        es[eid].i=i, es[eid].j=j, es[eid].mid=mid;//missing number
        es[eid].next=firstX[i], firstX[i]=eid; eid++;
    }
    int HK(){
        memset((void*)linkX, 0xff, sizeof(linkX)), memset((void*)linkY, 0xff, sizeof(linkY));//xid
        int res(0);
        while(HK_bfs()){
            for(int i=0; i<xid; i++)
                if(linkX[i]==-1&&HK_dfs(i)) res++;
        }
        return res;
    }
    bool HK_bfs(){
        int top=0, size=0;
        for(int i=0; i<xid; i++){
            if(linkX[i]==-1) queue[size++]=i;
            distX[i]=0;
        }
        memset((void*)distY, 0, sizeof(distY));
        bool found=false;
        for(;top<size;top++){
            int v=queue[top];
            for(int ed=firstX[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=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(linkY[es[ed].j])){//modify logic here!
                    linkX[v]=es[ed].j, linkY[es[ed].j]=v;//standard
                    linkXE[v]=ed, linkYE[es[ed].j]=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
        int ncase;
        cin>>ncase;
        while(ncase–){
            cin>>n;
            if(!(n&0x1)){cout<<-1<<endl; continue;}
            num=(n+1)/2, k=Combine(n, num);//n is odd judgement
            clr(),dfs(0);//construct graph
            int res=HK();
            assert(res==xid&&xid==yid);//perfect match assertion
            //for output
            for(int i=0; i<xid/*yid*/; i++){
                assert(linkY[i]!=-1);
                for(vector<int>::iterator p=Y[i].begin(); p!=Y[i].end(); p++){
                    cout<<(*p)<<" ";//PE error
                }
                cout<<"-> ";
                cout<<es[linkYE[i]].mid<<endl;
            }
        }
    #ifdef fbase
        in.close();
    #endif
        return 0;
    }
    #undef fbase
     
    •  最大流的残留题目:一道让人看着比较茫然的题目,黑书描述的更让人茫然。[解后的感觉是又是一个多维变量,枚举转化的思路]

    想了下,T作为变参来枚举状态即可。把每个太空站在T时刻的状态作为图结点,进而将太空船的转移作为边;由于可以留在太空站上,所以从(i,T-1)->(i,T)也是一个状态转化边。剩下就是Dicnic算法求解。题目描述和代码实现附上。

    家  园

    由于人类对自然的疯狂破坏,人们意识到在大约2300年之后,地球不能再居住了,于是在月球上建立了新的绿地,以便在需要时移民。令人意想不到的是,2177年冬由于未知的原因,地球环境发生了连锁崩溃,人类必须在最短的时间内迁往月球。
    现有n个太空站处于地球与月球之间(编号1..n),m艘公共交通太空船在其中来回穿梭,每个太空站Si可容纳无限的人,每艘太空船pi只可容纳Hpi人。对于每一艘太空船pi,将周期性地停靠一系列的太空站(Si1,Si2…Sir),如:(1,3,4)表示停靠太空站1 3 4 1 3 4 1 3 4 …。 任一艘太空船从任一个太空站驶往另一个任意的太空站耗时为1。人只能在太空船停靠太空站(或地球、月球)时上船或下船。初始时的人全在地球上,太空船全在初始站(太空船pi处于Si1),目标是让所有的人尽快地全部转移到月球上。
    输入:
    文件第一行为三个正整数 n(太空站个数)、 m(太空船个数)、 k(需要运送的地球上的人的个数),其中 1<=m<=13, 1<=n<=20, 1<=k<=50。
    接下来的n行给出了太空船的信息,第i+1行说明太空船pi,此行第一个数表示pi可容纳的人数Hpi,第二个数表示pi停靠一个周期的太空站个数r,1<=r<=n+2, 随后r个数便是停靠的太空站的编号(Si1,Si2,…,Sir), 地球用0表示,月球用-1表示。0时刻时,所有太空船都在初始站,随后开始运行,在时刻1,2,3…等正点时刻各艘太空船停靠相应的太空站,即人只有在0,1,2…等正点时刻才能上下太空船。
    输出:
        文件只有一个数,若问题有解,输出完成全部人员安全转移的时刻,否则输出0。
    输入输出示例:      
    输入文件:2 2 1  //m=2, n=2                         
              1 3 0 1 2
              1 3 1 2 –1
    输出文件:5

    代码实现:Dicnic有点忘记了,唉!
    // Homeland.cpp : Defines the entry point for the console application.
    //
    #include "stdafx.h"
    #include <iostream>
    #include <fstream>
    #include <vector>
    #include <assert.h>
    #include <stdlib.h>
    //CTSC 1999 homeland
    using namespace std;
    const int MAXT=1000, MAXSN=21000, MAXSE=42000, MAXM=13;
    //mapping (i, t)->mt+i
    typedef struct Edge{
        int i, j, next, op, f, c;
    }Edge;
    Edge es[MAXSE];
    int m, n, k, first[MAXSN], eid=0, pre[MAXSN], firstc[MAXSN], queue[MAXSN], ptr[MAXSN], cur[MAXM], cap[MAXM];
    vector<int> ship[MAXM];
    bool visited[MAXSN];
    //declaration
    void clr();
    void addEdge(int start, int end, int cap);
    //implementation
    void clr(){
        eid=0, memset((void*)first, 0xff, sizeof(first));
        memset((void*)cur, 0, sizeof(cur));//start 0
    }
    void addEdge(int start, int end, int cap){
        assert(eid<MAXSE);
        if(!cap) return;
        es[eid].i=start, es[eid].j=end, es[eid].f=0, es[eid].c=cap;
        es[eid].next=first[start], first[start]=eid, es[eid].op=eid+1; eid++;
        es[eid].i=end, es[eid].j=start, es[eid].f=0, es[eid].c=-1;
        es[eid].next=first[end], first[end]=eid, es[eid].op=eid-1; eid++;
    }
    //maxflow algorithm
    int Dicnic(int sv, int st);
    void bfslevel(int sv, int st);
    void dfsflow(int sv, int st);
    //implementation
    int Dicnic(int sv, int st){
        int maxflow=0;
        while(true){
            bfslevel(sv, st);
            if(pre[st]==INT_MAX) break;
            dfsflow(sv, st);
        }
        for(int ed=first[sv]; ed!=-1; ed=es[ed].next){
            if(es[ed].c>0) maxflow+=es[ed].f;
        }
        return maxflow;
    }
    void bfslevel(int sv, int st){
        assert(sv<st);
        for(int i=sv; i<=st; i++) pre[i]=INT_MAX;
        int top=0, size=0;
        pre[sv]=sv, queue[size++]=sv;
        for(;top<size;top++){
            int v=queue[top];
      if(v==st) return;
            for(int ed=first[v]; ed!=-1; ed=es[ed].next){
                if(pre[es[ed].j]>pre[v]+1){//in the residental graph
                    if(es[ed].c>es[ed].f||(es[ed].c==-1&&es[ed].f>0)){
                        queue[size++]=es[ed].j, pre[es[ed].j]=pre[v]+1;
                    }
                }
            }
        }
    }
    void dfsflow(int sv, int st){
        memset((void*)ptr, 0, sizeof(ptr)), memset((void*)visited, 0, sizeof(visited));
        memcpy((void*)firstc, (void*)first, sizeof(first));
        int top=0; queue[top]=sv;
        while(top>-1){
            if(queue[top]==st){
                int fmin=INT_MAX, tj=-1, value;
                for(int j=top; j>0; j–){
                    if(es[ptr[queue[j]]].c>es[ptr[queue[j]]].f){
                        if((value=es[ptr[queue[j]]].c-es[ptr[queue[j]]].f)<fmin) fmin=value;
                    }
                    if(es[ptr[queue[j]]].c==-1&&es[ptr[queue[j]]].f>0){
                        if((value=es[ptr[queue[j]]].f)<fmin) fmin=value;
                    }
                }
                //update
                for(int j=top; j>0; j–){
                    if(es[ptr[queue[j]]].c>es[ptr[queue[j]]].f){
                        es[ptr[queue[j]]].f+=fmin, es[es[ptr[queue[j]]].op].f+=fmin;
                        if(es[ptr[queue[j]]].f==es[ptr[queue[j]]].c) tj=j;
                    }
                    if(es[ptr[queue[j]]].c==-1&&es[ptr[queue[j]]].f>0){
                        es[ptr[queue[j]]].f-=fmin, es[es[ptr[queue[j]]].op].f-=fmin;
                        if(es[ptr[queue[j]]].f==0) tj=j;
                    }
                }
                if(tj!=-1)top=tj-1;
            }
            else{
                int tmp=firstc[queue[top]], tp=queue[top];
                for(;tmp!=-1;tmp=es[tmp].next){
                    if(!visited[es[tmp].j]&&pre[es[tmp].j]==pre[tp]+1){
                        if(es[tmp].c>es[tmp].f||(es[tmp].c==-1&&es[tmp].f>0)){
                            firstc[tp]=es[tmp].next;
                            queue[++top]=es[tmp].j, ptr[queue[top]]=tmp;//found one trip to st
                            break;
                        }
                    }
                }
                if(tmp==-1){visited[tp]=true;top–;}
            }
        }
    }
    #define fbase
    int main()
    {
    #ifdef fbase
        ifstream in("9.in");
        if(!in) return EXIT_FAILURE;
        cin.rdbuf(in.rdbuf());
    #endif
        //implementation
        int num, l, t=0, maxflow=0, pre_loc, cur_locs, tn;
        cin>>n>>m>>k;
     tn=n+2;
        for(int i=0; i<m; i++){
            cin>>cap[i]>>num;
            for(int j=0; j<num; j++){
                cin>>l;
                if(l==-1) l=n+1;
                ship[i].push_back(l);//for location check
            }
        }
        clr();
        do{
            t++;
            for(int i=0; i<m; i++){//其实只有这一段,其他都是模型求解。
                pre_loc=ship[i][cur[i]], cur_locs=ship[i][(cur[i]+1)%ship[i].size()];
                addEdge(pre_loc+tn*(t-1), cur_locs+tn*t, cap[i]);
                //modify cur[i]
                cur[i]=(cur[i]+1)%ship[i].size();
            }
      for(int i=0; i<n+3; i++)
       addEdge(i+tn*(t-1), i+tn*t, INT_MAX);
            maxflow+=Dicnic(0, n+1+tn*t);
        }while(maxflow<k&&t<MAXT);
        if(t<MAXT) cout<<t<<endl;
        else cout<<0<<endl;
    #ifdef fbase
        in.close();
    #endif
        return 0;
    }
    #undef fbase

    恢复到算法

    3 Comments

    • CTSC 2001 – Day 1 – Agent

    终极情报网

     

    【题目叙述】
    在最后的诺曼底登陆战开始之前,盟军与德军的情报部门围绕着最终的登陆地点展开了一场规模空前的情报战。
    这场情报战中,盟军的战术是利用那些潜伏在敌军内部的双重间谍,将假的登陆消息发布给敌军的情报机关的负责人。那些已经潜入敌后的间谍们都是盟军情报部的精英,忠实可靠;但是如何选择合适的人选,以及最佳的消息传递方法,才能保证假消息能够尽快而且安全准确地传递到德军指挥官们的耳朵里,成了困扰盟军情报部长的最大问题。他需要你的帮助。
     
    以下是情报部长提供的作战资料:
     
    在敌后一共潜伏着我方最优秀的N名间谍,分别用数字1, 2, …, N编号。在给定的作战时间内,任意两人之间至多只进行一次点对点的双人联系。
    我将给你一份表格,表格中将提供任意两位间谍ij之间进行联系的安全程度,用一个 [0, 1] 的实数Si j表示;以及他们这次联系时,能够互相传递的消息的最大数目,用一个正整数表示Mi j (如果在表格中没有被提及,那么间谍ij之间不进行直接联系)
    假消息从盟军总部传递到每个间谍手里的渠道也不是绝对安全,我们用 [0, 1] 的实数ASj表示总部与间谍j之间进行联系的安全程度,AMj则表示总部和间谍j之间进行联系时传递的消息的最大数目。对于不和总部直接联系的间谍,他的AMj=0(而表格中给出的他的ASj是没有意义的)。
    当然,假消息从间谍手中交到敌军的情报部官员的办公桌上的过程是绝对安全的,也即是说,间谍与敌军情报部门之间要么不进行直接联系,要么其联系的安全程度是1(即完全可靠)。
     
    现在情报部打算把K条假消息“透露”到德军那里。消息先由总部一次性发给N名间谍中的一些人,再通过他们之间的情报网传播,最终由这N名间谍中的某些将情报送到德军手中。对于一条消息,只有安全的通过了所有的中转过程到达敌军情报部,这个传递消息的过程才算是安全的;因此根据乘法原理,它的安全程度P就是从总部出发,经多次传递直到到达德军那里,每一次传递该消息的安全程度的乘积而对于整个计划而言,只有当N条消息都安全的通过情报网到达德军手中,没有一条引起怀疑时,才算是成功的。所以计划的可靠程度所有消息的安全程度的乘积显然,计划的可靠性取决于这些消息在情报网中的传递方法。
     
    我需要一个方案,确定消息应该从哪些人手中传递到哪些人手中,使得最终计划的可靠性最大。你可以利用计算机,来求得这个最可靠的消息传递方案。
     
    【输入文件】
    输入文件agent.in包含了盟军的作战资料表格。
    第一行包括两个整数NK,分别是间谍的总人数和计划包含的消息总数。
    第二行包括2N个数,前N个数是实数AS1, AS2, …, ASN(范围在[0, 1]以内);后N个数是整数AM1, AM1, …, AMN
    第三行包含了N个整数,其中第ii = 1, 2, …, N)个整数如果为0表示间谍i与德军情报部不进行联系,如果为1则表示间谍与德军情报部进行联系。
    第四行开始,每行包括4个数,依次分别是:代表间谍编号的正整数ij,间谍ij联系的安全性参数Si j[01]范围内的实数),以及ij之间传递的最大消息数 Mi j(每一行的i均小于j )。
    最后的一行包含两个整数-1  -1,表示输入数据的结束。
    0<N<3000<K<300
     
    【输出文件】
    输出文件agent.out中只有一行。这一行中包含一个实数P,给出的是整个计划的可靠程度P,保留5位有效数字(四舍五入)。
    如果情报网根本不能将K条消息传到德军手中,那么计划的可靠性为0你可以假定,如果计划存在,那么它的可靠性大于1e-12
     
    【输入输出样例】

    Agent.in
    Agent.out
    6  13
    0.9  0.7  0.8  0  0  0  2  6  8  0  0  0
    0  0  0  1  0  1
    1  4  0.5  2
    2  3  0.9  5
    2  5  0.8  2
    2  6  0.8  7
    3  5  0.8  2
    5  6  0.8  4
    -1  -1
    0.00021184
        
    代码实现如下:[注意精度控制]
    #include <iostream>
    #include <fstream>
    #include <iomanip>
    #include <math.h>
    //CTSC 2001 – Day 1 – Agent
    //0<N<300;0<K<300
    using namespace std;
    const int MAXN=301, MAXE=91000;
    typedef struct Edge{
        int i, j, next, op, f, c;
        double w;
    }Edge;
    Edge es[MAXE];
    int eid, n, k, first[MAXN], pre[MAXN], ptr[MAXN], an[MAXN];//for each input edge
    double as[MAXN], w[MAXN]/*cost*/;
    //declaration
    void addEdge(int i, int j, int c, double w);
    int expandPath(int sv, int st);
    void clr();
    //implementation
    void addEdge(int i, int j, int c, double w){
        if(!c) return;
        es[eid].i=i, es[eid].j=j, es[eid].c=c, es[eid].w=w;
        es[eid].next=first[i], first[i]=eid, es[eid].op=eid+1; eid++;
        es[eid].i=j, es[eid].j=i, es[eid].c=-1, es[eid].w=-w;
        es[eid].next=first[j], first[j]=eid, es[eid].op=eid-1; eid++;
    }
    void clr(){
        memset((void*)first, 0xff, sizeof(first)), eid=0;
    }
    int expandPath(int sv, int st){
        memset((void*)pre, 0xff, sizeof(pre));
        for(int i=1; i<=n+1; i++) w[i]=(double)INT_MAX;
        pre[sv]=sv, w[sv]=0.0;
        bool change=false;
        do{
            change=false;
            for(int i=1; i<=n+1; i++){
                for(int e=0; e<eid; e++){
                    if(pre[es[e].i]!=-1){//already exits previous node
                        if(es[e].c>es[e].f){
                            if(w[es[e].i]+es[e].w+1e-13<w[es[e].j]){
                                w[es[e].j]=w[es[e].i]+es[e].w, pre[es[e].j]=es[e].i, ptr[es[e].j]=e, change=true;
                            }
                        }
                        if(es[e].c==-1&&es[e].f>0){
                            if(w[es[e].i]+es[e].w+1e-13<w[es[e].j]){
                                w[es[e].j]=w[es[e].i]+es[e].w, pre[es[e].j]=es[e].i, ptr[es[e].j]=e, change=true;
                            }
                        }
                    }
                }
            }
        }while(change);
        if(pre[st]==-1) return 0;
        //calculate the maxflow
        int i=st, a=INT_MAX, value;
        for(;i!=sv; i=pre[i]){
            if(es[ptr[i]].c>es[ptr[i]].f){
                if((value=es[ptr[i]].c-es[ptr[i]].f)<a) a=value;
            }
            if(es[ptr[i]].c==-1&&es[ptr[i]].f>0){
                if((value=es[ptr[i]].f)) a=value;
            }
        }
        return a;
    }
    #define fbase
    int main()
    {
    #ifdef fbase
        ifstream in("AGENT.IN8");
        if(!in) return EXIT_FAILURE;
        cin.rdbuf(in.rdbuf());
    #endif
        //implementation
        int start, end, mn, a;
        double ms, sec=0.0;
        //createGraph
        cin>>n>>k;
        for(int i=1; i<=n; i++) cin>>as[i];
        for(int i=1; i<=n; i++) cin>>an[i];
        clr();
        for(int i=1; i<=n; i++){
            if(as[i]!=0&&an[i]!=0)
                addEdge(0, i, an[i], -log(as[i]));
        }
        for(int i=1; i<=n; i++){
            cin>>ms;
            if(ms==1) addEdge(i, n+1, INT_MAX, 0);
        }
        while(cin>>start>>end&&start!=-1&&end!=-1){
            cin>>ms>>mn; addEdge(start, end, mn, -log(ms)), addEdge(end, start, mn, -log(ms));
        }
        //for maxflow
        a=expandPath(0, n+1);
        while(a!=0){//for first cycle
            for(start=n+1; start!=0; start=pre[start]){
                if(es[ptr[start]].c>es[ptr[start]].f) es[ptr[start]].f+=a, es[es[ptr[start]].op].f+=a;
                if(es[ptr[start]].c==-1&&es[ptr[start]].f>0) es[ptr[start]].f-=a, es[es[ptr[start]].op].f-=a;
            }
            if(k>=a) sec+=a*w[n+1], k-=a;
            else sec+=k*w[n+1], k=0;
            a=expandPath(0, n+1);
        }
        if(k!=0) cout<<0<<endl;
        else{
            sec=exp(-sec);
            if(sec>1e-12) cout<<setprecision(5)<<showpoint<<sec<<endl;
            else cout<<0<<endl;
        }
    #ifdef fbase
        in.close();
    #endif
        return 0;
    }
    #undef fbase
    • The Grand DinnerUVA 10249,再次证明了UVA测试数据的严谨性,很简单的一个建模,编码也很简单。老是WA,想不通,但相信UVA的权威性,仔细一查,发现自己的预流标进算法实现有个问题:进行Push操作后的顶点,可能会使得L链表的前项变为存在余流,怎么办呢?两个办法,一是用queue来存储有余流的顶点,但这样所有增流操作中都要进去FIFO操作,对算导的框架有些影响;二是有Push操作就将顶点放在最前面,这样也能保证所有的U前项都是无流点;再精细一点,可以用一个数组来作为顶点在L中的索引数组,如果当前的Push操作是关于U和前项点的,就在直接提前。[后者由于引入了一个N的数组,所以访问数组的效率基本和忽视Push的冗余操作时间基本一致,下面是UVA上的数据。]汗颜,有错的代码居然作为自己的框架,唉!即使是算导也不能不加思考的照模式画萨。

    My Submissions

    #
     
    Problem
    Verdict
    Language
    Run Time
    Submission Date
    7118858
    Accepted
    C++
    0.880
    2009-05-09 16:42:40
    7118850
    Accepted
    C++
    0.904
    2009-05-09 16:40:57
    7118813
    Accepted
    C++
    0.868
    2009-05-09 16:32:13
    7118054
    Wrong answer
    C++
    0.288
    2009-05-09 11:05:05
    当然,就题目而言,最好的办法是基于完全二分图的一个贪心算法,可以杀到0.1左右的,这里主要是验证预流标进算法的实现。所以略去了,再次警示自己,三思而后行,做程序要静下心来,尤其是框架算法切不可草率,这种模型算法错框架,就等于没做了
    #include <iostream>
    #include <fstream>
    //UVA 10249 The Grand Dinner
    using namespace std;
    const int MAXN=130, MAXE=7400;
    typedef struct Edge{
        int i, j, next, op, f, c;
    }Edge;
    Edge es[MAXE];
    int m, n, eid, first[MAXN], hv[MAXN], ev[MAXN], l[MAXN], in[MAXN];
    //declaration
    void initialGraph();
    void addEdge(int i, int j, int c);
    bool discharge(int v);
    bool push(int eid);
    bool relabel(int v);
    void Hpreflow();
    void clr();
    //implementation
    void clr(){
        eid=0, memset((void*)first, 0xff, sizeof(int)*(n+m+2));
    }
    void addEdge(int i, int j, int c){
        if(!c) return;
        es[eid].i=i, es[eid].j=j, es[eid].f=0, es[eid].c=c;
        es[eid].next=first[i], first[i]=eid, es[eid].op=eid+1; eid++;
        es[eid].i=j, es[eid].j=i, es[eid].f=0, es[eid].c=-1;
        es[eid].next=first[j], first[j]=eid, es[eid].op=eid-1; eid++;
    }
    void initalGraph(){
        memset((void*)l, 0xff, sizeof(int)*(n+m+2));
        for(int i=0; i<n+m; i++) l[i]=i+1, in[i+1]=i;
        memset((void*)hv, 0, sizeof(int)*(n+m+2)), memset((void*)ev, 0, sizeof(int)*(n+m+2));
        hv[0]=m+n+1;
        for(int e=first[0]; e!=-1; e=es[e].next){
            if(es[e].c>0){
                es[e].f+=es[e].c, es[es[e].op].f+=es[e].c;
                ev[0]-=es[e].c, ev[es[e].j]+=es[e].c;
            }
        }
    }
    void Hpreflow(){
        initalGraph();
        int pos=0, u=l[pos];
        while(u!=-1){
            if(discharge(u)){//higher算导基础上的改进
                if(pos!=0){
                    in[l[0]]^=in[u], in[u]^=in[l[0]], in[l[0]]^=in[u];//自己做的索引数组
                    l[0]^=l[pos], l[pos]^=l[0], l[0]^=l[pos];

                }
                pos=0;
            }
            u=l[++pos];//next position
        }
    }
    bool relabel(int v){
        if(ev[v]<=0) return false;//here:bug
        int hmin=INT_MAX; bool tlabel=true;
        for(int e=first[v]; e!=-1; e=es[e].next){//in the residental graph
            if(es[e].c>es[e].f||(es[e].c==-1&&es[e].f>0)){
                if(hmin>hv[es[e].j]) hmin=hv[es[e].j];
                if(hv[es[e].j]<hv[v]) tlabel=false;
            }
        }
        if(tlabel){
            hv[v]=hmin+1; return true;
        }
        return false;
    }
    bool push(int eid){//first check is adminsiable-edge
        if(ev[es[eid].i]<=0||hv[es[eid].i]!=hv[es[eid].j]+1) return false;
        int flow=ev[es[eid].i];
        if(es[eid].c>es[eid].f){
            if(flow>(es[eid].c-es[eid].f)) flow=es[eid].c-es[eid].f;
            es[eid].f+=flow, es[es[eid].op].f+=flow;
            ev[es[eid].i]-=flow, ev[es[eid].j]+=flow;
            return true;
        }
        if(es[eid].c==-1&&es[eid].f>0){
            if(flow>es[eid].f) flow=es[eid].f;
            es[eid].f-=flow, es[es[eid].op].f-=flow;
            ev[es[eid].i]-=flow, ev[es[eid].j]+=flow;
            return true;
        }
        return false;
    }
    bool discharge(int u){
        int eid=first[u]; bool change=false;
        while(ev[u]>0){
            if(eid==-1) relabel(u), eid=first[u], change=true;//高度修改肯定要提前
            else if(hv[u]==hv[es[eid].j]+1&&(es[eid].c>es[eid].f||(es[eid].c==-1&&es[eid].f>0))){
                if(in[es[eid].j]<in[u]) change=true;//前项点的流入也需要提前,要精心和静心于代码,任何时候和情况下都不可浮躁!
                push(eid);
            }
            else eid=es[eid].next;
        }
        return change;
    }
    #define fbase
    int main()
    {
    #ifdef fbase
        ifstream in("input.txt");
        if(!in) return EXIT_FAILURE;
        cin.rdbuf(in.rdbuf());
    #endif
        int c, total, maxflow;
        //implementation
        while(cin>>m>>n&&m&&n){
            clr(); total=0, maxflow=0;
            for(int i=1; i<=m; i++){
                cin>>c, addEdge(0, i, c), total+=c;
                for(int j=n+m; j>=m+1; j–) addEdge(i, j, 1);
            }//for i->[1…m] with source and i->j, back-insert to linklist
            for(int i=m+1; i<=n+m; i++) cin>>c, addEdge(i, n+m+1, c);
            Hpreflow();
            if(total!=ev[n+m+1]) cout<<0<<endl;
            else{//for each team
                cout<<1<<endl;
                for(int i=1; i<=m; i++){
                    for(int eid=first[i]; eid!=-1; eid=es[eid].next){
                        if(es[eid].f==1&&es[eid].c!=-1){
                            cout<<es[eid].j-m;
                            if(es[eid].next!=-1) cout<<" ";
                        }
                    }
                    cout<<endl;
                }
            }
        }
    #ifdef fbase
        in.close();
    #endif
        return 0;
    }
    #undef fbase
     
    算法分析:恩,典型的组合题,LIS加最大流。主要考虑到最大流要做拆点操作,N->2N,好像不是很好,再想下,发现贪心就可以搞定了。用vector<int> len[1…MAXLIS]将其中每一项进行升序排列,对于一个当前长度i->Len[i]而言,若前面的存在两项,都比前面的项大,那么更大的那个是最优的;因为至少都和前面的一样长,类似于活动安排的贪心分析。
    代码实现:
    Ranking Submission Run Time Language Submission Date
    50 7119938 0.008[最好的是0ms,好强的结果] C++ 2009-05-10 08:53:21
    然后,看了下牛人的时间,基本都在0.001左右,想了下,可以在排序的那块改进,用插入排序来代替len[i].push_back,但没有找到STL的模板算法;应该用自己的代码会更快,这里就省去了。
    #include <iostream>
    #include <fstream>
    #include <vector>
    //uva 10546 the eagle’s nest
    using namespace std;
    const int MAXN=101;
    int d[MAXN], lis[MAXN], n, k;//lis[0…100] for length of lis
    vector<int> len[MAXN];
    //declaration
    int cmp(const int& t1, const int& t2);
    //implementation
    int cmp(const int& t1, const int& t2){
        return d[t1]<d[t2];//if true, t1->previous
    }
    #define fbase
    int main()
    {
    #ifdef fbase
        ifstream in("input.txt");
        if(!in) return EXIT_FAILURE;
        cin.rdbuf(in.rdbuf());
    #endif
        //implementation
        string str;
        int bsize=0, l, r, mid, ncase=1;
        while(cin>>n&&n){
            for(int i=1; i<=n; i++) cin>>str>>d[i];
            d[0]=0, memset((void*)lis, 0, sizeof(lis));
            for(int i=1; i<=bsize; i++) len[i].clear();//clear for len[i] vector
            bsize=0;
            for(int i=1; i<=n; i++){
                l=0, r=bsize;
                while(l+1<r){
                    mid=l+(r-l)/2;
                    if(d[i]<=d[lis[mid]]) r=mid;
                    else l=mid;
                }
                if(d[i]<=d[lis[r]]) r=l;
                len[r+1].push_back(i);
                if(r+1>bsize)  bsize=r+1;
                if(lis[r+1]==0) lis[r+1]=i;
                else if(d[i]<d[lis[r+1]]) lis[r+1]=i;
            }
            for(int i=1; i<=bsize; i++) sort(len[i].begin(), len[i].end(), cmp);
            bool terminate=false;
            int nums=0, pre, next, cur;
            while(!terminate){
                pre=-1, next=0;
                for(int i=bsize; i>=1; i–){
                    cur=pre;
                    if(len[i].size()==0){terminate=true; break;}
                    if(pre==-1){
                        pre=d[len[i][len[i].size()-1]], len[i].pop_back(); next++;
                    }
                    else{//pre!=-1
                        for(int j=len[i].size()-1; j>-1; j–){
                            if(pre>d[len[i][j]]){ pre=d[len[i][j]], len[i].pop_back(); next++; break;}
                            len[i].pop_back();
                        }
                    }
                    if(len[i].size()==0) terminate=true;
                    if(pre==cur) break;
                }
                if(next==bsize) nums+=bsize;
            }
            cout<<"Case #"<<(ncase++)<<": "<<nums<<endl;
        }
    #ifdef fbase
        in.close();
    #endif
        return 0;
    }
    #undef fbase
     
    • pku1637 — Sightseeing tour,这又是一道模型题,混合图的欧拉回路。黑书上的描述近似于天书,IRJ的一句:“实际上就是给无向边定向”,网上的一个兄弟:“算出出度和入度之差”[由于有向欧路的出度,入度之差为偶数,0,这里少边的欧路点必然也是偶数],犯了一个错,忘记/2了;出度和入度之差是边的2倍,这点要注意,然后就是用FIFO的预流推进解最大流。忽然发现一个很简单的欧路实现,勾起了我对失败之至的欧拉回路回忆。做BOP review的时候,看怎么把那道题切掉吧,还有那道男人题。
      //代码写的很次,还是贴出来吧,为了警示自己和别人的差距还很大,加油哈!

    Source Code

    Problem: 1637 User: orlando22
    Memory: 332K Time: 79MS//先做再改吧
    Language: C++ Result: Accepted
    • Source Code
      #include <iostream>
      #include <math.h>
      
      //pku 1637, zju1992 sightseeing tour
      using namespace std;
      
      const int MAXN=202, MAXE=2400;//vertexs 200, edge 1000
      typedef struct Edge{
          int i, j, next, op, f, c;
      }Edge;
      Edge es[MAXE];
      int eid, m, s, first[MAXN], ev[MAXN], hv[MAXN], l[MAXN], head, tail;
      //helper array
      int inofv[MAXN];
      
      //declaration
      void clr();
      void addEdge(int s, int e, int c);
      void initialflow();
      void Hpreflow();
      void discharge(int v);
      bool push(int eid);
      bool relabel(int v);
      void inline EnDQ(int v);
      int inline DeDQ();
      
      //implementation
      void clr(){
          eid=0, memset((void*)first, 0xff, sizeof(first));
          memset((void*)inofv, 0, sizeof(inofv));
      }
      void addEdge(int s, int e, int c){
          if(!c) return;
          es[eid].i=s, es[eid].j=e, es[eid].f=0, es[eid].c=c;
          es[eid].next=first[s], first[s]=eid, es[eid].op=eid+1; eid++;
          es[eid].i=e, es[eid].j=s, es[eid].f=0, es[eid].c=-1;
          es[eid].next=first[e], first[e]=eid, es[eid].op=eid-1; eid++;
      }
      void Hpreflow(){
          initialflow();
          int u=DeDQ();
          while(u!=-1){
              discharge(u);
              u=DeDQ();
          }
      }
      void discharge(int v){
          int eid=first[v];
          while(ev[v]>0){
              if(eid==-1) relabel(v), eid=first[v];
              else if(hv[v]==hv[es[eid].j]+1&&(es[eid].c>es[eid].f||(es[eid].c==-1&&es[eid].f>0)))
                  push(eid);
              else eid=es[eid].next;
          }
      }
      bool relabel(int v){
          if(ev[v]<=0) return false;
          int hmin=INT_MAX; bool tlabel=true;
          for(int e=first[v]; e!=-1; e=es[e].next){
              if(es[e].c>es[e].f||(es[e].c==-1&&es[e].f>0)){
                  if(hv[es[e].j]<hmin) hmin=hv[es[e].j];
                  if(hv[es[e].j]<hv[v]) tlabel=false;
              }
          }
          if(tlabel){
              hv[v]=hmin+1; return true;
          }
          return false;
      }
      bool push(int eid){
          if(ev[es[eid].i]<=0||hv[es[eid].i]!=hv[es[eid].j]+1) return false;
          int flow=ev[es[eid].i];
          if(es[eid].c>es[eid].f){
              if(es[eid].c-es[eid].f<flow) flow=es[eid].c-es[eid].f;
              es[eid].f+=flow, es[es[eid].op].f+=flow;
              ev[es[eid].i]-=flow, ev[es[eid].j]+=flow;
              if(ev[es[eid].j]>0) EnDQ(es[eid].j);
              return true;
          }
          if(es[eid].c==-1&&es[eid].f>0){
              if(es[eid].f<flow) flow=es[eid].f;
              es[eid].f-=flow, es[es[eid].op].f-=flow;
              ev[es[eid].i]-=flow, ev[es[eid].j]+=flow;
              if(ev[es[eid].j]>0) EnDQ(es[eid].j);
              return true;
          }
          return false;
      }
      void initialflow(){//for ev, hv, and l
          memset((void*)ev, 0, sizeof(ev)), memset((void*)hv, 0, sizeof(hv));
          head=tail=0;
          hv[0]=m+2;
          for(int eid=first[0]; eid!=-1; eid=es[eid].next){
              if(es[eid].c>0){
                  es[eid].f+=es[eid].c, es[es[eid].op].f+=es[eid].c;
                  ev[0]-=es[eid].c, ev[es[eid].j]+=es[eid].c;
                  EnDQ(es[eid].j);
              }
          }
      }
      void inline EnDQ(int v){
          if(v==0||v==m+1) return;
          if((tail+1)%m==head) return;
          tail=(tail+1)%m;
          l[tail]=v;
      }
      int inline DeDQ(){
          if(tail==head) return -1;
          head=(head+1)%m;
          return l[head];
      }
      
      int main()
      {
          //implementation
          int ncase, a, b; bool single, possible;
          cin>>ncase;
          while(ncase--){
              clr();
              cin>>m>>s;
              for(int i=0; i<s; i++){
                  cin>>a>>b>>single;
                  inofv[a]++, inofv[b]--;
                  if(!single) addEdge(a, b, 1);//for out edge
              }
              possible=true;
              for(int i=1; i<=m; i++){
                  if((abs(inofv[i])&0x1)==1){
                      possible=false; break;
                  }
              }
              if(possible){
                  for(int i=1; i<=m; i++){
                      if(inofv[i]>0) addEdge(0, i, inofv[i]/2);//注意注意注意注意注意注意注意注意注意注意注意注意
                      else if(inofv[i]<0) addEdge(i, m+1, -inofv[i]/2);
                  }
                  Hpreflow();
                  for(int e=first[0]; e!=-1; e=es[e].next){
                      if(es[e].c>0){
                          if(es[e].f!=es[e].c) possible=false;
                      }
                  }
              }
              if(possible) cout<<"possible"<<endl;
              else cout<<"impossible"<<endl;
          }
      
          return 0;
      }
      

    理论结束,开始做题

    Leave a comment

    • 由于最大流和二分的特点,所以先把模型的代码实现过了一遍。然后现在开始按照lrj和实用上的题目进行练习,自己还是对二分的算法HK算法不是很熟悉,练习的时候要多注意!剩下还有四道图论的综合题,要好好练下,注意解题的思路在白纸上写清楚,然后一次性完成程序。图论挺锻炼人的程序能力的,从建模到模型的组合,很多时候都要把许多思想技巧结合在一起。废话不说了!
    • 有两个dotNet技术上的盲点要敲打下,1。GC的分代处理机制;2。CodeDom机制。dotNet一日千里,WPF,WCF,WF已经是今非昔比了,keep moving!
    • 图论结束之后的任务,主要就是进行一些BOP回顾[主要是把原来一些冗长的代码精简下,回头来看,应该有能多的改进才对]和一些基本题目的白纸编程,整理简历和练习口语的同时,把关于google搜索的框架整理下,然后从Heritrix入手,先用C#来实现一个网络爬虫的原型[最好能把一些针对C#的设计模式具体实现之],至于Lucence的分词器模拟,不晓得自己有没有时间完成。不过,无论以后在哪里工作,我还是会把这个作为自己的兴趣做完的!
    完成的题目:
    1,调皮的导盲犬[lrj P341, 又见实用,P230 小狗散步,在线链接]
    分析:典型的二分图,多说无益,只是二分的时候把最后一个定点舍去即可。[代码框架:DFS的匈牙利算法,图的类型信息不够,无法判断是否是稠图,DFS足够了]

    Source Code

    Problem: 1034 User: orlando22
    Memory: 360K Time: 47MS
    Language: C++ Result: Accepted
    • Source Code
      #include <cmath>
      #include <iostream>
      
      //pku 1034, zju 2309
      using namespace std;
      const int MAXN=100, MAXE=10000;
      //for bio-partite graph
      typedef struct Edge{
          int x, y, next;
      }Edge;
      Edge es[MAXE];
      int eid, firstX[MAXN], linkY[MAXN];//X集的出边,Y集的匹配边,为了实现方便,将定点和景点翻了下!
      bool ry[MAXN];
      
      //for Xn and X1n
      int x[MAXN], y[MAXN], xx[MAXN], yy[MAXN], n, m;
      
      //declaration
      void inline addEdge(int start, int end);
      void inline clr();
      bool find(int u);
      
      //implementation
      void addEdge(int start, int end){
          es[eid].x=start, es[eid].y=end;
          es[eid].next=firstX[start], firstX[start]=eid; eid++;
      }
      void clr(){
          eid=0,
          memset((void*)firstX, 0xff, sizeof(firstX)),
          memset((void*)linkY, 0xff, sizeof(linkY));
      }
      bool find(int u){
          for(int e=firstX[u]; e!=-1; e=es[e].next){
              if(!ry[es[e].y]){
                  ry[es[e].y]=true;
                  if(linkY[es[e].y]==-1||find(linkY[es[e].y])){
                      linkY[es[e].y]=u; return true;
                  }
              }
          }
          return false;
      }
      
      int main()
      {
          //implementation
          int res(0);
          cin>>n>>m;
          for(int i=0; i<n; i++) cin>>x[i]>>y[i];
          for(int i=0; i<m; i++) cin>>xx[i]>>yy[i];
          //create bio-partite, clr();
          clr();
          for(int i=0; i<n-1; i++){
              double dis=sqrt((double)((x[i]-x[i+1])*(x[i]-x[i+1])+(y[i]-y[i+1])*(y[i]-y[i+1])));
              for(int j=0; j<m; j++){
                  double dis1=sqrt((double)((x[i]-xx[j])*(x[i]-xx[j])+(y[i]-yy[j])*(y[i]-yy[j]))),
                      dis2=sqrt((double)((x[i+1]-xx[j])*(x[i+1]-xx[j])+(y[i+1]-yy[j])*(y[i+1]-yy[j])));
                  if(2*dis>=dis1+dis2) addEdge(j, i);//consider the speed, reverse
              }
          }
          for(int i=0; i<m; i++){
              memset((void*)ry, 0, sizeof(bool)*n);//for all target vertex->sizeof(bool)*n
              res+=find(i);
          }
          cout<<(res+n)<<endl;
          for(int i=0; i<n; i++){
              if(i!=n-1) cout<<x[i]<<" "<<y[i]<<" ";
              else cout<<x[i]<<" "<<y[i];
              if(linkY[i]!=-1) cout<<xx[linkY[i]]<<" "<<yy[linkY[i]]<<" ";
          }
          cout<<endl;
      
          return 0;
      }
    其他的优化:可以用HK来加速,但对这个题目已经足够了!
    2,棋盘上的骑士[lrj P332, 实用P234,在线链接]
    分析:二分图的最大独立数问题;棋盘是一个自然的二分图,那么最大匹配必然对应棋盘上的最小覆盖数[最少那么多],由于最大独立数与最小覆盖互为补集,因此直接减去最大匹配即可。
    先用DFS的匈牙利算法写了个,TLE了,O(VE)的复杂度,V为200,E为40000,那么就是8*10^6,估算差不多在10秒左右,果真直接挂了!

    Source Code
    #include <iostream>
     
    using namespace std;
     
    const int MAXN=201, MAXD=8;
    int n, m, dx[MAXD]={-2, -2, -1, -1, 1, 1, 2, 2}, dy[MAXD]={-1, 1, -2, 2, -2, 2, -1, 1};
    typedef struct LT{
        int x, y;
    }LT;
    LT link[MAXN][MAXN];
    bool map[MAXN][MAXN], used[MAXN][MAXN];
     
    //declaration
    bool find(int x, int y);
     
    //implemenataion
    bool find(int x, int y){
        int x1, y1;
        for(int i=0; i<MAXD; i++){
            x1=x+dx[i], y1=y+dy[i];
            if(x1>0&&x1<=n&&y1>0&&y1<=n&&map[x1][y1]&&!used[x1][y1]){
                used[x1][y1]=true;
                if(link[x1][y1].x==-1||find(link[x1][y1].x, link[x1][y1].y)){
                    link[x1][y1].x=x, link[x1][y1].y=y; return true;
                }
            }
        }
        return false;
    }
     
    int main()
    {
        //implementation
        int x, y, res(0);
        cin>>n>>m;
        for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++) map[i][j]=true;
        for(int i=1; i<=m; i++) cin>>x>>y, map[x][y]=false;
        memset((void*)link, 0xff, sizeof(link));
     
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                if(map[i][j]&&((((n&0x1)==1&&((i-1)*n+j)&0x1)==1)||((n&0x1)==0&&(i&0x1)!=(j&0x1)))){//same color to (1,1)
                    memset((void*)used, 0, sizeof(used));
                    res+=find(i, j);
                }
            }
        }
        cout<<(n*n-m-res)<<endl;
        return 0;
    }
     
    然后用HK写了个,顺利过了,但实际从理论上估计变化不大的嘛,少了一个数量级而已,但显示的时间是672MS,菜晕!
    Source Code

    #include <iostream>
     
    //BOI task , ECNU 1465 Knights
    using namespace std;
     
    const int MAXN=201, MAXD=8;
    typedef struct LT{
        int x, y;
    }LT;
    LT link[MAXN][MAXN];
    int n, m, dx[MAXD]={-2, -2, -1, -1, 1, 1, 2, 2}, dy[MAXD]={-1, 1, -2, 2, -2, 2, -1, 1};
    bool map[MAXN][MAXN], xset[MAXN][MAXN];
    int dist[MAXN][MAXN], queue[MAXN*MAXN];
     
    //declaration
    bool HK_bfs();
    bool HK_dfs(int x, int y);
     
    //implementation
    bool HK_bfs(){
        bool found=false;
        int top=0, size=0, x, x1, y1, x2, y2;
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                if(link[i][j].x==-1&&xset[i][j]) queue[size++]=i*(n+1)+j;//(1,1)起的数组和一维的转化,要小心
                dist[i][j]=0;
            }
        }
        //for modify queue
        for(;top<size;top++){
            x=queue[top], x1=x/(n+1), y1=x-x1*(n+1);
            for(int i=0; i<MAXD; i++){
                x2=x1+dx[i], y2=y1+dy[i];
                if(x2>0&&x2<n+1&&y2>0&&y2<n+1&&map[x2][y2]){//not required for !out[x2][y2]
                    if(dist[x2][y2]==0){
                        dist[x2][y2]=dist[x1][y1]+1;
                        if(link[x2][y2].x==-1) found=true;
                        else dist[link[x2][y2].x][link[x2][y2].y]=dist[x2][y2]+1,
                            queue[size++]=link[x2][y2].x*(n+1)+link[x2][y2].y;
                    }
                }
            }
        }
        return found;
    }
     
    bool HK_dfs(int x, int y){
        int x1, y1;
        for(int i=0; i<MAXD; i++){
            x1=x+dx[i], y1=y+dy[i];
            if(x1>0&&x1<n+1&&y1>0&&y1<n+1&&map[x1][y1]){
                if(dist[x1][y1]==dist[x][y]+1){
                    dist[x1][y1]=0;//reset back to top
                    if(link[x1][y1].x==-1||HK_dfs(link[x1][y1].x, link[x1][y1].y)){//昨晚忘记加link[x][y]了,搞了个死循环
                        link[x1][y1].x=x, link[x1][y1].y=y, link[x][y].x=x1, link[x][y].y=y1; return true;
                    }
                }
            }
        }
        return false;
    }
     
    int main()
    {
        //implementation
        cin>>n>>m;
        int x, y, res(0);
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++) map[i][j]=true, xset[i][j]=false;
        }
        for(int i=1; i<=m; i++) cin>>x>>y, map[x][y]=false;
        //set xset for out-link
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                if(map[i][j]&&(((n&0x1)&&(((i-1)*n+j)&0x1)==1)||(!(n&0x1)&&(i&0x1)!=(j&0x1))))
                    xset[i][j]=true;
            }
        }
    memset((void*)link, 0xff, sizeof(link));//reset for link
        //for HK algorithm
        while(HK_bfs()){
            for(int i=1; i<=n; i++){
                for(int j=1; j<=n; j++)
                    if(xset[i][j]&&link[i][j].x==-1&&HK_dfs(i, j)) res++;
            }
        }
        cout<<(n*n-m-res)<<endl;
        return 0;
    }

     

    Older Entries