中山网页网站设计模板,自己做的网站怎么让别人看见,苏州工业园区限电,企业名称预先核准网上申请【题意】 假设一个试题库中有 n 道试题。 每道试题都标明了所属类别。 同一道题可能有多个类别属性。现要从题库中抽取 m 道题组成试卷。并要求试卷包含指定类型的试题。 试设计一个满足要求的组卷算法。 输入文件示例input.txt3 153 3 42 1 21 31 31 31 33 1 2 32 2 32 1 31 2… 【题意】 假设一个试题库中有 n 道试题。 每道试题都标明了所属类别。 同一道题可能有多个类别属性。现要从题库中抽取 m 道题组成试卷。并要求试卷包含指定类型的试题。 试设计一个满足要求的组卷算法。 输入文件示例input.txt3 153 3 42 1 21 31 31 31 33 1 2 32 2 32 1 31 21 22 1 22 1 32 1 21 13 1 2 3 输出文件示例output.txt1: 1 6 82: 7 9 103: 2 3 4 5 【分析】 二分图多重匹配 应该是指 点可以选w[i]次边只能选一次吧。 这样就不能用匈牙利了吧。。[咦~~好像也可以就是要记录所有w次匹配的是谁 然后枚举 也可以把点拆开然后做匈牙利有空再试试 嗯最大流建边就很简单啦那就不说了。。 1 #includecstdio2 #includecstdlib3 #includecstring4 #includeiostream5 #includealgorithm6 #includequeue7 #includecmath8 using namespace std;9 #define Maxn 101010 #define INF 0xfffffff11 12 struct node13 {14 int x,y,f,o,next;15 }t[Maxn*1010];int len;16 int first[Maxn];17 18 int mymin(int x,int y) {return xy?x:y;}19 int mymax(int x,int y) {return xy?x:y;}20 21 void ins(int x,int y,int f)22 {23 t[len].xx;t[len].yy;t[len].ff;24 t[len].nextfirst[x];first[x]len;t[len].olen1;25 t[len].xy;t[len].yx;t[len].f0;26 t[len].nextfirst[y];first[y]len;t[len].olen-1;27 }28 29 int st,ed;30 queueint q;31 int dis[Maxn];32 bool bfs()33 {34 while(!q.empty()) q.pop();35 memset(dis,-1,sizeof(dis));36 q.push(st);dis[st]0;37 while(!q.empty())38 {39 int xq.front();40 for(int ifirst[x];i;it[i].next) if(t[i].f0)41 {42 int yt[i].y;43 if(dis[y]-1)44 {45 dis[y]dis[x]1;46 q.push(y);47 }48 }49 q.pop();50 }51 if(dis[ed]-1) return 0;52 return 1;53 }54 55 int ffind(int x,int flow)56 {57 if(xed) return flow;58 int now0;59 for(int ifirst[x];i;it[i].next) if(t[i].f0)60 {61 int yt[i].y;62 if(dis[y]dis[x]1)63 {64 int affind(y,mymin(flow-now,t[i].f));65 t[i].f-a;66 t[t[i].o].fa;67 nowa;68 }69 if(nowflow) break;70 }71 if(now0) dis[x]-1;72 return now;73 }74 75 void output()76 {77 for(int i1;ilen;i2)78 printf(%d-%d %d\n,t[i].x,t[i].y,t[i].f);79 }80 81 int max_flow()82 {83 int ans0;84 while(bfs())85 {86 ansffind(st,INF);87 }88 return ans;89 }90 91 int op[Maxn][Maxn];92 93 int main()94 {95 int k,n,m0;96 scanf(%d%d,k,n);97 stnk1;edst1;98 len0;99 memset(first,0,sizeof(first));
100 for(int i1;ik;i)
101 {
102 int x;
103 scanf(%d,x);
104 mx;
105 ins(ni,ed,x);
106 }
107 for(int i1;in;i)
108 {
109 int x;
110 scanf(%d,x);
111 ins(st,i,1);
112 while(x--)
113 {
114 int y;
115 scanf(%d,y);
116 ins(i,yn,1);
117 }
118 }
119 int nowmax_flow();
120 if(nowm) printf(No Solution!\n);
121 else
122 {
123 for(int i1;ik;i) op[i][0]0;
124 for(int i1;ilen;i2) if(t[i].x!stt[i].y!edt[i].f0)
125 {
126 op[t[i].y-n][op[t[i].y-n][0]]t[i].x;
127 }
128 for(int i1;ik;i)
129 {
130 printf(%d: ,i);
131 for(int j1;jop[i][0];j)
132 printf(%d ,op[i][j]);printf(\n);
133 }
134 }
135 return 0;
136 } View Code 没special judge 测不了 哭泣。。 2016-11-04 14:53:36 转载于:https://www.cnblogs.com/Konjakmoyu/p/6030278.html
