題目鏈接：點擊查看

題目大意：作為食堂管理人，現(xiàn)在有n個學(xué)生需要打飯，每個學(xué)生需要一個飲料和食物才能滿足，每個學(xué)生可以同時接受多種不同的食物和飲料，現(xiàn)在給出每種食物和飲料的個數(shù)，問最多能讓多少學(xué)生滿足

題目分析：這個題目和之前奶牛匹配飲料和食物的題目一模一樣。。直接拆點就行了，不多廢話了：

源點->每種食物，流量為食物的數(shù)量

可匹配的食物->每個人的入點，流量為1

每個人的入點->每個人的出點，流量為1

每個人的出點->可匹配的飲料，流量為1

每種飲料->匯點，流量為飲料的數(shù)量

建完邊后直接跑最大流就好了，這次拿新偷到的SAP模板練練手

代碼：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e3+100;//點數(shù)的最大值const int M=N*N;//邊數(shù)的最大值char s[N];struct Node {int from,to,next;int cap; }edge[M];int tol,head[N],dep[N],gap[N];//gap[x]=y :說明殘留網(wǎng)絡(luò)中dep[i]==x的個數(shù)為yint n;//n是總的點的個數(shù)，包括源點和匯點void init() {tol=0;memset(head,-1,sizeof(head)); }void addedge(int u,int v,int w) {edge[tol].from=u;edge[tol].to=v;edge[tol].cap=w;edge[tol].next=head[u];head[u]=tol++;edge[tol].from=v;edge[tol].to=u;edge[tol].cap=0;edge[tol].next=head[v];head[v]=tol++; } void BFS(int start,int end) {memset(dep,-1,sizeof(dep));memset(gap,0,sizeof(gap));gap[0]=1;int que[N];int front,rear;front=rear=0;dep[end]=0;que[rear++]=end;while(front!=rear){int u=que[front++];if(front==N)front=0;for(int i=head[u];i!=-1;i=edge[i].next){int v=edge[i].to;if(dep[v]!=-1)continue;que[rear++]=v;if(rear==N)rear=0;dep[v]=dep[u]+1;++gap[dep[v]];}} } int SAP(int start,int end) {int res=0;BFS(start,end);int cur[N];int S[N];int top=0;memcpy(cur,head,sizeof(head));int u=start;int i;while(dep[start]<n){if(u==end){int temp=inf;int inser;for(i=0;i<top;i++)if(temp>edge[S[i]].cap){temp=edge[S[i]].cap;inser=i;}for(i=0;i<top;i++){edge[S[i]].cap-=temp;edge[S[i]^1].cap+=temp;}res+=temp;top=inser;u=edge[S[top]].from;}if(u!=end&&gap[dep[u]-1]==0)//出現(xiàn)斷層，無增廣路break;for(i=cur[u];i!=-1;i=edge[i].next)if(edge[i].cap!=0&&dep[u]==dep[edge[i].to]+1)break;if(i!=-1){cur[u]=i;S[top++]=i;u=edge[i].to;}else{int min=n;for(i=head[u];i!=-1;i=edge[i].next){if(edge[i].cap==0)continue;if(min>dep[edge[i].to]){min=dep[edge[i].to];cur[u]=i;}}--gap[dep[u]];dep[u]=min+1;++gap[dep[u]];if(u!=start)u=edge[S[--top]].from;}}return res; }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);int f,d;while(scanf("%d%d%d",&n,&f,&d)!=EOF){//1~n:person1 n+1~2*n:person2 2*n+1~2*n+f:food 2*n+f+1~2*n+f+d:drink init();int st=N-1,ed=st-1;for(int i=1;i<=f;i++)//st->food{int val;scanf("%d",&val);addedge(st,2*n+i,val);}for(int i=1;i<=d;i++)//drink->ed{int val;scanf("%d",&val);addedge(2*n+f+i,ed,val);}for(int i=1;i<=n;i++)//person1->person2addedge(i,i+n,1);for(int i=1;i<=n;i++){scanf("%s",s+1);for(int j=1;j<=f;j++){if(s[j]=='Y')addedge(2*n+j,i,1);}}for(int i=1;i<=n;i++){scanf("%s",s+1);for(int j=1;j<=d;j++){if(s[j]=='Y')addedge(i+n,2*n+f+j,1);}}n+=2;printf("%d\n",SAP(st,ed));}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的HDU - 4292 Food(最大流+思维建边)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。