P2763 试题库问题【网络流24题】【最大流】【路径覆盖】

题目描述

问题描述：

假设一个试题库中有

编程任务：

对于给定的组卷要求，计算满足要求的组卷方案。

输入格式

第一行有两个正整数

第二行有

接下来的

输出格式

输出共

输入输出样例

输入 #1<button class="copy-btn lfe-form-sz-middle" data-v-370e72e2="" data-v-52f2d52f="" type="button">复制</button>

输出 #1<button class="copy-btn lfe-form-sz-middle" data-v-370e72e2="" data-v-52f2d52f="" type="button">复制</button>

1: 1 6 8
2: 7 9 10
3: 2 3 4 5

思路

　　对于这种有限制的分配问题很容易想到用网络流建图解决

　　对于这道题，显然可以把试题和类型看做成二部图的两个部分

　　因为每道题只可以选一次

　　显然这张图的边容量最大为1

　　然后对整张图跑最大流

　　如果最大流 == 需要的题数

　　说明有方案

　　如何输出方案

　　类似于前面那道飞行员问题

　　因为容量为1，只要这条边被利用过，

　　悔边的容量一定为1.

　　所以只需要枚举所有被用到的类型的悔边即可

CODE

  1 #include <bits/stdc++.h>
  2 #define dbg(x) cout << #x << "=" << x << endl
  3 #define eps 1e-8
  4 #define pi acos(-1.0)
  5 
  6 using namespace std;
  7 typedef long long LL;
  8 
  9 const int inf = 0x3f3f3f3f;
 10 
 11 template<class T>inline void read(T &res)
 12 {
 13     char c;T flag=1;
 14     while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
 15     while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
 16 }
 17 
 18 namespace _buff {
 19     const size_t BUFF = 1 << 19;
 20     char ibuf[BUFF], *ib = ibuf, *ie = ibuf;
 21     char getc() {
 22         if (ib == ie) {
 23             ib = ibuf;
 24             ie = ibuf + fread(ibuf, 1, BUFF, stdin);
 25         }
 26         return ib == ie ? -1 : *ib++;
 27     }
 28 }
 29 
 30 int qread() {
 31     using namespace _buff;
 32     int ret = 0;
 33     bool pos = true;
 34     char c = getc();
 35     for (; (c < '0' || c > '9') && c != '-'; c = getc()) {
 36         assert(~c);
 37     }
 38     if (c == '-') {
 39         pos = false;
 40         c = getc();
 41     }
 42     for (; c >= '0' && c <= '9'; c = getc()) {
 43         ret = (ret << 3) + (ret << 1) + (c ^ 48);
 44     }
 45     return pos ? ret : -ret;
 46 }
 47 
 48 const int maxn = 200007;
 49 
 50 int n, m;
 51 int s, t;
 52 
 53 struct edge{
 54     int from,to;
 55     LL cap,flow;
 56 };
 57 
 58 map<int, int> vis;
 59 
 60 struct DINIC {
 61     int head[maxn << 1], nxt[maxn << 1], edge[maxn << 1], cnt;
 62     int cap[maxn << 1], depth[maxn << 1];
 63 
 64     void init() {
 65         cnt = 1;
 66         memset(head, 0, sizeof(head));
 67     }
 68 
 69     void BuildGraph(int u, int v, int w) {
 70         ++cnt;
 71         edge[cnt] = v;
 72         nxt[cnt] = head[u];
 73         cap[cnt] = w;
 74         head[u] = cnt;
 75 
 76         ++cnt;
 77         edge[cnt] = u;
 78         nxt[cnt] = head[v];
 79         cap[cnt] = 0;
 80         head[v] = cnt;
 81     }
 82 
 83     queue<int> q;
 84 
 85     bool bfs() {
 86         memset(depth, 0, sizeof(depth));
 87         depth[s] = 1;
 88         q.push(s);
 89         while(!q.empty()) {
 90             int u = q.front();
 91             q.pop();
 92             for ( int i = head[u]; i; i = nxt[i] ) {
 93                 int v = edge[i];
 94                 if(depth[v]) {
 95                     continue;
 96                 }
 97                 if(cap[i]) {
 98                     depth[v] = depth[u] + 1;
 99                     q.push(v);
100                 }
101             }
102         }
103         return depth[t];
104     }
105 
106     int dfs(int u, int dist) {
107         if(u == t) {
108             return dist;
109         }
110         int flow = 0;
111         for ( int i = head[u]; i && dist; i = nxt[i] ) {
112             if(cap[i] == 0)
113                 continue;
114             int v = edge[i];
115             if(depth[v] != depth[u] + 1) {
116                 continue;
117             }
118             int res = dfs(v, min(cap[i], dist));
119             cap[i] -= res;
120             cap[i ^ 1] += res;
121             //printf("cap[%d]:%d\n",t, cap[t]);
122             dist -= res;
123             flow += res;
124         }
125         return flow;
126     }
127 
128     int maxflow() {
129         int ans = 0;
130         while(bfs()) {
131             ans += dfs(s, inf);
132         }
133         return ans;
134     }
135 } dinic;
136 
137 int main()
138 {
139     //freopen("data.txt", "r", stdin);
140     int k;
141     read(k); read(n);
142     dinic.init();
143     s = 0, t = n + k + 1;
144     int x;
145     for ( int i = 1; i <= k; ++i ) {
146         read(x);
147         m += x;
148         dinic.BuildGraph(n + i, t, x);
149     }
150     for ( int i = 1; i <= n; ++i ) {
151         dinic.BuildGraph(s, i, 1);
152         int p;
153         read(p);
154         for ( int j = 1; j <= p; ++j ) {
155             read(x);
156             dinic.BuildGraph(i, x + n, 1);
157         }
158     }
159     int tot = dinic.maxflow();
160     //dbg(tot);
161     if(tot != m) {
162         puts("No Solution!");
163     }
164     else {
165         for ( int i = 1; i <= k; ++i ) {
166             int u = n + i;
167             printf("%d:",i);
168             for ( int j = dinic.head[u]; j; j = dinic.nxt[j] ) {
169                 int v = dinic.edge[j];
170                 if(dinic.cap[j] && v <= n) {
171                     printf(" %d",v);
172                 }
173             }
174             printf("\n");
175         }
176     }
177     return 0;
178 }

