Boleyn Su's Blog

动态规划，这次还自己写了个快排。

f[i][j]表示前i本中已经选了j本，并且最后一本选的是i时的最优值。

动规方程：f[i][j]=min{f[k][j-1]+abs(book[i].width-book[k].width);k<i}。

边界：f[i][0]=0，f[i][i]=sum{abs(book[j].width-book[j+1].width);j<i}，f[i][j]=oo(j>i)。

最后的答案：min{f[i][n-k]}

CODE:

/*

AUTHOR: Su Jiao

DATE: 2010-7-24

DESCRIPTION:

动态规划 专练

http://www.rqnoj.cn/Problem_225.html

[JSOI2007]书本整理

*/

#include <stdio.h>

#include <stdlib.h>

 

const int oo=(~0u)>>2;

const int MAXN=100;

struct Book{int h,w;};

int n,k;

Book book[MAXN+2];

int f[MAXN+2][MAXN+2];

void quick_sort(int L,int R)

{

     int i=L,j=R;

     Book mid=book[(L+R)>>1],swap;

     while (i<=j)

     {

           while (book[i].h<mid.h) i++;

           while (book[j].h>mid.h) j–;

           if (i<=j)

              swap=book[i],book[i]=book[j],book[j]=swap,

              i++,j–;

     }

     if (L<j) quick_sort(L,j);

     if (i<R) quick_sort(i,R);

}

int main()

{

    scanf(“%d%d”,&n,&k);

    for (int i=1;i<=n;i++) scanf(“%d%d”,&book[i].h,&book[i].w);

    quick_sort(1,n);

    for (int i=1;i<=n;i++)

        for (int j=0;j<=n;j++)

            f[i][j]=oo;

    for (int i=1;i<=n;i++)

        for (int j=0;j<=i;j++)

        {

            if (j==0) f[i][j]=0;

            else if (j==i) f[i][j]=i>1?f[i-1][j-1]+abs(book[i].w-book[i-1].w):0;

            else for (int ii=1,jj=j-1;ii<i;ii++)

                     f[i][j]<?=f[ii][jj]+(jj?abs(book[i].w-book[ii].w):0);

        }

    int answer=oo;

    for (int i=1;i<=n;i++)

        if (answer>f[i][n-k]) answer=f[i][n-k];

    printf(“%d\n”,answer);

}

 

后缀数组。

CODE:

/*

AUTHOR: Su Jiao

DATE: 2010-7-23

DESCRIPTION:

$DESCRIPTION

*/

#include <stdio.h>

#include <string.h>

 

#define max(a,b) ((a)>(b)?(a):(b))

const int LOG2_MAXLENGTH=20;

const int MAXLENGTH=1<<LOG2_MAXLENGTH;

const int MAXALPHABET=1024;

typedef int string[MAXLENGTH];

int sort[max(MAXLENGTH,MAXALPHABET)];

int _SA[MAXLENGTH],_rank[MAXLENGTH],_TSA[MAXLENGTH],_Trank[MAXLENGTH];

int* SA=_SA;

int* rank=_rank;

int* TSA=_TSA;

int* Trank=_Trank;

void get_SA(string s,int length)

{

     memset(sort,0,sizeof(sort));

     for (int i=1;i<=length;i++) sort[s[i]]++;

     for (int i=1;i<MAXALPHABET;i++) sort[i]+=sort[i-1];

     for (int i=1;i<=length;i++) SA[sort[s[i]]–]=i;

     rank[SA[1]]=1;

     for (int i=2;i<=length;i++)

         if (s[SA[i]]==s[SA[i-1]]) rank[SA[i]]=rank[SA[i-1]];

         else rank[SA[i]]=rank[SA[i-1]]+1;

     for (int block=1;block<length;block<<=1)

     {

         for (int i=1;i<=length;i++) sort[rank[SA[i]]]=i;

         for (int i=length;i>=1;i–)

             if (SA[i]-block>=1)

                TSA[sort[rank[SA[i]-block]]–]=SA[i]-block;

         for (int i=length-block+1;i<=length;i++)

             TSA[sort[rank[i]]–]=i;

         Trank[TSA[1]]=1;

         for (int i=2;i<=length;i++)

             if (rank[TSA[i]]==rank[TSA[i-1]]

                 &&rank[TSA[i]+block]==rank[TSA[i-1]+block])

                Trank[TSA[i]]=Trank[TSA[i-1]];

             else Trank[TSA[i]]=Trank[TSA[i-1]]+1;

         int* swap;

         swap=SA,SA=TSA,TSA=swap;

         swap=rank,rank=Trank,Trank=swap;

     }

}

