c/c++语言开发共享洛谷P2763题解

吐槽一下：蜜汁uke是什么玩意？！

题目分析：

1. 观察题面，对于给定的组卷要求，计算满足要求的组卷方案，可以发现这是一道明显的有条件的二分图匹配问题，于是考虑建模。

   • 建一个超级源点，一个超级汇点；源点与试题相连，汇点与类型相连。

   • 重点是类型的题数的建模。可以从感性来理解一下，其实这有一点限流的意思，每个类型只要求有这么多的题量，不能超出，于是考虑在类型与汇点相连的时候将容量设为类型的题数，在算最大流的时候将题量限制住，就能满足题面的要求了。(希望大家能明白我的意思 (qwq) )

   • 最后的图即为：超级源点与试题相连，容量为1；类型与对应的试题相连，容量为1；类型与超级汇点相连，容量为类型的题数。具体来说，超级源点 (s) 为节点 (1) ,试题为节点 (2—n+1)，类型为节点 (n+2—n+k+1) 超级汇点 (t) 为节点 (n+k+2) 。
2. 建模完成之后，考虑记录方案。
   • 因为 (dinic) 算法是通过 (xor;1) 来完成正向边与反向边的转变的，故正向边的 (e[i].to) 为路径终点，反向边的 (e[i;xor;1].to) 为路径起点， 所以可以通过枚举每一条边来找到相应的节点。
   • 又因为反向边的 (e[i;xor;1].v) 的初始化为0，当 (e[i;xor;1].vneq0) 时，即代表这条边是最大流跑过的边，也相当于这条边被匹配了。
   • 最后排除掉超级源点与超级汇点的情况。

3. 如果 (dinic) 跑一遍下来，ans(即最大流)依然为0，则本数据没有答案(即输出"no solution!")。

code(带详细注释):

#include<bits/stdc++.h> #define maxn 4010 #define maxm 10010 #define int long long  using namespace std; int k,n; inline void read(int &x) {     int f=1;x=0;char s=getchar();     while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}     while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}     x*=f; } int s,t; int ans=0,dep[maxn]; struct edge {     int to,next,v; }e[maxm<<1];//一定注意要开两倍空间(正反两条边)  int head[maxn],ei=1;//一定注意这里的ei为奇数  void add(int x,int y,int v) {     ei++;     e[ei].to=y;     e[ei].v=v;     e[ei].next=head[x];     head[x]=ei; } int bfs() {     queue<int>qu;     memset(dep,0,sizeof(dep));     dep[s]=1;     qu.push(s);     while(!qu.empty())     {         int fr=qu.front();         qu.pop();         for(int i=head[fr];i;i=e[i].next)         {             int to=e[i].to;             if(dep[to]!=0||e[i].v==0) continue;             qu.push(to);             dep[to]=dep[fr]+1;         }     }     return dep[t]!=0; } int dfs(int from,int maxflow) {     if(from==t) return maxflow;     int flow=0;     for(int i=head[from];i;i=e[i].next)     {         int to=e[i].to;         if(dep[to]!=dep[from]+1||e[i].v==0) continue;         int rst=dfs(to,min(maxflow-flow,e[i].v));         if(rst==0) dep[to]=0;         e[i].v-=rst;         e[i^1].v+=rst;         flow+=rst;         if(flow==maxflow) break;     }     return flow; } void dinic() {     while(bfs())     {         ans+=dfs(s,llong_max);     } } signed main() {     read(k),read(n);     s=1,t=k+n+2;//超级源点与超级汇点      for(int i=1;i<=n;i++)     {         add(s,i+1,1);         add(i+1,s,0);         //超级源点与试题相连，容量为1      }     for(int i=1,x;i<=k;i++)     {         read(x);         add(i+n+1,t,x);         add(t,i+n+1,0);         //类型与超级汇点相连，容量为类型的题数      }     for(int i=1,p;i<=n;i++)     {         read(p);         for(int j=1,x;j<=p;j++)         {             read(x);             add(i+1,x+n+1,1);             add(x+n+1,i+1,0);             //类型与对应的试题相连，容量为1         }     }     dinic();//跑dinic      if(ans==0)//没有答案      {         puts("no solution!");         return 0;     }      for(int num=1;num<=k;num++)//枚举所有类型      {         printf("%lld:",num);         for(int i=2;i<=ei;i+=2)//枚举每一条边来找到相应的节点          {             if(e[i].to!=s&&e[i].to!=t&&e[i^1].to!=s&&e[i^1].to!=t)//排除掉超级源点与超级汇点的情况             {                 if(e[i^1].v!=0)//这条边已经被匹配了                  {                     if(e[i].to-n-1==num)//判断是否为当前类型                      {                         printf("%lld ",e[i^1].to-1);                     }                 }             }         }         printf("n");     }     return 0; }

网络流注意事项：

1. 网络流关键在于建模，精髓也在建模。像本题一样的二分图匹配问题可采取我使用的建模方式：最大匹配=最大流。
2. 前向星的计数器初始化时，一定要为奇数。因为第n条边为正向边，第n+1条边为反向边，要实现 (e[i]) 为正向边，(e[i;xor;1]) 为反向边，就要保证正向边的i为奇数，即计数器要初始化为奇数。
3. 前向星边数一定要开两倍空间，因为正向边一条，反向边一条。