poj 3281 最大流建图

题目链接:http://poj.org/problem?id=3281

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <queue>
#include <vector> #define maxn 105
#define maxe 20000
using namespace std; const int INF = 0x3f3f3f; struct Edge{
int u,v,flow,cap;
int next;
Edge(int u=,int v=,int flow=,int cap=,int next=):
u(u),v(v),flow(flow),cap(cap),next(next) { }
}; struct Dinic{
int s,t;
int d[maxn];
int cur[maxn];
bool vis[maxn];
Edge edges[maxe];
int head[maxn],cnt; void init(){
memset(head,-,sizeof(head));
cnt = ;
} void addedge(int u,int v,int cap){
edges[cnt] = Edge(u,v,,cap,head[u]);
head[u] = cnt++;
edges[cnt] = Edge(v,u,,,head[v]);
head[v] = cnt++;
} bool bfs(){
memset(vis,,sizeof(vis));
queue<int> Q;
Q.push(s);
vis[s] = true;
d[s] = ;
while(!Q.empty()){
int u = Q.front(); Q.pop();
for(int i=head[u];i!=-;i=edges[i].next){
Edge& e = edges[i];
if(!vis[e.v] && e.cap > e.flow){
vis[e.v] = true;
d[e.v] = d[e.u] + ;
Q.push(e.v);
}
}
}
return vis[t];
} int dfs(int u,int res){
if(u == t || res == ) return res; //res 残流大小;
int flow = ,f;
for(int& i=cur[u];i!=-;i=edges[i].next){
Edge& e = edges[i];
if(d[e.v] == d[e.u] + && (f = dfs(e.v,min(res,e.cap-e.flow))) > ){
e.flow += f;
edges[i^].flow -= f;
flow += f;
res -= f;
if(res == ) break;
}
}
return flow;
} int MaxFlow(int s_,int t_){
s = s_; t = t_;
int flow = ;
while(bfs()){
for(int i=s;i<=t;i++) cur[i] = head[i];
flow += dfs(s,INF);
}
return flow;
}
}solver; int main()
{
//freopen("E:\\acm\\input.txt","r",stdin);
solver.init();
int N,F,D;
cin>>N>>F>>D;
int s = , t = F+*N+D+;
for(int i=;i<=F;i++) solver.addedge(s,i,);
for(int i=;i<=N;i++) solver.addedge(F+i,F+N+i,);
for(int i=;i<=D;i++) solver.addedge(F+*N+i,t,);
for(int i=;i<=N;i++){
int food,drink,temp;
cin>>food>>drink;
for(int j=;j<=food;j++){
cin>>temp;
solver.addedge(temp,F+i,);
}
for(int j=;j<=drink;j++){
cin>>temp;
solver.addedge(F+N+i,F+*N+temp,);
}
}
printf("%d\n",solver.MaxFlow(s,t));
}
上一篇:hdu2492 数状数组或者线段树


下一篇:解决cpplint在Python 3下没有任何输出的问题