int height[MAXLENGTH];

void get_height(string s,int length)

{

     for (int h=0,i=1;i<=length;i++)

     {

         if (h) h–;

         if (rank[i]!=1)

         {

            int j=SA[rank[i]-1];

            while (s[i+h]==s[j+h]) h++;

         }

         height[rank[i]]=h;

     }

}

 

const int MAXN=1000;

int n;

int length;

int id[MAXLENGTH];

string s;

char input_string[MAXLENGTH];

char* input=input_string-1;

int times;

int found[MAXN];

bool check(int value)

{

     int i=1;

     while (i<=length)

     {

           times++;

           while (i<=length&&height[i]<value) i++;

           int found_count=0;

           if (i!=1) found[id[SA[i-1]]]=times,found_count++;

           while (i<=length&&height[i]>=value)

           {

                 if (found[id[SA[i]]]!=times)

                    found[id[SA[i]]]=times,found_count++;

                 i++;

           }

           if (found_count*2>n) return true;

     }

     return false;

}

void print(int value)

{

     int i=1;

     while (i<=length)

     {

           times++;

           while (i<=length&&height[i]<value) i++;

           int found_count=0;

           if (i!=1) found[id[SA[i-1]]]=times,found_count++;

           while (i<=length&&height[i]>=value)

           {

                 if (found[id[SA[i]]]!=times)

                    found[id[SA[i]]]=times,found_count++;

                 i++;

           }

           if (found_count*2>n)

           {

              for (int j=SA[i-1];j<SA[i-1]+value;j++) printf(“%c”,s[j]-n);

              printf(“\n”);

           }

     }

}

int main()

{

    bool first=true;

    for (;;)

    {

        scanf(“%d”,&n);

        if (!n) break;

        length=0;

        for (int i=1;i<=n;i++)

        {

            scanf(“%s”,&input_string);

            int dlength=strlen(input_string);

            for (int j=1;j<=dlength;j++)

                s[length+j]=n+input[j],

                id[length+j]=i;

            length+=dlength+1;

            s[length]=i;

            id[length]=0;

        }

        s[length+1]=0;

        get_SA(s,length);

        get_height(s,length);

        int L=0,R=length;

        while (L+1!=R)

        {

              int mid=(L+R)>>1;

              if (check(mid)) L=mid;

              else R=mid;

        }

        if (first) first=false;

        else printf(“\n”);

        if (n==1)

        {

           for (int i=1;i<length;i++) printf(“%c”,s[i]-n);

           printf(“\n”);

        }

        else if (L) print(L);

        else printf(“?\n”);       

    }

}

 

原来做这道题的时候不会后缀数组，用RK过的，现在可以用后缀数组过了。

CODE:

/*

AUTHOR: Su Jiao

DATE: 2010-7-23

DESCRIPTION:

$DESCRIPTION

*/

#include <stdio.h>

#include <string.h>

 

const int LOG2_MAXLENGTH=16;

const int MAXLENGTH=1<<LOG2_MAXLENGTH;

const int MAXALPHABET=1000002;

typedef int string[MAXLENGTH];

int sort[MAXLENGTH];

int _SA[MAXLENGTH],_rank[MAXLENGTH],_TSA[MAXLENGTH],_Trank[MAXLENGTH];

int* SA=_SA;

int* rank=_rank;

int* TSA=_TSA;

int* Trank=_Trank;

void quick_sort(string s,int L,int R)

{

     int i=L,j=R,mid=s[SA[(L+R)>>1]],swap;

     while (i<=j)

     {

           while (s[SA[i]]<mid) i++;

           while (s[SA[j]]>mid) j–;

           if (i<=j)

           {

              swap=SA[i],SA[i]=SA[j],SA[j]=swap;

              i++,j–;

           }

     }

     if (L<j) quick_sort(s,L,j);

     if (i<R) quick_sort(s,i,R);

}

