[网络流24题] 试题库问题 (最大流)

依然是很经典的最大流模型..还是很好想

因为一个试题只能用一次，源点$S$向试题连流量为$1$的边

因为每种类型都需要$num_{i}$个试题，所以每种类型向汇点$T$连流量为$num_{i}$的边

每个试题只能在每个类型里出现一次，每个试题向每个类型连流量为$1$的边

然后$Dinic$就行了，不会输出方案的可以看这篇博客

  1 #include <vector>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 #define N1 1050
  6 #define M1 50010
  7 #define ll long long
  8 #define dd double
  9 #define inf 0x3f3f3f3f
 10 using namespace std;
 11 
 12 int gint()
 13 {
 14     int ret=0,fh=1;char c=getchar();
 15     while(c<'0'||c>'9'){if(c=='-')fh=-1;c=getchar();}
 16     while(c>='0'&&c<='9'){ret=ret*10+c-'0';c=getchar();}
 17     return ret*fh;
 18 }
 19 
 20 int n,m,nm,S,T;
 21 struct Edge{
 22 int head[N1],to[M1<<1],nxt[M1<<1],flow[M1<<1],cte;
 23 void ae(int u,int v,int F)
 24 {
 25     cte++; to[cte]=v; flow[cte]=F;  
 26     nxt[cte]=head[u]; head[u]=cte;
 27 }
 28 }e;
 29 
 30 int que[M1<<1],hd,tl,dep[N1],cur[N1];
 31 int bfs()
 32 {
 33     int x,j,v;
 34     memset(dep,-1,sizeof(dep)); memcpy(cur,e.head,sizeof(cur));
 35     hd=1,tl=0; que[++tl]=S; dep[S]=0; 
 36     while(hd<=tl)
 37     {
 38         x=que[hd++];
 39         for(j=e.head[x];j;j=e.nxt[j])
 40         {
 41             v=e.to[j]; 
 42             if(dep[v]!=-1||e.flow[j]<=0) continue;
 43             dep[v]=dep[x]+1; que[++tl]=v;
 44         }
 45     }
 46     return dep[T]!=-1;
 47 }
 48 int dfs(int x,int limit)
 49 {
 50     int j,v,flow,ans=0;
 51     if(x==T||!limit) return limit;
 52     for(j=cur[x];j;j=e.nxt[j])
 53     {
 54         cur[x]=j; v=e.to[j];
 55         if( dep[v]==dep[x]+1 && (flow=dfs(v,min(limit,e.flow[j]))) )
 56         {
 57             limit-=flow, ans+=flow;
 58             e.flow[j]-=flow, e.flow[j^1]+=flow;
 59             if(!limit) break;
 60         }
 61     }
 62     return ans;
 63 }
 64 int num[N1],sum[N1];
 65 void Dinic()
 66 {
 67     int mxflow=0,x,j,v;
 68     while(bfs())
 69     {
 70         mxflow+=dfs(S,inf);
 71     }
 72     for(x=n+1;x<=n+m;x++)
 73         for(j=e.head[x];j;j=e.nxt[j])
 74         {
 75             v=e.to[j];
 76             if(e.flow[j]>0) sum[x]++;
 77         }
 78     for(x=n+1;x<=n+m;x++) 
 79         if(sum[x]<num[x]){ puts("No Solution!"); return; }
 80     for(x=n+1;x<=n+m;puts(""),x++)
 81         for(j=e.head[x],printf("%d: ",x-n);j;j=e.nxt[j])
 82         {
 83             v=e.to[j];
 84             if(e.flow[j]>0) printf("%d ",e.to[j]);
 85         }
 86 }
 87 
 88 int main()
 89 {
 90     scanf("%d%d",&m,&n); nm=n+m+2;
 91     int i,j,s,x,ans; S=n+m+1,T=n+m+2; e.cte=1;
 92     for(i=n+1;i<=n+m;i++) num[i]=gint(), e.ae(i,T,num[i]), e.ae(T,i,0);
 93     for(i=1;i<=n;i++)
 94     {
 95         s=gint(); e.ae(S,i,1), e.ae(i,S,0);
 96         for(j=1;j<=s;j++) 
 97             x=gint(), e.ae(i,x+n,1), e.ae(x+n,i,0);
 98     }
 99     Dinic();
100     return 0;
101 }