BZOJ1433 ZJOI2009 假期的宿舍 二分图匹配

1433: [ZJOI2009]假期的宿舍

Time Limit: 10 Sec  Memory Limit: 162 MBSubmit: 2375  Solved: 1005[Submit][Status][Discuss]

Description

Input

Output

Sample Input

1 3 1 1 0 0 1 0 0 1 1 1 0 0 1 0 0

Sample Output

ˆ ˆ

HINT

对于30% 的数据满足1 ≤ n ≤ 12。对于100% 的数据满足1 ≤ n ≤ 50,1 ≤ T ≤ 20。

Source

  [ Submit][ Status][ Discuss]

-----------------------------------------------------------------

一开始看到ZJOI超害怕

后来发现是裸的二分图匹配

练一下匈牙利算法

代码如下:

#include<cstdio> #include<iostream> #include<cstring> #define cls(x) memset(x,0,sizeof(x)) #define For(i,x,y) for(int i=x;i<=y;++i) #define N 55 using namespace std; int a[N],b[N],map[N][N]; int p[5*N]; int vis[N*5];int n; bool find(int u) { For(i,1,n) { if(vis[i]||!map[u][i])continue; vis[i]=1; if(!p[i]||find(p[i])){p[i]=u;return 1;} } return 0; } void work() { memset(p,0,sizeof(p)); cin>>n;int ans=0; For(i,1,n)scanf("%d",&a[i]); For(i,1,n){scanf("%d",&b[i]);if(!a[i])b[i]=0;}int x; For(i,1,n)For(j,1,n)scanf("%d",&x),map[i][j]=(x&a[j]); For(i,1,n)For(j,1,n)if(a[i])map[i][i]=1; bool can=1; For(i,1,n) { cls(vis);if(b[i])continue; if(!find(i))can=0; } if(can)printf("^_^\n");else printf("T_T\n"); } int main() { int T;cin>>T; while(T--)work(); return 0; }

 

转载于:https://www.cnblogs.com/rwy233/p/6008034.html