void get_SA(string s,int length)

{

     for (int i=1;i<=length;i++) SA[i]=i;

     quick_sort(s,1,length);

     rank[SA[1]]=1;

     for (int i=2;i<=length;i++)

         if (s[SA[i]]==s[SA[i-1]]) rank[SA[i]]=rank[SA[i-1]];

         else rank[SA[i]]=rank[SA[i-1]]+1;

     for (int block=1;block<length;block<<=1)

     {

         for (int i=1;i<=length;i++) sort[rank[SA[i]]]=i;

         for (int i=length;i>=1;i–)

             if (SA[i]-block>=1) TSA[sort[rank[SA[i]-block]]–]=SA[i]-block;

         for (int i=length-block+1;i<=length;i++)

             TSA[sort[rank[i]]–]=i;

         int* swap;

         swap=SA,SA=TSA,TSA=swap;

         swap=rank,rank=Trank,Trank=swap;

         rank[SA[1]]=1;

         for (int i=2;i<=length;i++)

             if (Trank[SA[i]]==Trank[SA[i-1]]

                 &&Trank[SA[i]+block]==Trank[SA[i-1]+block])

                rank[SA[i]]=rank[SA[i-1]];

             else rank[SA[i]]=rank[SA[i-1]]+1;        

     }

}

int height[MAXLENGTH];

void get_height(string s,int length)

{

     for (int h=0,i=1;i<=length;i++)

     {

         if (h) h–;

         if (rank[i]!=1)

         {

            int j=SA[rank[i]-1];

            while (s[i+h]==s[j+h]) h++;

         }

         height[rank[i]]=h;

     }

}

 

int N,K;

string a;

bool check(int value)

{

     int i=1;

     while (i<=N)

     {

           while (i<=N&&height[i]<value) i++;

           int repeat=1;

           while (i<=N&&height[i]>=value)

           {

                 repeat++;

                 i++;

           }

           if (repeat>=K) return true;

     }

     return false;

}

int main()

{

    scanf(“%d%d”,&N,&K);

    for (int i=1;i<=N;i++) scanf(“%d”,a+i);

    get_SA(a,N);

    get_height(a,N);

    int L=0,R=N;

    while (L+1!=R)

    {

          int mid=(L+R)>>1;

          if (check(mid)) L=mid;

          else R=mid;

    }

    printf(“%d\n”,L);

}

 

后缀数组。

CODE:

/*

AUTHOR: Su Jiao

DATE: 2010-7-23

DESCRIPTION:

$DESCRIPTION

*/

#include <stdio.h>

#include <string.h>

 

#define max(a,b) ((a)>(b)?(a):(b))

const int LOG2_MAXLENGTH=16;

const int MAXLENGTH=1<<LOG2_MAXLENGTH;

const int MAXALPHABET=1024;

typedef int string[MAXLENGTH];

int sort[max(MAXLENGTH,MAXALPHABET)];

int _SA[MAXLENGTH],_rank[MAXLENGTH],_TSA[MAXLENGTH],_Trank[MAXLENGTH];

int* SA=_SA;

int* rank=_rank;

int* TSA=_TSA;

int* Trank=_Trank;

void get_SA(string s,int length)

{

     memset(sort,0,sizeof(sort));

     for (int i=1;i<=length;i++) sort[s[i]]++;

     for (int i=1;i<MAXALPHABET;i++) sort[i]+=sort[i-1];

     for (int i=1;i<=length;i++) SA[sort[s[i]]–]=i;

     rank[SA[1]]=1;

     for (int i=2;i<=length;i++)

         if (s[SA[i]]==s[SA[i-1]]) rank[SA[i]]=rank[SA[i-1]];

         else rank[SA[i]]=rank[SA[i-1]]+1;

     for (int block=1;block<length;block<<=1)

     {

         for (int i=1;i<=length;i++) sort[rank[SA[i]]]=i;

         for (int i=length;i>=1;i–)

             if (SA[i]-block>=1)

                TSA[sort[rank[SA[i]-block]]–]=SA[i]-block;

         for (int i=length-block+1;i<=length;i++)

             TSA[sort[rank[i]]–]=i;

         Trank[TSA[1]]=1;

         for (int i=2;i<=length;i++)

             if (rank[TSA[i]]==rank[TSA[i-1]]

                 &&rank[TSA[i]+block]==rank[TSA[i-1]+block])

                Trank[TSA[i]]=Trank[TSA[i-1]];

             else Trank[TSA[i]]=Trank[TSA[i-1]]+1;

         int* swap;

         swap=SA,SA=TSA,TSA=swap;

         swap=rank,rank=Trank,Trank=swap;

     }

}

