[BZOJ 1711]吃饭
转载请注明出处:http://danihao123.is-programmer.com/
这道题当初竟然没A……so sad
这题的建图要这么来:吃的、喝的、牛什么的统统拉进图里(不过牛本身只能同时享受一种食物,所以说点容量为1,要拆成俩点)。对于吃的,从[tex]S[/tex]向每个吃的连一条边。喝的每个向[tex]T[/tex]连一条边。牛本身按照喜好连即可(注意要拆成俩点!)。
代码:
/************************************************************** Problem: 1711 User: danihao123 Language: C++ Result: Accepted Time:20 ms Memory:864 kb ****************************************************************/ #include <cstdio> #include <cstring> #include <vector> #include <queue> using namespace std; const int maxn=405,INF=0x7f7f7f7f; namespace Dinic{ struct Edge{ int u,v,cap,flow; }; vector<Edge> edges; vector<int> G[maxn]; int m; inline void AddEdge(int u,int v,int cap){ edges.push_back((Edge){u,v,cap,0}); edges.push_back((Edge){v,u,0,0}); m=edges.size(); G[u].push_back(m-2); G[v].push_back(m-1); } bool vis[maxn]; int d[maxn]; int s,t; bool BFS(){ register int i,x; queue<int> Q; memset(vis,0,sizeof(vis)); d[s]=0; Q.push(s); vis[s]=true; while(!Q.empty()){ x=Q.front(); Q.pop(); for(i=0;i<G[x].size();i++){ Edge& e=edges[G[x][i]]; if(!vis[e.v] && e.cap>e.flow){ d[e.v]=d[x]+1; Q.push(e.v); vis[e.v]=true; } } } return vis[t]; } int cur[maxn]; int DFS(int x,int a){ if(x==t || a==0) return a; int flow=0,f; for(int& i=cur[x];i<G[x].size();i++){ Edge& e=edges[G[x][i]]; if(d[e.v]==d[x]+1){ f=DFS(e.v,min(a,e.cap-e.flow)); if(f>0){ flow+=f; e.flow+=f; edges[G[x][i]^1].flow-=f; a-=f; if(a==0) break; } } } return flow; } inline int Maxflow(int S,int T){ register int ans=0; s=S; t=T; while(BFS()){ memset(cur,0,sizeof(cur)); ans+=DFS(s,INF); } return ans; } }; int main(){ int N,F,D,f,d,x; register int i,j,t; scanf("%d%d%d",&N,&F,&D); t=2*N+F+D+1; for(i=1;i<=F;i++) Dinic::AddEdge(0,i,1); for(i=2*N+F+1;i<t;i++) Dinic::AddEdge(i,t,1); for(i=1;i<=N;i++) Dinic::AddEdge(F+2*i-1,F+2*i,1); for(i=1;i<=N;i++){ scanf("%d%d",&f,&d); for(j=1;j<=f;j++){ scanf("%d",&x); Dinic::AddEdge(x,2*i-1+F,1); } for(j=1;j<=d;j++){ scanf("%d",&x); Dinic::AddEdge(2*i+F,F+2*N+x,1); } } printf("%d\n",Dinic::Maxflow(0,t)); return 0; }