poj 2699 The Maximum Number of Strong Kings 网络流

#include <iostream>#include <cstdio>#include <cstring>using namespace std;const int maxn=19;int a[maxn],e[70][70],flag[maxn];int  n;void makegraph(){    memset(e,0,sizeof(e));    int ret=0;    for(int i=1;i<=n;i++)    for(int j=i+1;j<=n;j++)    {        ++ret;        e[ret][i+50]=1;        e[ret][j+50]=1;        e[0][ret]=1;        if(flag[i]&&a[j]>a[i])        e[ret][j+50]=0;    }    for(int i=1;i<=n;i++)    {        e[i+50][61]=a[i];    }}int level[71],que[71];bool makelevel(int s,int t){    memset(level,0,sizeof(level));    level[s]=1;    int iq=0;    que[++iq]=s;    for(int i=1;i<=iq;i++)    {        int top=que[i];        if(top==t) return true;        for(int i=0;i<=61;i++)        if(!level[i]&&e[top][i])        {            que[++iq]=i;            level[i]=level[top]+1;        }    }    return false;}int dfs(int now,int maxf,int t){    if(now==t) return maxf;    int ret=0,f;    for(int k=0;k<=61;k++)    if(e[now][k])    {        if(level[k]==level[now]+1)        {            f=dfs(k,min(maxf-ret,e[now][k]),t);            e[now][k]-=f;            e[k][now]+=f;            ret+=f;            if(ret==maxf) return ret;        }    }    return ret;}int dinic(int s,int t){    int ans=0;    while(makelevel(s,t))    ans+=dfs(s,111,t);    return ans;}int main(){    int tcase;    scanf("%d\n",&tcase);    while(tcase--)    {        n=0;        char tmp;        while(1)        {            scanf("%c",&tmp);            if(tmp==' ') continue;            else if(tmp=='\n') break;            else a[++n]=tmp-'0';        }        memset(flag,0,sizeof(flag));        int ans;        for(int i=n;i>=1;i--)        {            flag[i]=1;            makegraph();            if(dinic(0,61)==n*(n-1)/2)            ans=n-i+1;//            cout<<ans<<endl;        }        printf("%d\n",ans);    }    return 0;}