View Code

   #include    <   bits/stdc++.h   >  
   #define    dbg(   x   ) cout    <<    #x    <<    "   =   "    << x    << endl  
   #define    eps    1   e   -   8  
   #define    pi    acos(   -   1.0   )  

   using    namespace std   ;  
   typedef    long    long LL   ;  

   const    int inf    =    0x   3f3f3f3f   ;  

   template   <   class T   >   inline    void    read(T    &   res   )  
   {  
          char c   ;T flag   =   1   ;  
          while((c   =   getchar())   <   '   0   '   ||c   >   '   9   '   )if(c   ==   '   -   '   )flag   =-   1   ;res   =c   -   '   0   '   ;  
          while((c   =   getchar())   >=   '   0   '   &&c   <=   '   9   '   )res   =res   *   10   +c   -   '   0   '   ;res   *=flag   ;  
   }  

   namespace _buff    {  
          const    size_t BUFF    =    1    <<    19   ;  
          char    ibuf   [BUFF   ],    *ib    = ibuf   ,    *ie    = ibuf   ;  
          char    getc()    {  
              if    (ib    == ie   )    {  
               ib    = ibuf   ;  
               ie    = ibuf    +    fread(ibuf   ,    1   , BUFF   , stdin   );  
              }  
              return ib    == ie    ?    -   1    :    *ib   ++   ;  
          }  
   }  

   int    qread()    {  
          using    namespace _buff   ;  
          int ret    =    0   ;  
          bool pos    =    true   ;  
          char c    =    getc();  
          for    (;    (c    <    '   0   '    || c    >    '   9   '   )    && c    !=    '   -   '   ; c    =    getc())    {  
              assert(   ~c   );  
          }  
          if    (c    ==    '   -   '   )    {  
           pos    =    false   ;  
           c    =    getc();  
          }  
          for    (; c    >=    '   0   '    && c    <=    '   9   '   ; c    =    getc())    {  
           ret    =    (ret    <<    3   )    +    (ret    <<    1   )    +    (c    ^    48   );  
          }  
          return pos    ? ret    :    -ret   ;  
   }  

   const    int maxn    =    200007   ;  

   int n   , m   ;  
   int s   , t   ;  

   struct edge   {  
          int from   ,to   ;  
       LL cap   ,flow   ;  
   };  

   map   <int   ,    int> vis   ;  

   struct DINIC    {  
          int    head   [maxn    <<    1   ],    nxt   [maxn    <<    1   ],    edge   [maxn    <<    1   ], cnt   ;  
          int    cap   [maxn    <<    1   ],    depth   [maxn    <<    1   ];  

          void    init()    {  
           cnt    =    1   ;  
              memset(head   ,    0   ,    sizeof   (head   ));  
          }  

          void    BuildGraph(   int    u   ,    int    v   ,    int    w   )    {  
              ++cnt   ;  
              edge   [cnt   ]    = v   ;  
              nxt   [cnt   ]    =    head   [u   ];  
              cap   [cnt   ]    = w   ;  
              head   [u   ]    = cnt   ;  

              ++cnt   ;  
              edge   [cnt   ]    = u   ;  
              nxt   [cnt   ]    =    head   [v   ];  
              cap   [cnt   ]    =    0   ;  
              head   [v   ]    = cnt   ;  
          }  

       queue   <int> q   ;  

          bool    bfs()    {  
              memset(depth   ,    0   ,    sizeof   (depth   ));  
              depth   [s   ]    =    1   ;  
              q   .push(s   );  
              while(   !   q   .empty())    {  
                  int u    =    q   .front();  
                  q   .pop();  
                  for    (    int i    =    head   [u   ]; i   ; i    =    nxt   [i   ]    )    {  
                      int v    =    edge   [i   ];  
                      if(   depth   [v   ])    {  
                          continue;  
                      }  
                      if(   cap   [i   ])    {  
                          depth   [v   ]    =    depth   [u   ]    +    1   ;  
                          q   .push(v   );  
                      }  
                  }  
              }  
              return    depth   [t   ];  
          }  

          int    dfs(   int    u   ,    int    dist   )    {  
              if(u    == t   )    {  
                  return dist   ;  
              }  
              int flow    =    0   ;  
              for    (    int i    =    head   [u   ]; i    && dist   ; i    =    nxt   [i   ]    )    {  
                  if(   cap   [i   ]    ==    0   )  
                      continue;  
                  int v    =    edge   [i   ];  
                  if(   depth   [v   ]    !=    depth   [u   ]    +    1   )    {  
                      continue;  
                  }  
                  int res    =    dfs(v   ,    min(   cap   [i   ], dist   ));  
                  cap   [i   ]    -= res   ;  
                  cap   [i    ^    1   ]    += res   ;  
               //printf("cap[%d]:%d\n",t, cap[t]);  
               dist    -= res   ;  
               flow    += res   ;  
              }  
              return flow   ;  
          }  

          int    maxflow()    {  
              int ans    =    0   ;  
              while(bfs())    {  
               ans    +=    dfs(s   , inf   );  
              }  
              return ans   ;  
          }  
   } dinic   ;  

   int    main()  
   {  
       //freopen("data.txt", "r", stdin);  
          int k   ;  
          read(k   );    read(n   );  
          dinic   .init();  
       s    =    0   , t    = n    + k    +    1   ;  
          int x   ;  
          for    (    int i    =    1   ; i    <= k   ;    ++i    )    {  
              read(x   );  
           m    += x   ;  
              dinic   .BuildGraph(n    + i   , t   , x   );  
          }  
          for    (    int i    =    1   ; i    <= n   ;    ++i    )    {  
              dinic   .BuildGraph(s   , i   ,    1   );  
              int p   ;  
              read(p   );  
              for    (    int j    =    1   ; j    <= p   ;    ++j    )    {  
                  read(x   );  
                  dinic   .BuildGraph(i   , x    + n   ,    1   );  
              }  
          }  
          int tot    =    dinic   .maxflow();  
       //dbg(tot);  
          if(tot    != m   )    {  
              puts(   "   No Solution!   "   );  
          }  
          else    {  
              for    (    int i    =    1   ; i    <= k   ;    ++i    )    {  
                  int u    = n    + i   ;  
                  printf(   "   %d   :   "   ,i   );  
                  for    (    int j    =    dinic   .   head   [u   ]; j   ; j    =    dinic   .   nxt   [j   ]    )    {  
                      int v    =    dinic   .   edge   [j   ];  
                      if(   dinic   .   cap   [j   ]    && v    <= n   )    {  
                          printf(   "       %d   "   ,v   );  
                      }  
                  }  
                  printf(   "   \n   "   );  
              }  
          }  
          return    0   ;  
   }  