int height[MAXLENGTH];

void get_height(string s,int length)

{

     for (int h=0,i=1;i<=length;i++)

     {

         if (h) h–;

         if (rank[i]!=1)

         {

            int j=SA[rank[i]-1];

            while (s[i+h]==s[j+h]) h++;

         }

         height[rank[i]]=h;

     }

}

 

int n,a,b;

string s;

bool check(int value)

{

     #define abs(a) ((a)>=0?(a):-(a))

     int i=1;

     while (i<n)

     {

           while (i<n&&height[i]<value) i++;

           int first=n,last=0;

           if (i!=1) first=SA[i-1],last=SA[i-1];

           while (i<n&&height[i]>=value)

           {

                 if (SA[i]<first) first=SA[i];

                 if (SA[i]>last) last=SA[i];

                 i++;

           }

           if (last-first>=value) return true;

     }

     return false;

}

int main()

{

    for (;;)

    {

        scanf(“%d”,&n);

        if (!n) break;

        scanf(“%d”,&b);

        for (int i=1;i<n;i++)

            a=b,scanf(“%d”,&b),s[i]=(MAXALPHABET>>1)+b-a;

        s[n]=0;

        get_SA(s,n-1);

        get_height(s,n-1);

        int L=0,R=n;

        while (L+1!=R)

        {

              int mid=(L+R)>>1;

              if (check(mid)) L=mid;

              else R=mid;

        }

        if (L+1>=5) printf(“%d\n”,L+1);

        else printf(“%d\n”,0);

    }

}

 

后缀数组。二分答案。

CODE:

/*

AUTHOR: Su Jiao

DATE: 2010-7-23

DESCRIPTION:

$DESCRIPTION

*/

#include <stdio.h>

#include <string.h>

 

#define max(a,b) ((a)>(b)?(a):(b))

const int LOG2_MAXLENGTH=16;

const int MAXLENGTH=1<<LOG2_MAXLENGTH;

const int MAXALPHABET=1024;

typedef int string[MAXLENGTH];

int sort[max(MAXLENGTH,MAXALPHABET)];

int SA[MAXLENGTH],rank[MAXLENGTH],TSA[MAXLENGTH],Trank[MAXLENGTH];

void get_SA(string s,int length)

{

     memset(sort,0,sizeof(sort));

     for (int i=1;i<=length;i++) sort[s[i]]++;

     for (int i=1;i<MAXALPHABET;i++) sort[i]+=sort[i-1];

     for (int i=1;i<=length;i++) SA[sort[s[i]]–]=i;

     rank[SA[1]]=1;

     for (int i=2;i<=length;i++)

         if (s[SA[i]]==s[SA[i-1]]) rank[SA[i]]=rank[SA[i-1]];

         else rank[SA[i]]=rank[SA[i-1]]+1;

     for (int block=1;block<length;block<<=1)

     {

         for (int i=1;i<=length;i++) sort[rank[SA[i]]]=i;

         for (int i=length;i>=1;i–)

             if (SA[i]-block>=1)

                TSA[sort[rank[SA[i]-block]]–]=SA[i]-block;

         for (int i=length-block+1;i<=length;i++)

             TSA[sort[rank[i]]–]=i;

         Trank[TSA[1]]=1;

         for (int i=2;i<=length;i++)

             if (rank[TSA[i]]==rank[TSA[i-1]]

                 &&rank[TSA[i]+block]==rank[TSA[i-1]+block])

                Trank[TSA[i]]=Trank[TSA[i-1]];

             else Trank[TSA[i]]=Trank[TSA[i-1]]+1;

         memcpy(SA,TSA,sizeof(SA));

         memcpy(rank,Trank,sizeof(rank));

     }

}

int height[MAXLENGTH];

void get_height(string s,int length)

