题目 没错这也是板子题，我还是没建成图，没错我还是看的别人的代码AC的。我就是废物。 推荐一下学长的博客，关于图论的写的挺好的。 https://blog.csdn.net/Zhang_sir00/article/details/105019272 题目解释 n个牛，m种饮料，k种食物，每头牛有自己喜欢的食物，和饮料。现在农场主想尽量满足牛对喜欢的食物和饮料的需求，问这m种饮料，和k种食物最多满足几头牛？（这牛的地位感觉比我的家庭地位还高，呜呜呜~） 当时脑子一片空白这图能建？？？后来想到了开个超大数组用不同的区间段来建图。然后WA了。。然后就去看学长的代码了，发现的确是这样不过我建的有问题。。 没错这就是学长嘴中的简单构图，果然我是fw，有了这个图应该就知道怎么建图了。 AC代码
#include<iostream> #include<cstring> #include<cmath> #include<cstdio> #include<algorithm> #include<queue> #define mem(a,b) memset(a,b,sizeof(a)) #define MAX 660 #define inf 0x1f3f3f3f using namespace std; struct node{ int to,next,v; }edge[MAX<<7]; int cnt,n,f,d,s,e; int vis[MAX],head[MAX]; void init() { mem(head,-1); cnt=0; s=0; } void addedge(int from,int to,int value) { edge[cnt]={to,head[from],value}; head[from]=cnt++; } int bfs() { mem(vis,0); queue<int> q; vis[s]=1; q.push(s); while(q.size()) { int u=q.front(); q.pop(); for(int i=head[u];~i;i=edge[i].next) { int to=edge[i].to; if(edge[i].v==0||vis[to]) continue; vis[to]=vis[u]+1; q.push(to); } } return vis[e]; } int dfs(int u,int flow) { if(u==e||flow==0) return flow; for(int i = head[u];i!=-1;i=edge[i].next) { int to =edge[i].to; int v = edge[i].v; if(vis[to]!=vis[u]+1||v==0) continue; int k = dfs(to,min(flow,v)); if(k>0) { edge[i].v-=k; edge[i^1].v+=k; return k; } } return 0; } void dinic() { int ans=0; int k; while(bfs()) { while((k=dfs(s,inf))>0) ans+=k; } printf("%d\n",ans); } int main() { // init(); scanf("%d %d %d",&n,&f,&d); e=2*(n+f+d)+1; for(int i = 1 ; i<=f;i++) { addedge(s,i,inf); addedge(i,s,0); } for(int i = 1 ; i<=f;i++) { addedge(i,i+f,1); addedge(i+f,i,0); } for(int i = 1 ; i<=n;i++) { addedge(2*f+i,2*f+n+i,1); addedge(2*f+n+i,2*f+i,0); } for(int i = 1 ; i<=d;i++) { addedge(2*f+2*n+i,2*f+2*n+d+i,1); addedge(2*f+2*n+d+i,2*f+2*n+i,0); } for(int i = 1 ; i<=d;i++) { addedge(2*f+2*n+d+i,e,1); addedge(e,2*f+2*n+d+i,0); } for(int i = 1 ; i<=n ; i++) { int a,b,c; scanf("%d %d",&a,&b); for(int j = 1 ; j<=a;j++) { scanf("%d",&c); addedge(f+c,2*f+i,inf); addedge(2*f+i,f+c,0); } for(int j =1;j<=b;j++) { scanf("%d",&c); addedge(2*f+n+i,2*f+2*n+c,inf); addedge(2*f+2*n+c,2*f+n+i,0); } } dinic(); return 0; }