danihao123

搜索

音乐播放器

RSS

RSS Link

计数器

29173

[BZOJ 1433]假期的宿舍

2016年9月27日 13:06 | Comments(0) | Category:题解 | Tags:

这几乎是个二分图匹配的裸题了……

不过有很多细节问题,比如说题面里提到的那些。还有多组数据的话注意清理数组。

代码:

/**************************************************************
    Problem: 1433
    User: danihao123
    Language: C++
    Result: Accepted
    Time:68 ms
    Memory:824 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
const int maxn=55;
bool G[maxn][maxn];
int n,m;
int Pei[maxn];
bool vis[maxn];
bool DFS(int x){
    int i;
    for(i=1;i<=m;i++)
        if(G[x][i] && !vis[i]){
            vis[i]=true;
            if(!Pei[i] || DFS(Pei[i])){
                Pei[i]=x;
                return true;
            }
        }
    return false;
}
int Hungray(){
    register int i,ans=0;
    memset(Pei,0,sizeof(Pei));
    for(i=1;i<=n;i++){
        memset(vis,0,sizeof(vis));
        if(DFS(i))
            ans++;
    }
    return ans;
}
 
int Per[maxn],Bed[maxn];
bool isStudent[maxn],Back[maxn];
int main(){
    int T,N,u,v;
    register int i,j;
    scanf("%d",&T);
    while(T--){
        n=m=0;
        scanf("%d",&N);
        memset(G,0,sizeof(G));
        memset(Per,0,sizeof(Per));
        memset(Bed,0,sizeof(Bed));
        memset(isStudent,0,sizeof(isStudent));
        memset(Back,0,sizeof(Back));
        for(i=1;i<=N;i++){
            scanf("%d",&u);
            isStudent[i]=u;
        }
        for(i=1;i<=N;i++){
            scanf("%d",&u);
            if(isStudent[i]){
                Back[i]=u;
            }
        }
        for(i=1;i<=N;i++){
            if(isStudent[i]){
                Bed[i]=++m;
                if(!Back[i]){
                    Per[i]=++n;
                }
            }else{
                Per[i]=++n;
            }
        }
        for(i=1;i<=N;i++){
            if(isStudent[i]){
                G[Per[i]][Bed[i]]=true;
            }
            for(j=1;j<=N;j++){
                scanf("%d",&v);
                if(v && isStudent[j]){
                    G[Per[i]][Bed[j]]=true;
                }
            }
        }
        if(Hungray()==n)
            puts("^_^");
        else
            puts("T_T");
    }
    return 0;
}

[POJ 2446]Chessboard

2016年9月20日 13:00 | Comments(0) | Category:题解 | Tags:

很容易看出是二分图最大匹配,可是怎么建图呢……

我们可以考虑把一个点的横纵坐标相加,和为偶数者称之为偶数点,反之为奇数点。我们发现,每个骨牌都正好覆盖了一个奇数点和一个偶数点。于是乎就能把点分为两个集合了,建图就很方便了。

代码:

#include <cstdio>
#include <cstring>
const int maxn=35,maxm=520;
bool G[maxm][maxm];

// Hungray
int odd_cnt=0,even_cnt=0;
bool vis[maxm];
int GirlFriend[maxm];
bool DFS(int x){
    int i;
    for(i=1;i<=even_cnt;i++)
        if(G[x][i] && !vis[i]){
            vis[i]=true;
            if(!GirlFriend[i] || DFS(GirlFriend[i])){
                GirlFriend[i]=x;
                return true;
            }
        }
    return false;
}
inline int Hungray(){
    register int i,ans=0;
    for(i=1;i<=odd_cnt;i++){
        memset(vis,0,sizeof(vis));
        if(DFS(i))
            ans++;
    }
    return ans;
}

int n,m;
bool isHole[maxn][maxn];
int ct[maxn][maxn];
inline int AddPoint(int a,int b,int x,int y){
	if(ct[x][y])
		if(!isHole[x][y])
			G[ct[a][b]][ct[x][y]]=true;
}
int main(){
	int k,x,y;
	register int i,j,tot;
	scanf("%d%d%d",&m,&n,&k);
	tot=m*n-k;
	if(1&tot){
		puts("NO");
		return 0;
	}
	for(i=1;i<=k;i++){
		scanf("%d%d",&x,&y);
		isHole[y][x]=true;
	}
	for(i=1;i<=m;i++)
		for(j=1;j<=n;j++){
			if(isHole[i][j])
				continue;
			if(1&(i+j)){
				ct[i][j]=++odd_cnt;
			}else{
				ct[i][j]=++even_cnt;
			}
		}
	for(i=1;i<=m;i++)
		for(j=1;j<=n;j++){
			if(!isHole[i][j] && 1&(i+j)){
				AddPoint(i,j,i-1,j);
				AddPoint(i,j,i+1,j);
				AddPoint(i,j,i,j-1);
				AddPoint(i,j,i,j+1);
			}
		}
	if(Hungray()==(tot/2)){
		puts("YES");
	}else{
		puts("NO");
	}
	return 0;
}

[BZOJ 1191]超级英雄

2016年9月04日 19:18 | Comments(0) | Category:题解 | Tags:

看样子是裸的二分图匹配。

不过注意,选手按顺序答题,只要有一个题打不下来,就淘汰了。这个要做特殊处理,这样的话好像匈牙利算法就比较方便了。

代码:

/**************************************************************
    Problem: 1191
    User: danihao123
    Language: C++
    Result: Accepted
    Time:28 ms
    Memory:1812 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=1005;
bool G[maxn][maxn];
int Pei[maxn];
bool vis[maxn];
int n,m;
bool DFS(int x){
    int i;
    for(i=0;i<n;i++){
        if(G[x][i] && !vis[i]){
            vis[i]=true;
            if(!Pei[i] || DFS(Pei[i])){
                Pei[i]=x;
                return true;
            }
        }
    }
    return false;
}
inline int Hungray(){
    register int i,ans=0;
    for(i=1;i<=m;i++){
        memset(vis,0,sizeof(vis));
        if(DFS(i))
            ans++;
        else
            break;
    }
    return ans;
}
int main(){
    int u,v;
    register int i;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++){
        scanf("%d%d",&u,&v);
        G[i][u]=true;
        G[i][v]=true;
    }
    printf("%d\n",Hungray());
    return 0;
}


[POJ 1274]The Perfect Stall

2016年8月28日 17:33 | Comments(0) | Category:题解 | Tags:

很裸的二分图匹配辣~

不过这是我第一次写匈牙利算法……囧

还有时隔多年再次写了一次邻接矩阵QwQ

代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=201,maxm=40001;
bool G[maxn][maxn];

// Hungray
int n,m;
bool vis[maxn];
int GirlFriend[maxn];
bool DFS(int x){
    int i;
    for(i=1;i<=m;i++)
        if(G[x][i] && !vis[i]){
            vis[i]=true;
            if(!GirlFriend[i] || DFS(GirlFriend[i])){
                GirlFriend[i]=x;
                return true;
            }
        }
    return false;
}
inline int Hungray(){
    register int i,ans=0;
    for(i=1;i<=n;i++){
        memset(vis,0,sizeof(vis));
        if(DFS(i))
            ans++;
    }
    return ans;
}

int main(){
    register int i,j;
    int k,temp;
    while(scanf("%d%d",&n,&m)!=EOF){
        memset(G,0,sizeof(G));
        memset(GirlFriend,0,sizeof(GirlFriend));
        for(i=1;i<=n;i++){
            scanf("%d",&k);
            for(j=1;j<=k;j++){
                scanf("%d",&temp);
                G[i][temp]=true;
            }
        }
        printf("%d\n",Hungray());
    }
    return 0;
}