题解 P1231 【教辅的组成】

网络流经典。。。 为什么没有人写结构体前向星？？？ 来一发。。。 注： 1.数组大小开10倍，不然就像楼下说的那样会 WA。。。 2.将每个书拆点。 3.话说一开始我以为是二分图最大匹配，十分钟一发匈牙利，结果 WA 的很惨。。。 后来才发现我的匈牙利是 O（n^2），而 n<=1W 。。。 我也很想知道它是怎么 WA 的，不应该是 TLE 吗？？？ 不过，至少得出一点：此题不要用匈牙利。。。 附上 Dinic 的代码： ```cpp #include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<queue>// STL 的队列，懒人专用，懒到不想手写。。。 #define MAXN 100010//数组大小开 10 倍 #define MAX 999999999//最大值 using namespace std; int n,m,k,s,t,c=2,ans=0;//结构体前向星的起始下标我习惯于从2开始，0也没问题，但不能从1开始。。。 int head[MAXN],deep[MAXN]; struct node{//结构体前向星 int next,to,w; }a[MAXN<<1]; inline int read(){//弱弱的读优。。。 int date=0,w=1;char c=0; while(c<='0'||c>'9'){if(c=='-')w=-1;c=getchar();} while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();} return date*w; } void add(int u,int v,int w){//加边建图 a[c].to=v;a[c].w=w;正向边· a[c].next=head[u]; head[u]=c++; a[c].to=u;a[c].w=0;//反向边 a[c].next=head[v]; head[v]=c++; } bool bfs(){//广搜，应该都知道是 分层 用的吧。。。 int u,v; queue<int> q; memset(deep,0,sizeof(deep));//清空 deep[s]=1; q.push(s); while(!q.empty()){ u=q.front(); q.pop(); for(int i=head[u];i;i=a[i].next){ v=a[i].to; if(a[i].w&&!deep[v]){//枚举每一条正向边 deep[v]=deep[u]+1; if(v==t)return true;//达到汇点，说明有通路，直接跳出，开始增广路 q.push(v);//入队 } } } return false;//若无通路 } int dfs(int x,int limit){//增广路 if(x==t)return limit; int v,sum,cost=0; for(int i=head[x];i;i=a[i].next){ v=a[i].to; if(a[i].w&&deep[v]==deep[x]+1){//剪枝 sum=dfs(v,min(limit-cost,a[i].w));//递归，求能增广得流量 if(sum>0){ a[i].w-=sum; a[i^1].w+=sum;//“^”求另一条边，这就是为什么结构体前向星下标不能从1开始之原因 cost+=sum;//流量增加 if(cost==limit)break; } else deep[v]=-1;//剪枝 } } return cost; } int dinic(){//工作函数 So easy! int ans=0; while(bfs()) ans+=dfs(s,MAX); return ans; } int main(){ int f,u,v; n=read();m=read();k=read();//读入 f=read(); for(int i=1;i<=f;i++){ u=read();v=read(); add(v,u+m,1);//从答案向书加边 } f=read(); for(int i=1;i<=f;i++){ u=read();v=read(); add(u+n+m,v+n+n+m,1);//从书的拆点向习题加边 } for(int i=1;i<=n;i++)add(i+m,i+n+m,1);//将书与书的拆点连接 for(int i=1;i<=m;i++)add(n+m+k+n+1,i,1);//源点连到答案 for(int i=1;i<=k;i++)add(i+n+n+m,n+m+k+n+2,1);//习题连到汇点 s=n+m+k+n+1;t=n+m+k+n+2;//设定源点与汇点。 printf("%d\n",dinic());//解决并输出 while(1);//反抄袭 return 0; } **抄袭可耻，领悟光荣！抄袭可耻，领悟光荣！！抄袭可耻，领悟光荣！！！** ```