POJ3281:Dining（dinic+拆点）

PS:刷够网络流了，先这样吧，之后再刷，慢慢补。

题意：有F种食物,D种饮料,N头奶牛,只能吃某种食物和饮料(而且只能吃特定的一份),一种食物被一头牛吃了之后,其余牛就不能吃了第一行有N,F,D三个整数:接着2-N+1行代表第i头牛,前面两个整数是Fi与Di(食物与饮料的种类数量),接着是食物的种类与饮料的种类要求输出最多分配能够满足的牛的数量.

思路：这是一种神奇的建图方式-拆点。让我想打死都想不出来。sad

建图,有2*n+f+d+2个顶点，0表示源点,2*n+f+d+1表示汇点。由源点指向食物,再由食物指向牛,牛再指向对应的饮料,饮料再指向汇点当然要使每一头牛都对应每一份食物与饮料,所以应该牛i指向牛i再指向饮料,这样就可以避免一头牛只占用多份食物与饮料了全部是有向的边,而且权值全部为1 我在这里是1到f为食物点，f+1到f+2*n为牛点，f+2*n+1到f+2*n+d为饮料点

#include <iostream>

#include <stdio.h>

#include <string.h>

#include <algorithm>

#include <queue>

#include <math.h>

#define N 1100

#define inf 0x3f3f3f3f

typedef int ll;

using namespace std;

ll n,f,d,tt,dis[N],head[N];

struct node

{

    ll x,y,w,next;

} eg[N*N];

void init()

{

    tt=;

    memset(head,-,sizeof(head));

}

void add(int xx,int yy)

{

    eg[tt].x=xx;

    eg[tt].y=yy;

    eg[tt].w=;

    eg[tt].next=head[xx];

    head[xx]=tt++;

    eg[tt].x=yy;

    eg[tt].y=xx;

    eg[tt].w=;

    eg[tt].next=head[yy];

    head[yy]=tt++;

}

bool bfs(int s,int e)

{

    memset(dis,-,sizeof(dis));

    dis[s]=;

    queue<int>q;

    q.push(s);

    while(!q.empty())

    {

        int fa=q.front();

        q.pop();

        for(int i=head[fa]; i!=-; i=eg[i].next)

        {

            int v=eg[i].y;

            if(dis[v]==-&&eg[i].w)

            {

                dis[v]=dis[fa]+;

                q.push(v);

            }

        }

    }

    if(dis[e]>)

        return true;

    return false;

}

int dinic(int s,int maxt)

{

    if(s==*n+f+d+) return maxt;

    int a,sum=maxt;

    for(int i=head[s]; i!=-; i=eg[i].next)

    {

        int v=eg[i].y;

        if(dis[v]==dis[s]+&&eg[i].w>)

        {

            a=dinic(v,min(sum,eg[i].w));

            eg[i].w-=a;

            eg[i+].w+=a;

            sum-=a;

        }

    }

    return maxt-sum;

}

int main()

{

    ll xx,yy,s1,s2;

    scanf("%d%d%d",&n,&f,&d);

        init();

        for(int j=;j<=f;j++)

        {

            add(,j);

        }

        for(int j=;j<=d;j++)

        {

            add(f+*n+j,f+*n+d+);

        }

        for(int i=;i<=n;i++)

        {

            scanf("%d%d",&s1,&s2);

            for(int j=;j<=s1;j++)

            {

                scanf("%d",&xx);

                add(xx,f+i);

            }

            for(int j=;j<=s2;j++)

            {

                scanf("%d",&yy);

                add(f+n+i,f+*n+yy);

            }

        }

        for(int i=;i<=n;i++)

        {

            add(f+i,f+n+i);

        }

        ll ans=;

        while(bfs(,*n+f+d+))

        {

            ans+=dinic(,inf);

        }

        printf("%d\n",ans);

    return ;

}

巴特西

POJ3281:Dining（dinic+拆点）

最新文章

热门文章