{

     for (int h=0,i=1;i<=length;i++)

     {

         if (h) h–;

         if (rank[i]!=1)

         {

            int j=SA[rank[i]-1];

            while (s[i+h]==s[j+h]) h++;

         }

         height[rank[i]]=h;

     }

}

 

const int MAXN=1000;

int t,n;

string s;

int length;

int id[MAXLENGTH];

bool check(int value)

{

     int i=1;

     while (i<=length)

     {

           while (i<=length&&height[i]<value) i++;

           bool found[MAXN];

           memset(found,0,sizeof(found));

           if (i!=1) found[id[SA[i-1]]]=true;

           while (i<=length&&height[i]>=value)

           {

                 found[id[SA[i]]]=true;

                 i++;

           }

           bool all_found=true;

           for (int j=1;j<=n;j++) if (!found[j]) all_found=false;

           if (all_found) return true;

     }

     return false;

}

int main()

{

    scanf(“%d”,&t);

    for (int tt=0;tt<t;tt++)

    {

        length=0;

        scanf(“%d”,&n);

        for (int i=1;i<=n;i++)

        {

            char input_string[MAXLENGTH];

            char* input=input_string-1;

            scanf(“%s”,&input_string);

            int dlength=strlen(input_string);

            for (int j=1;j<=dlength;j++)

            {

                s[length+j]=(n<<1)+1+unsigned(input[j]);

                id[length+j]=i;

            }

            length+=dlength+1;

            s[length]=i<<1;

            for (int j=1;j<=dlength;j++)

            {

                s[length+j]=(n<<1)+1+unsigned(input[dlength-j+1]);

                id[length+j]=i;

            }

            length+=dlength+1;

            s[length]=(i<<1)|1;

        }

        s[length+1]=0;

        get_SA(s,length);

        get_height(s,length);

        int L=0,R=length+1;

        while (L+1!=R)

        {

              int mid=(L+R)>>1;

              if (check(mid)) L=mid;

              else R=mid;

        }

        if (n==1) printf(“%d\n”,(length>>1)-1);

        else printf(“%d\n”,L);

    }

}

 

最长公共前缀，用后缀数组做的。

CODE:

/*

AUTHOR: Su Jiao

DATE: 2010-7-23

DESCRIPTION:

$DESCRIPTION

*/

#include <stdio.h>

#include <string.h>

 

#define max(a,b) a>b?a:b

const int LOG2_MAXLENGTH=16;

const int MAXLENGTH=1<<LOG2_MAXLENGTH;

const int MAXALPHABET=128;

typedef char string[MAXLENGTH];

int sort[max(MAXALPHABET,MAXLENGTH)];

int SA[MAXLENGTH],rank[MAXLENGTH],TSA[MAXLENGTH],Trank[MAXLENGTH];

void get_SA(string s,int length)

{

     memset(sort,0,sizeof(sort));

     for (int i=1;i<=length;i++) sort[s[i]]++;

     for (int i=1;i<MAXALPHABET;i++) sort[i]+=sort[i-1];

     for (int i=1;i<=length;i++) SA[sort[s[i]]–]=i;

     rank[SA[1]]=1;

     for (int i=2;i<=length;i++)

         if (s[SA[i-1]]==s[SA[i]]) rank[SA[i]]=rank[SA[i-1]];

         else rank[SA[i]]=rank[SA[i-1]]+1;

     for (int block=1;block<length;block<<=1)

     {

         for (int i=1;i<=length;i++) sort[rank[SA[i]]]=i;        

         for (int i=length;i>=1;i–)

             if (SA[i]-block>=1)

                TSA[sort[rank[SA[i]-block]]–]=SA[i]-block;

         for (int i=length-block+1;i<=length;i++)

             TSA[sort[rank[i]]–]=i;

         Trank[TSA[1]]=1;

         for (int i=2;i<=length;i++)

             if (rank[TSA[i-1]]==rank[TSA[i]]

                 &&rank[TSA[i-1]+block]==rank[TSA[i]+block])

                Trank[TSA[i]]=Trank[TSA[i-1]];

             else Trank[TSA[i]]=Trank[TSA[i-1]]+1;

         memcpy(SA,TSA,sizeof(SA));

         memcpy(rank,Trank,sizeof(rank));

     }

}

