奇趣网做网站,中国菲律宾南海开战,wordpress没有外观,惠州免费建站模板传送门#xff1a;Here 题意#xff1a;有K种类型的共N道试题用来出卷子#xff0c;要求卷子须有M道试题。已知每道题属于p种类型#xff0c;每种类型的试题必须有且仅有k[i]道。现问出这套试卷的一种具体方案 思路分析 昨天打了一天的Dinic#xff0c;今天又打了…传送门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]1level[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);Kr,Nr;S 0, T NK2;memset(first, -1, sizeof(first));for(int i 1; i K; i){xr;Mx;add(S, iN, x, 0);add(iN, S, 0, 0);}for(int i 1; i N; i){pr;for(int j 1; j p; j){xr;add(xN, i, 1, 0);add(i, xN, 0, 0);}add(i, T, 1, 0);add(T, i, 0, 0);}Dinic();int c;for(int i 1; i K; i){c iN;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;
} 转载于:https://www.cnblogs.com/qixingzhi/p/9420874.html
