推广游戏网站怎么做,杭州市江干区建设局网站,wordpress get_the_date,苏州建设招投标网站题目描述 蒟蒻HansBug在一本语文书里面发现了一本答案#xff0c;然而他却明明记得这书应该还包含一份练习题。然而出现在他眼前的书多得数不胜数#xff0c;其中有书#xff0c;有答案#xff0c;有练习册。已知一个完整的书册均应该包含且仅包含一本书、一本练习册和一份…题目描述 蒟蒻HansBug在一本语文书里面发现了一本答案然而他却明明记得这书应该还包含一份练习题。然而出现在他眼前的书多得数不胜数其中有书有答案有练习册。已知一个完整的书册均应该包含且仅包含一本书、一本练习册和一份答案然而现在全都乱做了一团。许多书上面的字迹都已经模糊了然而HansBug还是可以大致判断这是一本书还是练习册或答案并且能够大致知道一本书和答案以及一本书和练习册的对应关系即仅仅知道某书和某答案、某书和某练习册有可能相对应除此以外的均不可能对应。既然如此HansBug想知道在这样的情况下最多可能同时组合成多少个完整的书册。 输入输出格式 输入格式 第一行包含三个正整数N1、N2、N3分别表示书的个数、练习册的个数和答案的个数。 第二行包含一个正整数M1表示书和练习册可能的对应关系个数。 接下来M1行每行包含两个正整数x、y表示第x本书和第y本练习册可能对应。1xN11yN2 第M13行包含一个正整数M2表述书和答案可能的对应关系个数。 接下来M2行每行包含两个正整数x、y表示第x本书和第y本答案可能对应。1xN11yN3 输出格式 输出包含一个正整数表示最多可能组成完整书册的数目。 输入输出样例 输入样例#15 3 4
5
4 3
2 2
5 2
5 1
5 3
5
1 3
3 1
2 2
3 3
4 3输出样例#12 说明 样例说明 如题N15N23N34表示书有5本、练习册有3本、答案有4本。 M15表示书和练习册共有5个可能的对应关系分别为书4和练习册3、书2和练习册2、书5和练习册2、书5和练习册1以及书5和练习册3。 M25表示数和答案共有5个可能的对应关系分别为书1和答案3、书3和答案1、书2和答案2、书3和答案3以及书4和答案3。 所以以上情况的话最多可以同时配成两个书册分别为书2练习册2答案2、书4练习册3答案3。 数据规模 对于数据点1, 2, 3M1M2 20 对于数据点4~10M1M2 20000 题解将书本拆点练习册连向书本1书本2连向答案再建立超级源点和超级汇点跑一边最大流即可敲这题是为了打模板的。 #includealgorithm
#includefstream
#includecstdio
#includecstdlib
#includecmath
#includecstring
#includeiostream
using namespace std;int n1,n2,n3,m1,m2,x,y,cur;//n1是书n2是练习册n3是答案m1书册m2书答案
int head[50050],lev[50050],q[50050];
struct tedge
{int to,nex,val;
}e[200010];void Add(int u,int v,int val)
{cur;e[cur].to v;e[cur].nex head[u];e[cur].val val;head[u] cur;cur;e[cur].to u;e[cur].nex head[v];e[cur].val 0;head[v] cur;
}int bfs(int S,int T)
{int h1,t1;for (int i0; i2*n1n2n311; i)lev[i] 0;q[h] S; lev[S] 1;while (ht){int uq[h];for (int ihead[u]; i!-1; ie[i].nex){int ve[i].to;if (lev[v]0e[i].val0){lev[v] lev[u]1;t; q[t]v;}}h;}return (max(lev[T],0));
}int dfs(int u,int T,int f)
{if (uT||f0) return f;int ret0,d;for (int ihead[u]; i!-1; ie[i].nex){int ve[i].to;if (lev[v]lev[u]e[i].val0){ddfs(v,T,min(f,e[i].val));retd;f-d;e[i].val-d;if (i%20) e[i-1].vald;else e[i1].vald;if (f0) break;}}return ret;
}void Dinic()
{int maxflow0;for (;bfs(1,2*n1n2n311);)maxflowdfs(1,2*n1n2n311,1e9);printf(%d\n,maxflow);
}int main()
{freopen(c.in,r,stdin);freopen(c.out,w,stdout);scanf(%d%d%d,n1,n2,n3);for (int i0; i2*n1n2n311; i)head[i] -1;scanf(%d,m1);for (int i1; im1; i){int x,y;scanf(%d%d,x,y);Add(2*n1y1,x1,1);}scanf(%d,m2);for (int i1; im2; i){int x,y;scanf(%d%d,x,y);Add(xn11,2*n1n2y1,1);}for (int i1; in1; i)Add(i1,in11,1);for (int i1; in2; i)Add(1,2*n1i1,1);for (int i1; in3; i)Add(2*n1n2i1,2*n1n2n311,1);Dinic();return 0;
} 转载于:https://www.cnblogs.com/Janous/p/7683549.html
