hust 1024(2분 + 최대 흐름)

dance party

Time Limit: 2 Sec
Memory Limit: 128 MB
Submissions: 374
Solved: 136

Description

You are organizing a dance party. The party will be attended by n boys and n girls. There will be several rounds of dancing. In each round, you divide the guests into n dancing pairs. Each guest must be in exactly one pair, and each pair must contain one boy and one girl. Each boy must dance with a different girl in every round. Some boys and girls like each other and some do not. During the party, each boy agrees to dance with at most k girls he doesn't like. Similarly, each girl agrees to dance with at most k boys she doesn't like. You are given the each pairs of boys and girls who agree to dance with each other .Find out the maximum number of rounds you can organize.

Input

The first line contains a integer t,which means there are t cases followed. For each case,the first line contain three integer n,m,k ,which means there are n boys and n girls attending the party and m pairs of boys and girls who agree to dance with each other,and each boy or girl agrees to dance with at most k girls or boys he or she doesn't like.At last ,there are m lines with two integers a,b which means boy a and girl b agree to dance with each other. (0

Output

The output cotains only one integer which means the maximum number of rounds you can organize.

Sample Input

Sample Output

2
2

HINT

Source

lshmouse
분석: 이 문제는 최대 몇 번까지 이분도를 할 수 있는지 정확하게 일치하는 것으로 볼 수 있다. 즉, 최대 흐름이 점의 배수에 딱 맞기 때문에 이분답을 한 다음에 최대 흐름으로 실행 가능한지 판단하는 데 관건은 구도에 있다.
2분 답안ans;
모든 남자아이를 왼쪽의 점 X, 여자아이는 오른쪽의 점 Y로 보고 X를 자신이 좋아하는 춤추는 Xa, 싫어하는 Xb, Y와 함께 Ya, Yb로 나눈다. 원점 src와 그래서 Xa 사이에 용량이 ans인 유향변을 연결하고 Ya와 환점dest 사이에 용량이 ans인 유향변을 연결한다. Xa와 Xb, Yb와 Ya 사이에 유향변을 연결한 다음에 매거한다. 그래서 남자아이 i, 여자아이 j. 만약에 i가 j와 함께 할 수 있다면만약에 Xai와 Yaj 사이에 용량이 1인 유향변을 연결한다. 그렇지 않으면 Xbi와 Ybj 사이에 유향변을 연결한다. 현재 최대 흐름은 n의 배수와 답안 ans가 가능하다면...
코드:

#include<cstdio>
using namespace std;
const int mm=111111;
const int mn=444;
const int oo=1000000000;
int node,src,dest,edge,k,n;
int reach[mm],flow[mm],next[mm];
int head[mn],work[mn],dis[mn],q[mn];
bool like[111][111];
inline int min(int a,int b)
{
    return a<b?a:b;
}
inline void prepare(int _node,int _src,int _dest)
{
    node=_node,src=_src,dest=_dest;
    for(int i=0; i<node; ++i)head[i]=-1;
    edge=0;
}
inline void addedge(int u,int v,int c)
{
    reach[edge]=v,flow[edge]=c,next[edge]=head[u],head[u]=edge++;
    reach[edge]=u,flow[edge]=0,next[edge]=head[v],head[v]=edge++;
}
bool Dinic_bfs()
{
    int i,u,v,l,r=0;
    for(i=0; i<node; ++i)dis[i]=-1;
    dis[q[r++]=src]=0;
    for(l=0; l<r; ++l)
        for(i=head[u=q[l]]; i>=0; i=next[i])
            if(flow[i]&&dis[v=reach[i]]<0)
            {
                dis[q[r++]=v]=dis[u]+1;
                if(v==dest)return 1;
            }
    return 0;
}
int Dinic_dfs(int u,int exp)
{
    if(u==dest)return exp;
    for(int &i=work[u],v,tmp; i>=0; i=next[i])
        if(flow[i]&&dis[v=reach[i]]==dis[u]+1&&(tmp=Dinic_dfs(v,min(exp,flow[i])))>0)
        {
            flow[i]-=tmp;
            flow[i^1]+=tmp;
            return tmp;
        }
    return 0;
}
int  Dinic_flow()
{
    int i,ret=0,delta;
    while(Dinic_bfs())
    {
        for(i=0; i<node; ++i)work[i]=head[i];
        while(delta=Dinic_dfs(src,oo))ret+=delta;
    }
    return ret;
}
inline void fresh(int c)
{
    int i,j;
    for(i=0; i<edge; ++i)flow[i]=((i&1)==0);
    for(i=1; i<=n; ++i)
    {
        flow[head[i]^1]=c;
        flow[head[i+3*n]]=c;
        flow[head[i+2*n]]=k;
        flow[next[head[i]]]=k;
    }
}
int main()
{
    int i,j,m,t,l,r;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%d",&n,&m,&k);
        for(i=1; i<=n; ++i)
            for(j=1; j<=n; ++j)like[i][j]=0;
        while(m--)scanf("%d%d",&i,&j),like[i][j]=1;
        prepare(n*4+2,0,n*4+1);
        for(i=1; i<=n; ++i)
            for(j=1; j<=n; ++j)
                if(like[i][j])addedge(i,j+3*n,0);
                else addedge(i+n,j+2*n,0);
        for(i=1; i<=n; ++i)
        {
            addedge(i,i+n,0);
            addedge(i+2*n,i+3*n,0);
            addedge(src,i,0);
            addedge(i+3*n,dest,0);
        }
        l=0,r=n;
        while(l<=r)
        {
            m=(l+r)>>1;
            fresh(m);
            if(Dinic_flow()==n*m)l=m+1;
            else r=m-1;
        }
        printf("%d
",l-1);
    }
    return 0;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

cocos2d Lua 학습(一)

ios에서 루아 함수 호출 및 전참 방법 lua 코드: 출력 결과: lua 호출 C++ 방법: add 함수: lua 코드: 출력 결과: 함수를 호출합니다. 함수를 호출하려면 다음 협의를 따르십시오. 우선, 호출할 함...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.