现在的位置: 首页 > 综合 > 正文

hdu 3081&hdu 3277 (最大流)

2018年02月20日 ⁄ 综合 ⁄ 共 4202字 ⁄ 字号 评论关闭

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

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

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

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




hdu 3081:

#include<stdio.h>
#include<string.h>
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]<ans)
        maxflow+=dfs(start,inf);
    return maxflow;
}
bool judge(int D)
{
    memset(head,-1,sizeof(head));
    num=0;
    int i,j;
    for(i=1;i<=n;i++)
	{
		addedge(start,i,D);
		addedge(i+n,end,D);
		for(j=1;j<=n;j++)
		{
			if(map[i][j])addedge(i,j+n,1);
		}		
	}
    if(isap()==n*D)
        return true;
    return false;
}
int main()
{
    int i,j,k,m,F,t,x,y,flag;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%d",&n,&m,&F);
        tot=0;start=0;end=n+n+1;ans=end+1;
        memset(first,-1,sizeof(first));
		memset(map,false,sizeof(map));
        for(i=1;i<=n;i++)
            f[i]=i;
        for(i=0;i<m;i++)
        {
            scanf("%d%d",&x,&y);
            Addedge(x,y);
			map[x][y]=true;
        }
        while(F--)
        {
            scanf("%d%d",&x,&y);
            if(find(x)!=find(y))
				f[find(x)]=find(y);
        }
		for(i=1;i<=n;i++)
        {
            for(j=i+1;j<=n;j++)
            {
                if(find(i)!=find(j))continue;
                for(k=first[i];k!=-1;k=E[k].next)
                    map[j][E[k].ed]=true;
                for(k=first[j];k!=-1;k=E[k].next)
                    map[i][E[k].ed]=true;                    
            }
        }
        int L=0,R=n,mid;
        flag=0;
        while(L<=R)
        {
            mid=(L+R)>>1;
            if(judge(mid))
            {
                flag=mid;
                L=mid+1;
            }
            else R=mid-1;
        }
        printf("%d\n",flag);
    }
    return 0;
}

hdu 3277:



#include<stdio.h>
#include<string.h>
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]<ans)
        maxflow+=dfs(start,inf);
    return maxflow;
}
bool judge(int D)
{
    memset(head,-1,sizeof(head));
    num=0;
    int i,j;
    for(i=1;i<=n;i++)
    {
        addedge(start,i,D);
        addedge(i+n,end,D);
        addedge(i,i+2*n,K);
        for(j=1;j<=n;j++)
        {
            if(map[i][j])
                addedge(i,j+n,1);
            else addedge(i+2*n,j+n,1);
        }
    }
    if(isap()==n*D)
        return true;
    return false;
}
int main()
{
    int i,j,k,m,F,t,x,y,flag;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%d%d",&n,&m,&K,&F);
        tot=0;start=0;end=n+n+n+1;ans=end+1;
        memset(first,-1,sizeof(first));
        memset(map,false,sizeof(map));
        for(i=1;i<=n;i++)
            f[i]=i;
        for(i=0;i<m;i++)
        {
            scanf("%d%d",&x,&y);
            Addedge(x,y);
            map[x][y]=true;
        }
        while(F--)
        {
            scanf("%d%d",&x,&y);
            if(find(x)!=find(y))
                f[find(x)]=find(y);
        }
        for(i=1;i<=n;i++)
        {
            for(j=i+1;j<=n;j++)
            {
                if(find(i)!=find(j))continue;
                for(k=first[i];k!=-1;k=E[k].next)
                    map[j][E[k].ed]=true;
                for(k=first[j];k!=-1;k=E[k].next)
                    map[i][E[k].ed]=true;                    
            }
        }
        int L=1,R=n,mid;
        flag=0;
        while(L<=R)
        {
            mid=(L+R)>>1;
            if(judge(mid))
            {
                flag=mid;
                L=mid+1;
            }
            else R=mid-1;
        }
        printf("%d\n",flag);
    }
    return 0;
}

抱歉!评论已关闭.