链接
bzoj 1433: [ZJOI2009] 假期的宿舍
题解
构建二分图, 每个人需要住校的人连认识的人的空床和自己的床,
匈牙利算法二分图匹配
注意清空上组数据 ORZ
代码
- #include<cstdio>
- #include<cstring>
- #include<algorithm>
- inline int read() {
- int x=0;
- char c=getchar();
- while(c<'0'||c>'9') c=getchar();
- while(c<='9'&&c>='0')x=x*10+c-'0',c=getchar();
- return x;
- }
- const int maxn = 10007;
- int stdd=0,T;
- int stu[maxn],lev[maxn],vis[maxn],link[maxn];
- struct node {
- int v,next;
- }edge[maxn];int num,head[maxn];
- void add_edge(int u,int v) {edge[++num].v=v;edge[num].next=head[u];head[u]=num;}
- bool find(int x,int f) {
- for(int i=head[x];i;i=edge[i].next) {
- int v=edge[i].v;
- if(vis[v]==f)continue;
- vis[v]=f;
- if(link[v]==-1||find(link[v],f)) {
- link[v]=x;return true;
- }
- }
- return false;
- }
- void solve(int n) {
- int ans=0;
- for(int i=1;i<=n;++i)
- //if(lev[i]<=0)
- if(find(i,i))ans++;
- if(ans==stdd)puts("^_^");
- else puts("T_T");
- }
- int main() {
- T=read();
- for(int n;T--;) {
- stdd=0;
- memset(vis,0,sizeof vis);
- memset(lev,-1,sizeof lev);
- memset(head,0,sizeof head);
- memset(link,-1,sizeof link);num=0;
- n=read();
- for(int i=1;i<=n;++i) stu[i]=read();
- for(int p,i=1;i<=n;++i) {
- p=read();
- if(stu[i]) {
- if(!p) stdd++,add_edge(i,n+i);
- lev[i]=p;
- }
- else stdd++;
- }
- for(int p,i=1;i<=n;++i)
- for(int j=1;j<=n;++j) {
- p=read();
- if(!p)continue;
- if(((stu[i]&&!lev[i])||!stu[i])&&stu[j])add_edge(i,n+j);
- }
- solve(n);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2494499.html