盱眙在仕德伟做网站的有几家,赣州网络优化,从网上下载的网站源码怎么用,吸引人的软文月老的难题 时间限制#xff1a;1000 ms | 内存限制#xff1a;65535 KB难度#xff1a;4描述月老准备给n个女孩与n个男孩牵红线#xff0c;成就一对对美好的姻缘。 现在#xff0c;由于一些原因#xff0c;部分男孩与女孩可能结成幸福的一家#xff0c;部分可能不会结… 月老的难题 时间限制1000 ms | 内存限制65535 KB 难度4 描述 月老准备给n个女孩与n个男孩牵红线成就一对对美好的姻缘。 现在由于一些原因部分男孩与女孩可能结成幸福的一家部分可能不会结成幸福的家庭。 现在已知哪些男孩与哪些女孩如果结婚的话可以结成幸福的家庭月老准备促成尽可能多的幸福家庭请你帮他找出最多可能促成的幸福家庭数量吧。 假设男孩们分别编号为1~n,女孩们也分别编号为1~n。 输入第一行是一个整数T,表示测试数据的组数(1T400) 每组测试数据的第一行有两个整数n,K其中男孩的人数与女孩的人数都是n。(n500,K10 000) 随后的K行每行有两个整数i,j表示第i个男孩与第j个女孩有可能结成幸福的家庭。(1i,jn)输出对每组测试数据输出最多可能促成的幸福家庭数量样例输入 1
3 4
1 1
1 3
2 2
3 2 样例输出 2 View Code #includestdio.h
#includestring.h
#define N 10010
#define M 510
int num;
int link[M];
int head[M],next[N],key[N];
bool use[M];void add(int u,int v)
{key[num]v;next[num]head[u];head[u]num;
}bool find(int u)
{int i,temp;for(ihead[u];i!-1;inext[i]){tempkey[i];if(!use[temp]){use[temp]true;if(link[temp]-1||find(link[temp])){link[temp]u;return true;}}}return false;
}int main()
{int T,i,a,b,n,k,ans;scanf(%d,T);while(T--){memset(link,-1 ,sizeof(link));memset(head,-1,sizeof(head));num0;scanf(%d%d,n,k);for(i0;ik;i){scanf(%d%d,a,b);add(a,b);}ans0;for(i1;in;i){memset(use,false,sizeof(use));if(find(i))ans;}printf(%d\n,ans);}return 0;
} 真想骂娘啦一个变量搞错WA了两个小时还是对算法的不够熟悉造成的。 这个题的特别之处是男女编号相同在构建增广路的时候比较特别用hash图存储了 转载于:https://www.cnblogs.com/zibuyu/archive/2013/03/17/2964981.html