int height[MAXLENGTH];

void get_height(string s,int length)

{

     for (int h=0,i=1;i<=length;i++)

     {

         if (h) h–;

         if (rank[i]-1>=1)

         {

            int j=SA[rank[i]-1];

            while (s[i+h]==s[j+h]) h++;

         }

         height[rank[i]]=h;

     }

}

int log2[MAXLENGTH];

int rmq[LOG2_MAXLENGTH][MAXLENGTH];

void get_RMQ(int length)

{

     log2[1]=0;

     for (int i=2;i<=length;i++) log2[i]=log2[i-1]+(i==(i&(-i)));

     for (int i=1;i<=length;i++) rmq[0][i]=i;

     for (int log=1;log<=log2[length];log++)

     {

         int exp=1<<log,exp_div_2=exp>>1;

         for (int i=1;i<=length-exp+1;i++)

         {

             int a=rmq[log-1][i];

             int b=rmq[log-1][i+exp_div_2];

             rmq[log][i]=height[a]<height[b]?a:b;

         }

     }    

}

int RMQ(int a,int b)

{

    int log=log2[b-a+1];

    int exp=1<<log;

    a=rmq[log][a],b=rmq[log][b-exp+1];

    return height[a]<height[b]?a:b;

}

int LCP(int a,int b)

{

    a=rank[a],b=rank[b];

    if (a>b) return height[RMQ(b+1,a)];

    else return height[RMQ(a+1,b)];

}

 

int H;

int n;

string s;

int main()

{

    scanf(“%d\n”,&H);

    for (int h=0;h<H;h++)

    {

        scanf(“%d\n”,&n);

        for (int i=1;i<=n;i++) scanf(“%c\n”,s+i);

        s[n+1]=0;

        get_SA(s,n);

        get_height(s,n);

        get_RMQ(n);

        int answer=1;

        for (int repeat=1;repeat<n;repeat++)

            for (int start=1;start+repeat<=n;start+=repeat)

            {

                int lcp=LCP(start,start+repeat);

                int get=lcp/repeat+1;

                int maybe_start=start-(repeat-(lcp%repeat));

                if (maybe_start>=1)

                   if (LCP(maybe_start,maybe_start+repeat)>=repeat) get++;

                if (get>answer) answer=get;

            }

        printf(“%d\n”,answer);

    }

}

 

用Floyd求出可以确定的所有轻重关系，然后如果某个珠子有不小于(n+1)/2个珠子比它重则它不可能是中间的，如果某个珠子有不小于(n+1)/2个珠子比它轻则它不可能是中间的。

最后，Floyd也是动态规划。

CODE:

/*

AUTHOR: Su Jiao

DATE: 2010-7-22

DESCRIPTION:

动态规划 乱做

http://acm.pku.edu.cn/JudgeOnline/problem?id=1975

*/

#include <stdio.h>

#include <string.h>

 

const int MAXN=128;

int t,N,M,a,b;

int G[MAXN][MAXN];

int H[MAXN][MAXN];

 

int main()

{

    scanf(“%d”,&t);

    for (int tt=0;tt<t;tt++)

    {

        scanf(“%d%d”,&N,&M);

        memset(G,0,sizeof(G)),memset(H,0,sizeof(H));

        for (int i=0;i<M;i++)

            scanf(“%d%d”,&a,&b),G[–a][–b]=1,H[b][a]=1;

        for (int k=0;k<N;k++)

            for (int i=0;i<N;i++)

                for (int j=0;j<N;j++)

                {

                    if (G[i][k]&&G[k][j])

                       G[i][j]=1;

                    if (H[i][k]&&H[k][j])

                       H[i][j]=1;

                }

        int answer=0;

        for (int i=0;i<N;i++)

        {

            int heavier=0;

            for (int j=0;j<N;j++)

                if (G[j][i]) heavier++;

            int lighter=0;

            for (int j=0;j<N;j++)

                if (H[j][i]) lighter++;

            if (heavier>=((N+1)>>1)||lighter>=((N+1)>>1)) answer++;

        }

        printf(“%d\n”,answer);

    }

}

 

动态规划，f[i][j]表示用a串的前i个字符和b串的前j个字符匹配c串的前i+j个字符是否可行。

