JOJ 2727:GRE(ハイブリッドオーラロード)

アルゴリズムは基本的にSightseeing tourと同じであるが,判定図の連通性に注意し,かつ判定条件を緩和し,2度が奇抜な点がある場合には,1辺を加えて回路を構成する.
一般的なEKアルゴリズム

#include <cstdio>
#include <string.h>
#include <string>
#include <map>
#include <iostream>
#define min(a,b) ((a)>(b))?(b):(a)

using namespace std ;

const int maxn=30;
const int Inf=0x7fffffff;
int cap[maxn][maxn],flow[maxn][maxn],p[maxn],minflow[maxn],q[maxn];
int deg[maxn];
int n,m,junc;
int I=0;
bool vis[maxn];

int maxflow(int s , int t)
{
    int f=0,u,v,rear,head;
    memset(flow , 0 , sizeof(flow));
    while (true)
    {
       memset(minflow , 0 , sizeof(minflow));
       minflow[s]=Inf;
       head=0;
       rear=1;
       q[head]=s;
       while (rear>head)
       {
            u=q[head];head++;
            for (v=0 ; v<=t ; ++v)
            {
                 if(!minflow[v] && cap[u][v]>flow[u][v])
                 {
                    p[v]=u;
                    q[rear]=v;rear++;
                    minflow[v]=min(minflow[u],cap[u][v]-flow[u][v]);
                 }
            }
       }
       //printf("mint=%d
",minflow[t]);
       if(!minflow[t])break;
       for (u=t ; u!=s ; u=p[u])
       {
            flow[u][p[u]]-=minflow[t];
            flow[p[u]][u]+=minflow[t];
       }
       f+=minflow[t];
    }
    return f;
}

int find (int x)
{
    return p[x]<0?x:p[x]=find(p[x]);
}

void merge (int a , int b)
{
    int x=find(a);
    int y=find(b);
    int tmp;
    if(x!=y)
    {
        tmp=p[x]+p[y];
        (p[x]>p[y])?(p[x]=y,p[y]=tmp):(p[y]=x,p[x]=tmp);
        junc++;
    }
}

