本文主要是介绍poj 3281 Dining 最大流dinic 模板题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
分析：因为同时有饮料喝食物所以不能二分匹配，只能跑最大流；#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
#include <set>
using namespace std;
#define MM(a) memset(a,0,sizeof(a))
typedef long long ll;
typedef unsigned long long ULL;
const int mod = 1000000007;
const double eps = 1e-10;
const int inf = 0x3f3f3f3f;
const int big=50000;
int max(int a,int b) {return a>b?a:b;};
int min(int a,int b) {return a<b?a:b;};
struct Edge{
int to,cap,rev;
};
int level[500];
vector<Edge> G[500];
void add_edge(int f,int t)
{
G[f].push_back((Edge){t,1,G[t].size()});
G[t].push_back((Edge){f,0,G[f].size()-1});
}
void bfs(int s)
{
queue<int> q;
q.push(s);
level[s]=1;
//cout<<s<<" "<<level[s]<<endl;
while(q.size())
{
int now=q.front();q.pop();
for(int i=0;i<G[now].size();i++)
if(G[now][i].cap>0)
{
Edge e=G[now][i];
//printf("%d: %d\n",now,e.to);
if(level[e.to]<0)
{
level[e.to]=level[now]+1;
//printf("%d %d: %d %d\n",now,level[now],e.to,level[e.to]);
q.push(e.to);
}
}
}
}
int dfs(int s,int t)
{
if(s==t)
return 1;
for(int i=0;i<G[s].size();i++)
{
Edge &e=G[s][i];
if(level[e.to]>level[s]&&e.cap>0&&dfs(e.to,t))
{
e.cap-=1;
G[e.to][e.rev].cap+=1;
return 1;
}
}
return 0;
}
int max_flow(int s,int t)
{
int ans=0;
for(;;)
{
memset(level,-1,sizeof(level));
bfs(s);
//printf("%d\n",level[t]);
if(level[t]<0)
return ans;
while(dfs(s,t))
ans++;
}
}
void init()
{
for(int i=0;i<=500;i++)
G[i].clear();
}
int main()
{
int n,f,d,fx,dx,temp;
while(~scanf("%d %d %d",&n,&f,&d))
{
init();
for(int i=1;i<=n;i++)
{
scanf("%d %d",&fx,&dx);
for(int j=1;j<=fx;j++)
{
scanf("%d",&temp);
add_edge(temp,f+i);
}
for(int j=1;j<=dx;j++)
{
scanf("%d",&temp);
add_edge(i+n+f,2*n+f+temp);
}
}
for(int i=1;i<=f;i++)
add_edge(0,i);
for(int i=1;i<=d;i++)
add_edge(f+2*n+i,f+d+2*n+1);
for(int i=1;i<=n;i++)
add_edge(i+f,i+n+f);
/*
for(int i=0;i<=f+d+2*n+1;i++)
for(int j=0;j<G[i].size();j++)
if(G[i][j].cap>0)
printf("%d: %d %d\n",i,G[i][j].to,G[i][j].cap);
*/
printf("%d\n",max_flow(0,f+d+2*n+1));
}
return 0;
}
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
#include <set>
using namespace std;
#define MM(a) memset(a,0,sizeof(a))
typedef long long ll;
typedef unsigned long long ULL;
const int mod = 1000000007;
const double eps = 1e-10;
const int inf = 0x3f3f3f3f;
const int big=50000;
int max(int a,int b) {return a>b?a:b;};
int min(int a,int b) {return a<b?a:b;};
struct Edge{
int to,cap,rev;
};
int level[500];
vector<Edge> G[500];
void add_edge(int f,int t)
{
G[f].push_back((Edge){t,1,G[t].size()});
G[t].push_back((Edge){f,0,G[f].size()-1});
}
void bfs(int s)
{
queue<int> q;
q.push(s);
level[s]=1;
while(q.size())
{
int now=q.front();q.pop();
for(int i=0;i<G[now].size();i++)
{
Edge e=G[now][i];
if(level[e.to]<0&&e.cap>0)
{
level[e.to]=level[s]+1;
q.push(e.to);
}
}
}
}
int dfs(int s,int t)
{
if(s==t)
return 1;
for(int i=0;i<G[s].size();i++)
{
Edge e=G[s][i];
if(level[e.to]>level[s]&&dfs(e.to,t))
{
G[s][i].cap-=1;
G[e.to][G[s][i].rev].cap+=1;
return 1;
}
}
return 0;
}
void max_flow(int s,int t)
{
memset(level,-1,sizeof(level));
int ans=0;
for(;;)
{
bfs(s);
if(level[t]<0)
break;
while(dfs(s,t))
ans++;
}
printf("%d\n",ans);
}
int main()
{
int n,f,d,fx,dx,temp;
while(~scanf("%d %d %d",&n,&f,&d))
{
for(int i=1;i<=n;i++)
{
scanf("%d %d",&fx,&dx);
for(int j=1;j<=fx;j++)
{
scanf("%d",temp);
add_edge(temp,f+i);
}
for(int j=1;j<=dx;j++)
{
scanf("%d",&temp);
add_edge(i+n+f,2*n+f+temp);
}
}
for(int i=1;i<=f;i++)
add_edge(0,i);
for(int i=1;i<=d;i++)
add_edge(f+2*n+i,f+d+2*n+1);
max_flow(0,f+d+2*n+1);
}
return 0;
}
这篇关于poj 3281 Dining 最大流dinic 模板题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
