首页 > 代码库 > 二分图的一些题目合集
二分图的一些题目合集
妈蛋状态都被狗吃了，已经开始不自觉对着电脑发呆……被几道二分图的题亮瞎了双眼（这么弱可是gdkoi只剩一个月gdoi只剩100+天……！！）
wikioi1222信与信封问题
二分图，但是判断两个合集中的某两个点是不是只能连在一起。那么我们就在跑一边最大匹配后直接用是否可以增广来判断。如果可以增广那么这两个点是有其他方式连在一起的，否则这两个点就必须连在一起。具体做法是先去掉这两个点的边，不过那么match数组也要跟着改一下。
var map:array[0..200,0..200]of boolean; matchx,matchy:array[0..200]of longint; chose:array[0..200]of boolean; n:longint;function dfs(x:longint):boolean;var i:longint;begin for i:=1 to n do if map[x,i] and chose[i] then begin chose[i]:=false; if (matchx[i]=0) or dfs(matchx[i]) then begin matchx[i]:=x; matchy[x]:=i; exit(true); end; end; exit(false);end;procedure into;var j,k:longint;begin readln(n); fillchar(map,sizeof(map),true); while true do begin readln(j,k); if j=0 then break; map[j,k]:=false; end;end;function work:boolean;var ans,i,j:longint; flag:boolean;begin for i:=1 to n do begin fillchar(chose,sizeof(chose),true); if not dfs(i) then exit(false); end; flag:=false; for i:=1 to n do begin fillchar(chose,sizeof(chose),true); j:=matchy[i]; map[i,j]:=false; matchx[j]:=0; matchy[i]:=0; if not dfs(i) then begin writeln(i,‘ ‘,j); matchx[j]:=i; matchy[i]:=j; flag:=true; end; map[i,j]:=true; end; exit(flag);end;begin into; if not work then writeln(‘none‘); readln;end.
bzoj2150: 部落战争
最小路径覆盖，等于=点数-最大匹配，把有向图转为二分图的做法就是把每个点分成两个点，一个是入点，如果有边指向这个点则指向入点，一个是出点，如果这个点有指向其他点则出点。这样把原图的边转化一下，然后就直接最大匹配。
type arr=record toward,next:longint; end;const maxm=10000; maxn=5000;var edge:array[0..maxm]of arr; first,match:array[0..maxn]of longint; map:array[0..100,0..100]of boolean; chose:array[0..maxn]of boolean; n,m,tot,ans:longint;function check(x,y:longint):boolean;begin exit( (x>=1) and (x<=n) and (y>=1) and (y<=m) and map[x,y] );end;function calc(x,y:longint):longint;begin exit((x-1)*m+y);end;procedure addedge(j,k:longint);begin inc(tot); edge[tot].toward:=k; edge[tot].next:=first[j]; first[j]:=tot;end;function dfs(x:longint):boolean;var i,too:longint;begin i:=first[x]; while i>0 do begin too:=edge[i].toward; if chose[too] then begin chose[too]:=false; if (match[too]=0) or dfs(match[too]) then begin match[too]:=x; exit(true); end; end; i:=edge[i].next; end; exit(false);end;procedure into;var i,j,r,l:longint; ch:char;begin readln(n,m,l,r); for i:=1 to n do begin for j:=1 to m do begin read(ch); if ch=‘.‘ then map[i,j]:=true else inc(ans); end; readln; end; for i:=1 to n do for j:=1 to m do begin if check(i+l,j-r) then addedge(calc(i,j),calc(i+l,j-r)); if check(i+r,j-l) then addedge(calc(i,j),calc(i+r,j-l)); if check(i+l,j+r) then addedge(calc(i,j),calc(i+l,j+r)); if check(i+r,j+l) then addedge(calc(i,j),calc(i+r,j+l)); end;end;procedure work;var i,j:longint;begin for i:=1 to n do for j:=1 to m do if map[i,j] then begin fillchar(chose,sizeof(chose),true); if dfs(calc(i,j)) then inc(ans); end; writeln(n*m-ans);end;begin into; work; readln; readln;End.
bzoj1191: [HNOI2006]超级英雄Hero
直接跑匈牙利，不能增广就退出就行了。
const maxn=1000;var match:array[0..maxn]of longint; chose:array[0..maxn]of boolean; too:array[0..maxn,1..2]of longint; i,j,n,m:longint;function dfs(x:longint):boolean;var i,j:longint;begin for i:=1 to 2 do begin j:=too[x,i]; if chose[j] then begin chose[j]:=false; if (match[j]=0) or dfs(match[j]) then begin match[j]:=x; exit(true); end; end; end; exit(false);end;begin readln(n,m); for i:=1 to m do readln(too[i,1],too[i,2]); for i:=1 to m do begin fillchar(chose,sizeof(chose),true); if not dfs(i) then begin writeln(i-1); break; end; if i=m then writeln(m); end;end.
bzoj1854: [Scoi2010]游戏
这题有两个做法，一个是二分图，一个是并查集
二分图，类似超级英雄，直接搞。然后就会tle，问题在于那个fillchar（chose），这个太耗时了，然后就把chose改为记录第几次更新，这样每次就不用fillchar（chose）一边。这是一个新姿势。
type arr=record toward,next:longint; end;const maxm=1000000; maxn=20000;var first:array[0..maxn]of longint; match,chose:array[0..maxm]of longint; edge:array[0..maxm*2]of arr; n,tot,sum:longint;procedure addedge(j,k:longint);begin inc(tot); edge[tot].toward:=k; edge[tot].next:=first[j]; first[j]:=tot;end;function dfs(x:longint):boolean;var i,too:longint;begin i:=first[x]; while i>0 do begin too:=edge[i].toward; if chose[too]<>sum then begin chose[too]:=sum; if (match[too]=0) or dfs(match[too]) then begin match[too]:=x; exit(true); end; end; i:=edge[i].next; end; exit(false);end;procedure work;var i,j,k:longint;begin readln(n); for i:=1 to n do begin readln(j,k); addedge(j,i); addedge(k,i); end; fillchar(chose,sizeof(chose),0); sum:=1; for i:=1 to 10000 do begin if not dfs(i) then break; inc(sum); end; writeln(sum-1);end;begin work;end.
并查集，具体看hzwer大神，简直吓傻。
http://hzwer.com/2950.html
var chose:array[0..10002]of boolean; fa:array[0..10002]of longint; n,i,j,k,x1,x2:longint;procedure swap(var x,y:longint);var i:longint;begin i:=x; x:=y; y:=i;end;function find(x:longint):longint;begin if fa[x]<>x then fa[x]:=find(fa[x]); exit(fa[x]);end;begin readln(n); for i:=1 to 10002 do fa[i]:=i; for i:=1 to n do begin readln(j,k); x1:=find(j); x2:=find(k); if x1=x2 then chose[x1]:=true else begin if x1>x2 then swap(x1,x2); fa[x1]:=x2; chose[x1]:=true; end; end; for i:=1 to 10001 do if not chose[i] then begin writeln(i-1); break; end;end.
速度上看差不多。
然后发几道残念！！根本不会写！！我去一定要找时间a掉。
3218: a + b Problem http://www.lydsy.com/JudgeOnline/problem.php?id=3218
2744: [HEOI2012]朋友圈 http://www.lydsy.com/JudgeOnline/problem.php?id=2744
1443: [JSOI2009]游戏Game http://www.lydsy.com/JudgeOnline/problem.php?id=1443
3035: 导弹防御塔http://www.lydsy.com/JudgeOnline/problem.php?id=3035
还有小学生oj若干题，再也不说小学生oj水了，好多题我不会啊啊啊啊！
这还怎么参加比赛。
二分图的一些题目合集
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。