int main ()
{
    int cas,i,j,u,v,d,sum,point;
    const int s=26;
    const int t=27;
    string str;
    //map<string,int>mapstr;
    //freopen ("in.txt","r",stdin);
    //freopen ("out.txt","w",stdout);
    scanf("%d",&cas);
    while (cas--)
    {
        memset (cap , 0 , sizeof(cap));
        memset (deg , 0 , sizeof(deg));
        memset (vis , 0 , sizeof(vis));
        //mapstr.clear();
        point=sum=0;
        scanf("%d",&m);
        for (i=0 ; i<26 ; ++i)
         p[i]=-1;
        junc=1;
        for (i=0 ; i<m ; ++i)
        {
            cin>>str>>d;
            //printf("map=%d
",mapstr[str]);
            //if(mapstr[str]==0)
            {
                int len=str.size();
                u=str[0]-'a';v=str[len-1]-'a';
                vis[u]=1; vis[v]=1;
                merge(u,v);
                if(v!=u)
                deg[v]++,deg[u]--;
                if(d)cap[u][v]+=1;
                //mapstr[str]=i+1;
            }
            //printf("u=%d v=%d 
",u,v);
        }
        bool flag=true;
        for (i=0 ; i<26 ; ++i)
        if(vis[i])point++;
        if(point!=junc)flag=false;
        int odd_d=0,start=28,end=28;
        for (i=0 ; i<26 ; ++i)
        {
            if(deg[i]&1)
            {
               odd_d++;
               if(odd_d==1)start=i,deg[i]--;
               if(odd_d==2)end=i,deg[i]++;
               //printf("%d %d
",i,odd_d);
            }
            if(odd_d>2)flag=false; 
            if(!flag)break;
        }
        if(flag)
        {
            if(odd_d==2)
            cap[start][end]+=1;
            for (i=0 ; i<26 ; ++i)
            {
                //printf("%d ",deg[i]);
                deg[i]>>=1;
                if(deg[i]>0)cap[i][t]=deg[i],sum+=deg[i];
                if(deg[i]<0)cap[s][i]=-deg[i];
            }
            int ans=maxflow(s,t);
            //printf("
%d %d
%d %d
",ans,sum,start,end);
            printf("%d  %d
",junc,point);
            if(ans==sum)printf("Case %d: Well done!
",++I);
            else printf("Case %d: Poor boy!
",++I);
        }
        else printf("Case %d: Poor boy!
",++I);
    }
    return 0;
}

ダゴのテンプレートが改良された後、JOJ一を走って、へへへ

#include <cstdio>
#include <string.h>
#define min(a,b) ((a)>(b))?(b):(a)

using namespace std ;

const int maxn=28;
const int Inf=0x5fffffff;
int cap[maxn][maxn],dist[maxn],gap[maxn],fath[maxn];
int deg[maxn];
int n=27,m,junc;
int I=0;
const int source=0;//            0，     26      
const int sink=27;
bool vis[maxn];

int dfs (int p , int limit=Inf)
{
    if(p==n)return limit;
    for (int i=0 ; i<=n ; ++i)
    {
        if(dist[p]==dist[i]+1 && cap[p][i]>0)
        {
            int t=dfs(i,min(limit , cap[p][i]));
            if(t<0)return t;//      
            if(t>0)//   
            {
                cap[p][i]-=t;
                cap[i][p]+=t;
                return t;
            }
        }
    }
    int tmp=n+1 ;
    for (int i=0 ; i<=n ; ++i)
        if(cap[p][i]>0)
            tmp=min(tmp,dist[i]+1);
    
    //printf("dist[p]=%d   dist0=%d   tmp=%d
",dist[p],dist[0],tmp);
    //printf("gap=");
    //for (int i=0 ; i<n ; i++)printf("%d ",gap[i]);
    //puts("");
    if(--gap[dist[p]]==0 || dist[0]>n)return -1;//         
    ++gap[dist[p]=tmp];
    return 0;
}

int SAP()
{
    gap[source]=n+1;
    int f = 0 , t=0;
    while (~(t=dfs(source))) f+=t;
    //printf("%d
",t);
    return f;
}

int find (int x)
{
    return fath[x]<0?x:fath[x]=find(fath[x]);
}

void merge (int a , int b)
{
    int x=find(a);
    int y=find(b);
    int tmp;
    if(x!=y)
    {
        tmp=fath[x]+fath[y];
        (fath[x]>fath[y])?(fath[x]=y,fath[y]=tmp):(fath[y]=x,fath[x]=tmp);
        junc++;
    }
}

int main ()
{
    int cas,i,j,u,v,d,sum,point;
    char str[25];
    scanf("%d",&cas);
    while (cas--)
    {
        memset (cap , 0 , sizeof(cap));
        memset (deg , 0 , sizeof(deg));
        memset (vis , 0 , sizeof(vis));
        memset (dist , 0 , sizeof(dist));
        memset (gap , 0 , sizeof(gap));
        point=sum=0;
        scanf("%d",&m);
        for (i=1 ; i<=26 ; ++i)
         fath[i]=-1;
        junc=1;
        for (i=0 ; i<m ; ++i)
        {
            scanf("%s%d",str,&d);
            {
                int len=strlen(str);
                u=str[0]-'a'+1;v=str[len-1]-'a'+1;
                vis[u]=1; vis[v]=1;
                merge(u,v);
                if(v!=u)
                deg[v]++,deg[u]--;
                if(d)cap[u][v]+=1;
            }
            //printf("u=%d v=%d 
",u,v);
        }
        bool flag=true;
        for (i=1 ; i<=26 ; ++i)
        if(vis[i])point++;
        if(point!=junc)flag=false;
        int odd_d=0,start=28,end=28;
        for (i=1 ; i<=26 ; ++i)
        {
            if(deg[i]&1)
            {
               odd_d++;
               if(odd_d==1)start=i,deg[i]--;
               if(odd_d==2)end=i,deg[i]++;
            }
            if(odd_d>2)flag=false; 
            if(!flag)break;
        }
        if(flag)
        {
            if(odd_d==2)
            cap[start][end]++;
            for (i=1 ; i<=26 ; ++i)
            {
                deg[i]>>=1;
                if(deg[i]>0)cap[i][sink]=deg[i],sum+=deg[i];
                if(deg[i]<0)cap[source][i]=-deg[i];
            }
            int ans=SAP();
            if(ans==sum)printf("Case %d: Well done!
",++I);
            else printf("Case %d: Poor boy!
",++I);
        }
        else printf("Case %d: Poor boy!
",++I);
    }
    return 0;
}