首页 > 代码库 > 【网络流#7】POJ 3281 Dining 最大流 - 《挑战程序设计竞赛》例题

【网络流#7】POJ 3281 Dining 最大流 - 《挑战程序设计竞赛》例题

不使用二分图匹配,使用最大流即可,设源点S与汇点T,S->食物->牛->牛->饮料->T,每条边流量为1,因为流过牛的最大流量是1,所以将牛拆成两个点。

前向星,Dinic,复杂度:O(V2E)

直接套用模板

#include<cstdio>#include<cstring>#include<cmath>#include<iostream>#include<algorithm>#include<set>#include<map>#include<stack>#include<vector>#include<queue>#include<string>#include<sstream>#define eps 1e-9#define ALL(x) x.begin(),x.end()#define INS(x) inserter(x,x.begin())#define FOR(i,j,k) for(int i=j;i<=k;i++)#define MAXN 1005#define MAXM 30005using namespace std;typedef long long LL;int i,j,k,n,m,x,y,T,ans,big,cas,F,D,S,f,d,id;bool flag;const int inf = 0x3f3f3f3f;struct edgenode{    int from,to,next;    int cap;}edge[MAXM];int Edge,head[MAXN],ps[MAXN],dep[MAXN];void add_edge(int x,int y,int c){    edge[Edge].from=x;    edge[Edge].to=y;    edge[Edge].cap=c;    edge[Edge].next=head[x];    head[x]=Edge++;        edge[Edge].from=y;    edge[Edge].to=x;    edge[Edge].cap=0;    edge[Edge].next=head[y];    head[y]=Edge++;}int dinic(int n,int s,int t){    int tr,flow=0;    int i,j,k,l,r,top;    while(1){        memset(dep,-1,(n+1)*sizeof(int));        for(l=dep[ps[0]=s]=0,r=1;l!=r;)//BFS部分,将给定图分层         {            for(i=ps[l++],j=head[i];j!=-1;j=edge[j].next)            {                if (edge[j].cap&&-1==dep[k=edge[j].to])                {                    dep[k]=dep[i]+1;ps[r++]=k;                    if(k==t)                    {                        l=r;                        break;                    }                }            }        }        if(dep[t]==-1)break;                for(i=s,top=0;;)//DFS部分         {            if(i==t)//当前点就是汇点时             {                for(k=0,tr=inf;k<top;++k)                    if(edge[ps[k]].cap<tr)tr=edge[ps[l=k]].cap;                                    for(k=0;k<top;++k)                    edge[ps[k]].cap-=tr,edge[ps[k]^1].cap+=tr;                                    flow+=tr;                i=edge[ps[top=l]].from;            }                        for(j=head[i];j!=-1;j=edge[j].next)//找当前点所指向的点                 if(edge[j].cap&&dep[i]+1==dep[edge[j].to]) break;                            if(j!=-1)            {                ps[top++]=j;//当前点有所指向的点,把这个点加入栈中                 i=edge[j].to;            }            else            {                 if (!top) break;//当前点没有指向的点,回溯                 dep[i]=-1;                i=edge[ps[--top]].from;            }        }    }    return flow;}int main(){    memset(head,-1,sizeof(head));Edge=0;    scanf("%d%d%d",&n,&F,&D);    S=0;    T=n+n+F+D+1;    for (i=1;i<=F;i++)    {        add_edge(S,2*n+i,1);    }    for (i=1;i<=D;i++)    {        add_edge(2*n+F+i,T,1);    }        for (i=1;i<=n;i++)    {        scanf("%d%d",&f,&d);        add_edge(i,n+i,1);        for (j=1;j<=f;j++)        {            scanf("%d",&id);            id=2*n+id;             add_edge(id,i,1);        }        for (j=1;j<=d;j++)        {            scanf("%d",&id);            id=2*n+F+id;            add_edge(n+i,id,1);        }    }    printf("%d\n",dinic(T+1,S,T));    return 0;}

  

【网络流#7】POJ 3281 Dining 最大流 - 《挑战程序设计竞赛》例题