那么f[i][j]=(f[i][j-1] and b[j]==c[i+j]) or (f[i-1][j] and a[i]==c[i+j])，边界f[0][0]=true。

CODE:

/*

AUTHOR: Su Jiao

DATE: 2010-7-22

DESCRIPTION:

动态规划 乱做

http://acm.pku.edu.cn/JudgeOnline/problem?id=2192

*/

#include <stdio.h>

#include <string.h>

 

const int MAXLENGTH=400+1;

typedef char string[MAXLENGTH];

int n;

string a,b,c;

int f[MAXLENGTH][MAXLENGTH];

string s[]={“no”,“yes”};

 

int main()

{

    scanf(“%d”,&n);

    for (int nn=1;nn<=n;nn++)

    {

        scanf(“%s%s%s”,&a,&b,&c);

        int al=strlen(a),bl=strlen(b),cl=strlen(c);

        for (int i=0;i<=al;i++)

            for (int j=0;j<=bl;j++)

            {

                f[i][j]=false;

                if (j>0&&b[j-1]==c[i+j-1]&&f[i][j-1]) f[i][j]=true;

                if (i>0&&a[i-1]==c[i+j-1]&&f[i-1][j]) f[i][j]=true;

                if (!i&&!j) f[i][j]=true;

            }

        printf(“Data set %d: %s\n”,nn,s[al+bl==cl&&f[al][bl]]);

    }

}

 

在无向带正权的图中找两条没有公共边的最短路，用网络流做。

先用最短路求出所有点到源点的距离，然后建立网络，其中点就是本来的那些点，边是原图中满足dis[u]+d[u][v]=dis[v]的边<u,v>，然后容量都为1。

求最大流，最大流的值小于2则无解，否者输出两条路径。

CODE:

/*

AUTHOR: Su Jiao

DATE: 2010-7-21

DESCRIPTION:

网络流 乱做

http://acm.sgu.ru/problem.php?contest=0&problem=185

*/

#include <stdio.h>

 

const int oo=19930309;

const int MAXV=400+2;

 

int S,T;

int d[MAXV][MAXV];

int dis[MAXV];

bool inq[MAXV];

int q[MAXV];

int head,tail;

 

void SPFA()

{

     for (int i=S;i<=T;i++) dis[i]=oo;

     inq[q[head=tail=0]=S]=true;

     dis[S]=0;

     while (head<=tail)

     {

           int u;

           inq[u=q[(head++)%MAXV]]=false;

           for (int v=S;v<=T;v++)

               if (d[u][v]&&dis[v]>dis[u]+d[u][v])

               {

                  if (!inq[v])

                     inq[q[(++tail)%MAXV]=v]=true;

                  dis[v]=dis[u]+d[u][v];

               }

     }

}

namespace sj

{

          const int oo=(~0u)>>1;

          const int MAXV=400+2;

          const int MAXE=400*400;

          typedef struct struct_edge* edge;

          struct struct_edge{int v,c;edge n,b;};

          struct_edge pool[MAXE];

          edge top;

          int S,T,V;

          edge adj[MAXV];

          int d[MAXV],dn[MAXV+1];

          void add_edge(int u,int v,int c)

          {

               top->v=v,top->c=c,top->n=adj[u],adj[u]=top++;

               top->v=u,top->c=0,top->n=adj[v],adj[v]=top++;

               adj[u]->b=adj[v],adj[v]->b=adj[u];

          }

          int augment(int u,int e)

          {

              if (u==T) return e;

              if (d[S]==V) return 0;

              int f=0,mind=V-1;

              for (edge i=adj[u];i;i=i->n)

                  if (i->c)

                  {

                     if (d[u]==d[i->v]+1)

                     {

                        int df=augment(i->v,e<i->c?e:i->c);

                        i->c-=df;

                        i->b->c+=df;

                        e-=df;

                        f+=df;

                        if (e==0) return f;

                     }

                     if (mind>d[i->v]) mind=d[i->v];

                  }

              if (f) return f;

              else

              {

                  if (!–dn[d[u]]) d[S]=V;

                  else dn[d[u]=mind+1]++;

                  return 0;

              }

          }

          int sap()

