刚回到家 开了二分匹配专题 手握xyl模板 奋力写写写 终于写完了一群模板题
A hdu1045
对这个图进行 行列的重写 给每个位置赋予新的行列 使不能相互打到的位置 拥有不同的行与列
然后左行右列 边是新的坐标 求最大匹配
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<map>
#include<string>
#include<vector>
#include<queue>
#include<iostream>
using namespace std;
#define L long long
char s[50][50];
int n ;
vector<int >q[50];
int a[50][50];
int b[50][50];
int m ;
bool vis[50];
int f[50];
bool fin(int u){
for(int i=0;i<q[u].size();i++){
int v =q[u][i];
if(vis[v]){
vis[v] = false;
if(f[v] == -1 || fin(f[v])){
f[v] = u ;
return true;
}
}
}
return false;
}
int xyl(){
int res = 0;
memset(f,-1,sizeof(f));
for(int i=1;i<=m;i++){
memset(vis,true,sizeof(vis));
if(fin(i)){
res ++ ;
}
}
return res ;
}
int main(){
while(scanf("%d",&n)!=EOF){
if(n == 0)break;
for(int i=1;i<=n;i++){
scanf("%s",s[i] + 1);
}
for(int i = 0; i<= 40; i ++)q[i].clear();
int cntx = 0;
int cnt1 = 0;
bool fl = false;
for(int i=1;i<=n;i++){
fl = false;
for(int j=1;j<=n;j++){
if(s[i][j] == 'X'){
fl = true;
}
else {
if(fl == true){
cntx ++ ;
fl = false;
}
a[i][j] = cntx + i;
cnt1 =a[i][j] ;
}
}
}
int cnty = 0;
int cnt2 = 0;
fl = false;
for(int j=1;j<=n;j++){
fl = false;
for(int i=1;i<=n;i++){
if(s[i][j] == 'X'){
fl = true;
}
else {
if(fl == true){
cnty ++ ;
fl = false;
}
b[i][j] = cnty + j ;
cnt2 = b[i][j] ;
}
}
}
for(int i = 1; i<=n ;i ++){
for(int j = 1; j<=n; j ++) {
if(s[i][j] != 'X'){
q[a[i][j]].push_back(b[i][j]);
}
}
}
m = max(cnt1,cnt2) ;
int ans = xyl();
printf("%d
",ans);
}
}
B hdu2444
double room的意思 不是两个房间 是双人间
所以题意就是判断二分图 顺便求最大匹配
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<map>
#include<string>
#include<vector>
#include<queue>
#include<iostream>
using namespace std;
#define L long long
vector<int >q[205];
int n , m ;
int co[205];
bool vis[205];
bool bfs(int u){
queue<int>que;
que.push(u);
co[u] = 0;
while(!que.empty()){
int f = que.front();que.pop();
for(int i = 0; i< q[f].size(); i ++){
int v = q[f][i];
if(co[v] == -1){
co[v] = co[f] ^ 1 ;
que.push(v);
}
else {
if(co[v] == co[f]){
return false;
}
}
}
}
return true;
}
int linker[205];
bool fin(int u){
for(int i=0;i<q[u].size();i++){
int v = q[u][i];
if(vis[v]){
vis[v] = false ;
if(linker[v] == -1 || fin(linker[v])){
linker[v] = u ;
return true;
}
}
}
return false;
}
int xyl(){
int res = 0;
memset(linker , -1 , sizeof(linker));
for(int i = 1; i<= n ; i ++ ){
memset(vis, true , sizeof(vis));
if(fin(i)){
res ++ ;
}
}
return res ;
}
int main(){
// freopen("in.cpp" , "r" , stdin);
while(scanf("%d%d",&n,&m)!=EOF){
for(int i = 1; i<=n ;i ++)q[i].clear();
for(int i = 1; i<=m ;i ++){
int a,b ;
scanf("%d%d",&a, &b);
q[a].push_back(b);
q[b].push_back(a);
}
memset(co, -1 , sizeof(co));
bool ok = true;
for(int i = 1; i<=n ;i ++){
if(co[i] == -1){
if(!bfs(i)){
ok = false;
}
}
}
if(ok == false){
printf("No
");
continue ;
}
int ans = xyl() ;
printf("%d
",ans/2);
}
}
C hdu1083
一边课程 一边学生 最大匹配是否等于课程
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<map>
#include<string>
#include<vector>
#include<queue>
#include<iostream>
using namespace std;
#define L long long
int n , p ;
bool vis[305];
vector <int >q[305];
int linker[305];
bool fin(int u){
for(int i = 0; i< q[u].size() ;i ++ ){
int v = q[u][i];
if(vis[v]){
vis[v] = false;
if(linker[v] == -1 || fin(linker[v])){
linker[v] = u ;
return true;
}
}
}
return false;
}
int xyl(){
int res = 0 ;
memset(linker , -1 ,sizeof(linker));
for(int i = 1; i<= p;i ++) {
memset(vis,true,sizeof(vis));
if(fin(i)){
res ++ ;
}
}
return res ;
}
int main(){
int t;
scanf("%d",&t);
while(t -- ){
scanf("%d%d",&p,&n);
for(int i = 1; i<= p; i ++){
q[i].clear() ;
}
for(int i = 1; i<= p; i ++) {
int x ;
scanf("%d" , &x) ;
for(int j = 1; j<= x; j ++ ){
int z ;
scanf("%d", &z );
q[i].push_back(z);
}
}
int ans = xyl () ;
if(ans == p){
printf("YES
");
}
else {
printf("NO
");
}
}
}
D hdu1281
不可以放车的地方不影响攻击 那就不用重新写行列了
每个坐标都是一条边 求出最大匹配之后枚举每个坐标不可用 是不是重要点
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<map>
#include<string>
#include<vector>
#include<queue>
#include<iostream>
using namespace std;
#define L long long
int n , m ;
int x ;
vector<int >q[105];
int banx,bany;
int inx[10500];
int iny[10500];
int linker[105];
bool vis[105];
bool fin(int u){
for(int i = 0; i< q[u].size() ;i ++ ) {
int v = q[u][i];
if(u == banx && v == bany){
continue;
}
if(vis[v]){
vis[v] = false;
if(linker[v] == -1 || fin(linker[v])){
linker[v] = u ;
return true;
}
}
}
return false;
}
int xyl(){
int res = 0 ;
memset(linker , -1 ,sizeof(linker)) ;
for(int i = 1; i<= n ;i ++){
memset(vis,true,sizeof(vis));
if(fin(i)){
res ++ ;
}
}
return res ;
}
int main(){
//freopen("in.cpp" , "r" , stdin);
int cas = 1;
while(scanf("%d%d%d",&n,&m,&x)!=EOF){
for(int i = 1; i<= 100; i ++)
q[i].clear() ;
for(int k = 1; k <= x ;k ++) {
int i , j ;
scanf("%d%d",&i,&j);
q[i].push_back(j);
inx[k] = i ;
iny[k] = j ;
}
banx = 0;
bany = 0;
int maxx = xyl();
int ans = 0;
for(int i = 1; i<= x ; i ++ ){
banx = inx[i];
bany = iny[i];
int res = xyl() ;
if(res != maxx){
ans ++ ;
}
}
printf("Board %d have %d important blanks for %d chessmen.
",cas ++ ,ans , maxx);
}
}
E hdu2819
这个用到了线性代数的知识
初等变换有三种 1 交换两行 2 一行*=k 3 一行 += 另一行*k
用其中的任意一种 都可以达到简化阶梯式(对角线上都是1)
并且 如果行变换可以 那么只用列变换也可以
那么 建图的方法 左边是行 右边是列 边代表左边的行 可以提供右边的列数 即有 做列数的潜力(左边的这一行经过移动 在对角线上 交点是右边的那一列)
最后linker记录的就是 经过改变后 第i行 是原来的linker[i]行
处理后输出行的变换就可以了 并且有最大匹配 = n
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<map>
#include<string>
#include<vector>
#include<queue>
#include<iostream>
using namespace std;
#define L long long
int n ;
vector<int >q[105];
bool vis[105];
int linker[105];
bool fin(int u ){
for(int i = 0; i< q[u].size(); i ++){
int v = q[u][i];
if(vis[v]){
vis[v] = false;
if(linker[v] == -1 || fin(linker[v])){
linker[v] = u;
return true;
}
}
}
return false;
}
int xyl(){
int res = 0;
memset(linker , -1 ,sizeof(linker));
for(int i = 1; i<= n ;i ++){
memset(vis, true, sizeof(vis));
if(fin(i)){
res ++ ;
}
}
return res ;
}
int f[105];
int a[105];
int b[105];
int main(){
while(scanf("%d",&n)!=EOF){
for(int i = 1; i <= n ;i ++)q[i].clear();
for(int i = 1; i <= n ;i ++){
for(int j = 1; j<= n ;j ++){
int x;
scanf("%d", &x );
if(x == 1)
q[i].push_back(j);
}
}
int pd = xyl() ;
if(pd != n){
printf("%d
", -1);
continue;
}
for(int i = 1; i<= n ;i ++)f[i] = i ;
int ans = 0;
for(int i = 1; i<= n ;i ++){
int z = linker[i];
int where = f[z];
if(where != i){
ans ++ ;
a[ans] = where ;
b[ans] = i ;
for(int j = 1; j<= n; j ++){
if(f[j] == i){
f[j] = where ;
f[z] = j ;
}
}
}
}
printf("%d
",ans);
for(int i = 1; i<= ans ;i ++){
printf("R %d %d
",a[i] , b[i]);
}
}
}
F hdu 2389
建图是容易想的 左边是人 右边是伞 最大匹配就可以了
问题在于 xyl算法的时间复杂度是VE 3000个点的情况下 稠密图会超时
在解决这类问题的时候 HK算法可以达到 E*sqrt(V)的时间复杂度
并且 在处理分层图的时候 网络流Dinic算法也可以达到E*sqrt(V)的复杂度
但是网络流也T掉了不知道为什么...
HK算法是通过每一次bfs来看 当前有没有可以进行增广的潜力 并且进行一个lv的处理
如果有潜力的话 就使用这个lv的处理 来进行增广路运算
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<map>
#include<string>
#include<vector>
#include<queue>
#include<iostream>
using namespace std;
#define L long long
int n , m ;
int p ;
int x[3050];
int y[3050];
int s[3050];
int jl[3050];
vector<int >q[3050];
int linker[3050];
bool mx[3050];
int dx[3050] , dy[3050];
int dis ;
bool vis[3050];
int INF = 1 << 28 ;
bool bfs(){
queue<int >que;
dis = INF ;
memset(dx, -1 , sizeof(dx));
memset(dy, -1 , sizeof(dy));
for(int i = 1; i <= n; i ++){
if(mx[i] == false){
que.push(i);
dx[i] = 0;
}
}
while(!que.empty()){
int f = que.front(); que.pop ();
if(dx[f] > dis )break;
for(int i = 0; i < q[f].size() ;i ++ ){
int v = q[f][i];
if(dy[v] == -1 ){
dy[v] = dx[f] + 1;
if(linker[v] == -1)dis = dy[v];
else {
dx[linker[v]] = dy[v] + 1 ;
que.push(linker[v]) ;
}
}
}
}
if(dis == INF)return false ;
else return true;
}
bool fin(int u ){
for(int i = 0; i< q[u].size(); i ++ ){
int v = q[u][i] ;
if(vis[v] && dy[v] == dx[u] + 1){
vis[v] = false;
if(linker[v] != -1 && dis == dy[v])continue;
if(linker[v] == -1 || fin(linker[v])){
linker[v] = u ;
mx[u] = true ;
return true;
}
}
}
return false ;
}
int hk(){
int res = 0;
memset(mx , false , sizeof(mx)) ;
memset(linker , -1 , sizeof(linker)) ;
while(bfs()){
memset(vis , true , sizeof(vis));
for(int i = 1 ; i<= n ;i ++){
if(mx[i] == false && fin(i)){
res ++ ;
}
}
}
return res ;
}
bool ok[3050];
int main(){
int t;
scanf("%d",&t);
int cas = 1;
while(t -- ){
memset(ok , false , sizeof(ok)) ;
scanf("%d",&p);
scanf("%d",&n);
for(int i = 1; i<=n ;i ++)q[i].clear();
for(int i = 1; i<=n ;i ++){
scanf("%d%d%d",&x[i],&y[i],&s[i]);
jl[i] = s[i] * s[i] * p * p ;
}
scanf("%d",&m);
for(int i = 1; i<=m ;i ++){
int xx , yy ;
scanf("%d%d",&xx,&yy);
for(int j = 1; j <= n ;j ++){
int dis = (xx - x[j])*(xx - x[j]) + (yy - y[j])*(yy - y[j]);
if(dis <= jl[j]){
q[j].push_back(i);
ok[j] = true;
}
}
}
int ans = hk() ;
printf("Scenario #%d:
",cas ++ );
printf("%d
",ans);
}
}
G hdu4185
对于相连的两个油田连边 答案就是最大匹配
虽然点数达到了36w 边数最大也有72w左右 需要使用HK或者Dinic
但是这道题数据很小 xyl就可以过了 .. 为什么我会知道这种事情..
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<map>
#include<string>
#include<vector>
#include<queue>
#include<iostream>
using namespace std;
#define L long long
int n ;
vector<int >q[360005];
int id[605][605];
char s[605][605];
int m ;
bool vis[360005];
int linker[360005];
bool fin(int u ){
for(int i = 0 ; i< q[u].size(); i ++){
int v = q[u][i];
if(vis[v]){
vis[v] = false;
if(linker[v] == -1 || fin(linker[v])){
linker[v] = u ;
return true;
}
}
}
return false ;
}
int xyl(){
int res = 0;
memset(linker , -1 , sizeof(linker)) ;
for(int i = 1 ; i<= m ;i ++){
for(int j = 1; j<= m ;j ++)vis[j] = true;
if(fin(i)){
res ++ ;
}
}
return res;
}
int main(){
int t;
scanf("%d",&t);
int cas = 1;
int cnt = 0;
memset(id, 0 , sizeof(id)) ;
while(t -- ){
scanf("%d" ,&n );
int minn = cnt ;
for(int i = 1 ; i<= n ; i ++){
scanf("%s", s[i] + 1);
}
for(int i = 1 ; i<= n ; i ++){
for(int j = 1; j<= n ; j ++){
if(s[i][j] == '#'){
id[i][j] = ++ cnt ;
}
}
}
m = cnt - minn ;
for(int i = 1; i<= m ;i ++){
q[i].clear() ;
}
for(int i = 1; i<= n ; i ++ ){
for(int j = 1; j <= n ;j ++){
if(id[i][j] > minn){
if(id[i+1][j] > minn){
int u = id[i][j] - minn ;
int v = id[i+1][j] - minn ;
q[u].push_back(v) ;
q[v].push_back(u) ;
}
if(id[i][j+1] > minn){
int u = id[i][j] - minn ;
int v = id[i][j+1] - minn ;
q[u].push_back(v) ;
q[v].push_back(u) ;
}
}
}
}
int ans = xyl();
printf("Case %d: %d
",cas ++ , ans/2);
}
}
H hdu1054
求一下最小点覆盖就可以了 最小点覆盖 = 最大匹配
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<map>
#include<string>
#include<vector>
#include<queue>
#include<iostream>
using namespace std;
#define L long long
int n ;
vector<int >q[50000];
int linker[50000];
bool vis[50000];
bool fin(int u){
for(int i = 0 ; i< q[u].size() ; i ++ ){
int v = q[u][i];
if(vis[v]){
vis[v] = false;
if(linker[v] == -1 || fin(linker[v])){
linker[v] = u ;
return true ;
}
}
}
return false ;
}
int xyl(){
int res = 0;
memset(linker, -1 ,sizeof(linker));
for(int i = 0; i< n ;i ++){
memset(vis, true , sizeof(vis));
if(fin(i))res ++ ;
}
return res ;
}
int main(){
while(scanf("%d",&n)!=EOF){
for(int i = 0; i< n ;i ++)q[i].clear() ;
for(int i = 1 ;i<= n ; i ++){
int u ;
int m ;
scanf("%d:(%d)",&u , & m);
for(int j = 1 ; j<= m ; j ++){
int x;
scanf("%d",&x);
q[u].push_back(x);
q[x].push_back(u);
}
}
int ans = xyl();
printf("%d
",ans/2);
}
}
J hdu1151 & K poj2594
题目所求 一个DAG的最小不相交路径 = DAG中的顶点 - 二分图的最大匹配
将最小相交路径转化为最小不相交路径的办法 ： 如果a可以到达b 那么a到b有一条边
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<map>
#include<string>
#include<vector>
#include<queue>
#include<iostream>
using namespace std;
#define L long long
int n ;
int m ;
vector<int >q[50000];
bool a[150][150];
int linker[150];
bool vis[150];
bool fin(int u){
for(int i = 0; i < q[u].size() ;i ++ ){
int v = q[u][i];
if(vis[v]){
vis[v] = false ;
if(linker[v] == -1 || fin(linker[v])){
linker[v] = u ;
return true;
}
}
}
return false ;
}
int xyl(){
int res = 0;
memset(linker , -1 , sizeof(linker)) ;
for(int i = 1; i <= n ; i ++ ){
memset(vis , true ,sizeof(vis)) ;
if(fin(i)){
res ++ ;
}
}
return res ;
}
int main(){
int t;
scanf("%d",&t);
while(t--){
scanf("%d%d",&n, &m);
for(int i = 1; i <= n ;i ++)q[i].clear();
memset(a, false , sizeof(a));
for(int i = 1; i <= m ; i ++ ){
int u , v;
scanf("%d%d",&u , &v );
a[u][v] = true ;
}
for(int i = 1; i<= n ;i ++){
for(int j = 1; j <= n; j ++){
for(int k = 1; k <= n ;k ++){
if(a[i][k] == true && a[k][j] == true){
a[i][j] = true;
}
}
}
}
for(int i = 1; i<= n ;i ++) {
for(int j = 1 ; j <= n ;j ++){
if(a[i][j]){
q[i].push_back(j) ;
}
}
}
int maxx = xyl() ;
int ans = n - maxx ;
printf("%d
",ans) ;
}
}
L hdu3829
因为题目限定了一个人的hate与love的相反 那么可以将孩子分为两部分 一部分喜欢狗 一部分喜欢猫
如果矛盾是边 那么满足二分图
求这个二分图的最大独立点集就可以了
最大独立点集 ： 一个二分图中的点的集合 里面的所有的点相互之间没有边
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<map>
#include<string>
#include<vector>
#include<queue>
#include<iostream>
using namespace std;
#define L long long
int n , m , p;
vector<int >q[505];
int linker[505];
bool vis[505];
struct node {
char l ;
int num1 ;
char h ;
int num2 ;
int id ;
}a[505];
bool fin(int u){
for(int i = 0; i< q[u].size() ;i ++ ){
int v = q[u][i];
if(vis[v]){
vis[v] = false ;
if(linker[v] == -1 || fin(linker[v])){
linker[v] = u ;
return true;
}
}
}
return false ;
}
int cntc ;
int cntd ;
int xyl(){
int res = 0;
memset(linker , -1 ,sizeof(linker)) ;
for(int i = 1 ; i <= cntc ; i ++ ){
memset(vis , true , sizeof(vis));
if(fin(i))
res ++ ;
}
return res ;
}
int main(){
while(scanf("%d%d%d",&n,&m,&p)!=EOF){
for(int i = 1; i<= p ; i ++)q[i].clear();
cntc = 0;
cntd = 0;
for(int i = 1; i<= p ; i ++){
char s[50];
scanf("%s,",s);
a[i].l = s[0] ;
a[i].num1 = 0;
int len = strlen(s);
for(int j = 1 ; j < len ; j ++)a[i].num1 *= 10 , a[i].num1 += ( s[j] - '0' );
scanf("%s,",s);
a[i].h = s[0] ;
a[i].num2 = 0;
len = strlen(s);
for(int j = 1 ; j < len ; j ++)a[i].num2 *= 10 , a[i].num2 += ( s[j] - '0' );
if(a[i].l == 'C'){
cntc ++ ;
a[i].id = cntc;
}
else {
cntd ++ ;
a[i].id = cntd ;
}
}
for(int i = 1; i <= p ; i ++ ){
for(int j = 1 ; j <= p ; j ++ ){
if((a[i].l == a[j].h && a[i].num1 == a[j].num2) || (a[i].h == a[j].l && a[i].num2 == a[j].num1)) {
if(a[i].l == 'C'){
q[a[i].id].push_back(a[j].id) ;
}
else {
q[a[j].id].push_back(a[i].id);
}
}
}
}
int ans = xyl() ;
printf("%d
", p - ans) ;
}
}
经过几天的手速练习 发现二分图难在建模 代码是很套路的东西 交给队里最菜的主代码手就可以了
所以 虽然我做了很多模板题 但是 我仍然训练了我在队里的担当 ...
剩下的明天开始做吧 ...