「網絡流24題」試題庫問題

傳送門：>Here<

題意：有K種類型的共N道試題用來出卷子，要求卷子須有M道試題。已知每道題屬于p種類型，每種類型的試題必須有且僅有k[i]道。現問出這套試卷的一種具體方案

思路分析

昨天打了一天的Dinic，今天又打了一遍。板子倒是很熟了……

這題很簡單，沒看題解就想出來了（貌似建圖方法還和題解不太一樣？2333）

首先不要被以前做的題束縛了，這可是網絡流，容量不一定為1！于是很容易想到從源點往每種類型的題那里連容量為k[i]的邊，然后每種類型再連題目（容量為1），最后連回匯點（容量為1）即可。

最后統計答案就是看每一種類型的題有容量的出邊即可

Code

沒有細節，一遍AC（甚至調試都沒有……）

/*By DennyQi*/
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
#define  r  read()
#define  Max(a,b)  (((a)>(b)) ? (a) : (b))
#define  Min(a,b)  (((a)<(b)) ? (a) : (b))
using namespace std;
typedef long long ll;
const int MAXN = 10010;
const int MAXM = 10010;
const int INF = 1061109567;
inline int read(){int x = 0; int w = 1; register int c = getchar();while(c ^ '-' && (c < '0' || c > '9')) c = getchar();if(c == '-') w = -1, c = getchar();while(c >= '0' && c <= '9') x = (x << 3) +(x << 1) + c - '0', c = getchar(); return x * w;
}
int K,N,M,S,T,x,p;
int first[MAXM*2],nxt[MAXM*2],to[MAXM*2],cap[MAXM*2],flow[MAXM*2],num_edge=-1;
int level[MAXN],cur[MAXN];
queue <int> q;
inline void add(int u, int v, int c, int f){to[++num_edge] = v;cap[num_edge] = c;flow[num_edge] = f;nxt[num_edge] = first[u];first[u] = num_edge;
}
inline bool BFS(){memset(level, 0, sizeof(level));while(!q.empty()) q.pop();q.push(S);level[S] = 1;int u,v;while(!q.empty()){u = q.front(); q.pop();for(int i = first[u]; i!=-1; i = nxt[i]){v = to[i];if(!level[v] && cap[i]-flow[i]>0){level[v] = level[u] + 1;q.push(v);}}}return level[T] != 0;
}
int DFS(int u, int a){if(u == T || a == 0) return a;int ans = 0, _f,v;for(int& i = cur[u]; i != -1; i = nxt[i]){v = to[i];if(level[u]+1==level[v] && cap[i]-flow[i]>0){_f = DFS(v, Min(a,cap[i]-flow[i]));ans += _f, a -= _f;flow[i] += _f, flow[i^1] -= _f;if(a == 0) break;}}return ans;
}
inline void Dinic(){int ans = 0;while(BFS()){for(int i = S; i <= T; ++i) cur[i] = first[i];ans += DFS(S, INF);}
}
int main(){
//    freopen(".in","r",stdin);K=r,N=r;S = 0, T = N+K+2;memset(first, -1, sizeof(first));for(int i = 1; i <= K; ++i){x=r;M+=x;add(S, i+N, x, 0);add(i+N, S, 0, 0);}for(int i = 1; i <= N; ++i){p=r;for(int j = 1; j <= p; ++j){x=r;add(x+N, i, 1, 0);add(i, x+N, 0, 0);}add(i, T, 1, 0);add(T, i, 0, 0);}Dinic();int c;for(int i = 1; i <= K; ++i){c = i+N;printf("%d: ",i);for(int j = first[c]; j != -1; j = nxt[j]){if(cap[j]-flow[j]==0 && cap[j] == 1){printf("%d ", to[j]);}}printf("\n");}return 0;
}

?