网络流子序列EK

#include<stdio.h>
#include<queue>
#include<algorithm>
#include<string.h>
#include<vector>
#define nn 1005
#define INF 0x3f3f3f
using namespace std;

int n,m,f[nn][nn],tem,pre[nn],vis[nn],maxx=0,d[nn][nn],maxnum=0,ans=1,k,i,num[nn];

/*void pro()
{
    for(i=0; i<=n+m+1; i++)
        for(j=0; j<=n+m+1; j++)
            if(f[i][j])
                printf(\"f[%d][%d]=%d\\n\",i,j,f[i][j]);
}*/


int bfs(int st,int en)
{
    tem=INF;
    memset(vis,0,sizeof(vis));
    memset(pre,-1,sizeof(pre));
    for(i=1; i<=n; i++)
        pre[i+n]=i;
    int flag=0;
    queue <int> q;
    q.push(st);
    vis[st]=1;

    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(i=1; i<=2*n; i++)
        {

            if((!vis[i])&&(f[u][i]>0))
            {
                vis[i]=1;
                pre[i]=u;
                printf(\"pre[%d]=%d\\n\",i,u);

                    q.push(i);


            }//若
            else if(f[u][2*n+1]>0)
            {
                pre[2*n+1]=u;
                printf(\",wpwe pre[%d]=%d\\n\",2*n+1,u);
                flag=1;

            }

        }
    }


    return flag;
}

void EK(int en)
{
    printf(\"ok,ek!\\n\");


    maxnum=0;
    maxx=0;
    while(bfs(0,2*n+1))
    {
        ans=1;

        for(k=en; pre[k]!=-1; k=pre[k])
        {
            printf(\"k==%d\\n,pre[%d]=%d\\n\",k,k,pre[k]);
            f[pre[k]][k]-=1;
            f[k][pre[k]]+=1;
            printf(\"f[%d][%d]=%d,f[%d][%d]=%d\\n\",pre[k],k,f[pre[k]][k],k,pre[k],f[k][pre[k]]);
            if((k>=1)&&(k<=n)&&(pre[k]>=n+1)&&(pre[k]<=2*n)&&(f[k][pre[k]]==1))

            {
                ans++;
                printf(\"plus\\n\");
            }
        }

        printf(\"oui,maxx=%d,maxnum=%d\\n\",maxx,maxnum);
        if(maxx<ans)
        {
            maxx=ans;
            maxnum=0;

        }
        if(maxx==ans)
        {
            maxnum++;
        }
        printf(\"yes,maxx=%d,maxnum=%d\\n\",maxx,maxnum);

    }


    printf(\"final,maxx=%d,maxnum=%d\\n\",maxx,maxnum);
}

int main()
{

    scanf(\"%d\",&n);//n个点
    memset(f,0,sizeof(f));
    for(i=1; i<=n; i++)
    {
        scanf(\"%d\",&num[i]);


        f[i][i+n]=1;
        if(i>=2)
        {
            if(num[i]>num[i-1])
            {
                f[i+n-1][i]=1;
                printf(\"%d and %d\\n\",i+n-1,i);
            }
            else
            {
                f[0][i]=1;

                f[i+n-1][2*n+1]=1;

                for(k=i-1; k>0; k--)
                {
                    if(num[k]<num[i])
                    {
                        f[0][i]=0;//这是接上前面的
                        f[k+n][i]=1;
                        break;
                    }
                }
            }
        }
    }
    f[0][1]=1;
    f[2*n][2*n+1]=1;
    for(i=0; i<=2*n+1; i++)
        for(k=0; k<=2*n+1; k++)
        {
            if(f[i][k])
                printf(\"f[%d][%d]=%d\\n\",i,k,f[i][k]);
            d[i][k]=f[i][k];
        }
    EK(2*n+1);
    printf(\"sec!\\n\");
    for(i=0; i<=2*n+1; i++)
        for(k=0; k<=2*n+1; k++)
        {

            f[i][k]=d[i][k];
            if(f[i][k])
                printf(\"f[%d][%d]=%d\\n\",i,k,f[i][k]);
        }
         f[1][1+n]=f[0][1]=f[n][2*n]=f[2*n][2*n+1]=INF;

    for(i=0; i<=2*n+1; i++)
        for(k=0; k<=2*n+1; k++)
        {
            if(f[i][k])
                printf(\"f[%d][%d]=%d\\n\",i,k,f[i][k]);
        }
    printf(\"sssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss\\n\");
    EK(2*n+1);
    return 0;
}//子序列，主要是建图要一些技巧，然后注意给最前一点和最后点INF就行