          {

              int f=0;

              dn[0]=V;

              while (d[S]<V) f+=augment(S,oo);

              return f;

          }

          void dfs(int u)

          {

               if (u==T) printf(“%d\n”,u);

               else

               {

                   printf(“%d “,u);

                   for (edge i=adj[u];i;i=i->n)

                       if ((!i->c)&&(!((i-pool)&1)))

                       {

                          i->c++;

                          i->b->c–;

                          dfs(i->v);

                          break;

                       }

               }

          }

}

 

int main()

{

    int n,m,x,y,l;

    scanf(“%d%d”,&n,&m),S=1,T=n;

    for (int u=S;u<=T;u++)

        for (int v=S;v<=T;v++)

            d[u][v]=oo;

    for (int i=0;i<m;i++)

        scanf(“%d%d%d”,&x,&y,&l),d[x][y]=d[y][x]=l;

    SPFA();

    sj::top=sj::pool;

    sj::S=S,sj::T=T,sj::V=n;

    for (int u=S;u<=T;u++)

        for (int v=S;v<=T;v++)

            if (dis[u]+d[u][v]==dis[v])

               sj::add_edge(u,v,1);

    if (sj::sap()<2) printf(“No solution\n”);

    else

    {

        sj::dfs(sj::S);

        sj::dfs(sj::S);

    }

}

 

混合图的欧拉回路，用网络流做。

CODE:

/*

AUTHOR: Su Jiao

DATE: 2010-7-21

DESCRIPTION:

网络流 乱做

http://acm.pku.edu.cn/JudgeOnline/problem?id=1637

*/

#include <stdio.h>

#include <string.h>

 

const int oo=(~0u)>>1;

const int MAXV=1102;

const int MAXE=6200;

typedef struct struct_edge* edge;

struct struct_edge{int v,c;edge n,b;};

struct_edge pool[MAXE];

edge top;

int S,T,V;

edge adj[MAXV];

int d[MAXV];

int q[MAXV];

int head,tail;

void add_edge(int u,int v,int c)

{

     top->v=v,top->c=c,top->n=adj[u],adj[u]=top++;

     top->v=u,top->c=0,top->n=adj[v],adj[v]=top++;

     adj[u]->b=adj[v],adj[v]->b=adj[u];

}

bool relabel()

{

     for (int i=0;i<V;d[i++]=oo) ;

     d[q[head=tail=0]=T]=0;

     while (head<=tail)

     {

           int u=q[head++];

           for (edge i=adj[u];i;i=i->n)

               if (i->b->c&&d[i->v]==oo)

                  d[q[++tail]=i->v]=d[u]+1;

           if (d[S]!=oo) return true;

     }

     return false;

}

int augment(int u,int e)

{

    if (u==T) return e;

    int f=0;

    for (edge i=adj[u];i&&e;i=i->n)

        if (i->c&&d[u]==d[i->v]+1)

           if (int df=augment(i->v,e<i->c?e:i->c))

              i->c-=df,i->b->c+=df,e-=df,f+=df;

    return f;

}

int dinic()

{

    int f=0;

    while (relabel()) f+=augment(S,oo);

    return f;

}

 

const int SIZE=1000;

int n,m,s,a[SIZE],b[SIZE],c[SIZE];

int degree[SIZE];

int main()

{

    scanf(“%d”,&n);

    for (int t=0;t<n;t++)

    {

        scanf(“%d%d”,&m,&s);

        memset(degree,0,sizeof(degree));

        for (int i=0;i<s;i++)

            scanf(“%d%d%d”,a+i,b+i,c+i),

            degree[a[i]]++,degree[b[i]]–;

        top=pool;

        memset(adj,0,sizeof(adj));

        S=0,T=m+1,V=m+2;

        int total=0;

        bool no_solution=false;

        for (int i=1;i<=m;i++)

        {

            if (degree[i]&1) no_solution=true;

            if (degree[i]>0) add_edge(S,i,degree[i]>>1),total+=degree[i]>>1;

            else add_edge(i,T,(-degree[i])>>1);

        }

        for (int i=0;i<s;i++)

            if (!c[i]) add_edge(a[i],b[i],1);

        if (no_solution||dinic()!=total) printf(“im”);

        printf(“possible\n”);

    }

}