hdu 3081&hdu 3277 (最大流) - c++编程基础

hdu 3081题意：n个女孩，n个男孩，每个女孩有自己喜欢的男孩，她也会喜欢自己朋友喜欢的男孩，朋友间的关系是可以传递的。每个女孩每轮游戏要找一个喜欢的男孩过家家。问游戏最多能玩多少轮。

hdu 3277：跟3081题目意思大概一样，就是加了一个每个女孩可以选k个自己不喜欢的男孩。

hdu 3081：思路：图是二分图，如果把每个女孩跟喜欢的男孩连边，建设能玩D轮游戏，就是该图的最大流是D*n了，所以加上源点汇点，再二分找出最大的游戏论数。

hdu 3277：在一题上把女孩拆成两个点，拆出来的点连接不喜欢的男孩，在二分建图时不能太复杂，不然得TLE。

hdu 3081：

#include  
#include  
const int N=300;  
const int inf=0x3fffffff;  
int head[N],num,gap[N],dis[N],first[N],tot,f[N],start,end,ans,n;  
bool map[110][110];  
struct edge  
{  
    int st,ed,flow,next;  
}e[N*10000];  
struct node  
{  
    int ed,next;  
}E[N*N];  
int find(int a)  
{  
    if(a!=f[a])  
        f[a]=find(f[a]);  
    return f[a];  
}  
void addedge(int x,int y,int w)  
{  
    e[num].ed=y;e[num].flow=w;e[num].next=head[x];head[x]=num++;  
    e[num].ed=x;e[num].flow=0;e[num].next=head[y];head[y]=num++;  
}  
void Addedge(int x,int y)  
{  
    E[tot].ed=y;E[tot].next=first[x];first[x]=tot++;  
}  
int dfs(int u,int minflow)    
{    
    if(u==end)return minflow;    
    int i,v,f,min_dis=ans-1,flow=0;    
    for(i=head[u];i!=-1;i=e[i].next)    
    {    
        v=e[i].ed;    
        if(e[i].flow<=0)continue;    
        if(dis[v]+1==dis[u])    
        {    
            f=dfs(v,e[i].flow>minflow-flow minflow-flow:e[i].flow);    
            e[i].flow-=f;    
            e[i^1].flow+=f;    
            flow+=f;    
            if(flow==minflow)break;    
            if(dis[start]>=ans)return flow;    
        }    
        min_dis=min_dis>dis[v] dis[v]:min_dis;    
    }    
    if(flow==0)    
    {    
        if(--gap[dis[u]]==0)    
            dis[start]=ans;    
        dis[u]=min_dis+1;    
        gap[dis[u]]++;    
    }    
    return flow;    
}  
int isap()  
{  
    int maxflow=0;  
    memset(gap,0,sizeof(gap));  
    memset(dis,0,sizeof(dis));  
    gap[0]=ans;  
    while(dis[start]>1;  
            if(judge(mid))  
            {  
                flag=mid;  
                L=mid+1;  
            }  
            else R=mid-1;  
        }  
        printf("%d\n",flag);  
    }  
    return 0;  
}

hdu 3277：

#include  
#include  
const int N=1000;  
const int inf=0x3fffffff;  
int head[N],num,gap[N],dis[N],first[N],tot,f[N],start,end,ans,n,K;  
bool map[300][300];  
struct edge  
{  
    int st,ed,flow,next;  
}e[N*1000];  
struct node  
{  
    int ed,next;  
}E[N*N];  
int find(int a)  
{  
    if(a!=f[a])  
        f[a]=find(f[a]);  
    return f[a];  
}  
void addedge(int x,int y,int w)  
{  
    e[num].ed=y;e[num].flow=w;e[num].next=head[x];head[x]=num++;  
    e[num].ed=x;e[num].flow=0;e[num].next=head[y];head[y]=num++;  
}  
void Addedge(int x,int y)  
{  
    E[tot].ed=y;E[tot].next=first[x];first[x]=tot++;  
}  
int dfs(int u,int minflow)    
{    
    if(u==end)return minflow;    
    int i,v,f,min_dis=ans-1,flow=0;    
    for(i=head[u];i!=-1;i=e[i].next)    
    {    
        v=e[i].ed;    
        if(e[i].flow<=0)continue;    
        if(dis[v]+1==dis[u])    
        {    
            f=dfs(v,e[i].flow>minflow-flow minflow-flow:e[i].flow);    
            e[i].flow-=f;    
            e[i^1].flow+=f;    
            flow+=f;    
            if(flow==minflow)break;    
            if(dis[start]>=ans)return flow;    
        }    
        min_dis=min_dis>dis[v] dis[v]:min_dis;    
    }    
    if(flow==0)    
    {    
        if(--gap[dis[u]]==0)    
            dis[start]=ans;    
        dis[u]=min_dis+1;    
        gap[dis[u]]++;    
    }    
    return flow;    
}  
int isap()  
{  
    int maxflow=0;  
    memset(gap,0,sizeof(gap));  
    memset(dis,0,sizeof(dis));  
    gap[0]=ans;  
    while(dis[start]>1;  
            if(judge(mid))  
            {  
                flag=mid;  
                L=mid+1;  
            }  
            else R=mid-1;  
        }  
        printf("%d\n",flag);  
    }  
    return 0;  
}