题目链接:https://www.luogu.org/problemnew/show/P2055
我真的觉得这道题很恶心。
考点:二分图匹配||网络流
思路:建立超级源点和汇点,分为两个集合,需要床位的为一个集合,提供床位的为第二个集合,根据相互认识的关系连边,求最大匹配。
第一个集合为:非本校学生和本校不回家的学生。第二个集合为:本校学生。
代码如下:
#include<iostream> #include<cstdio> #include<algorithm> #include<queue> #include<cstring> using namespace std; const int INF=0x3f3f3f3f; int num=1,head[100000],t,n,st[100000],re[100000],s,kn,d,ans,dep[100000]; struct E{ int next,dis,to; }e[1000000]; void add(int u,int v,int w){ e[++num].to=v; e[num].next=head[u]; e[num].dis=w; head[u]=num; } int bfs(){ queue<int>q; int u,v; memset(dep,0,sizeof(dep)); dep[s]=1; q.push(s); while(!q.empty()){ u=q.front(); q.pop(); for(int i=head[u];i;i=e[i].next){ v=e[i].to; if(!dep[v]&&e[i].dis){ dep[v]=dep[u]+1; if(v==d)return 1; q.push(v); } } } return 0; } int dfs(int u,int flow){ if(u==d)return flow; for(int i=head[u];i;i=e[i].next){ int v=e[i].to; if((dep[v]==dep[u]+1)&&e[i].dis){ int w=dfs(v,min(flow,e[i].dis)); if(w>0){ e[i].dis-=w; e[i^1].dis+=w; return w; } } } return 0; } int dinic(){ while(bfs()) ans-=dfs(s,INF); if(ans==0) return 1; else return 0; } int main(){ scanf("%d",&t); for(int o=1;o<=t;o++){ memset(st,0,sizeof(st)); memset(re,0,sizeof(re)); memset(e,0,sizeof(e)); memset(head,0,sizeof(head)); scanf("%d",&n); num=1;s=0;d=2*n+1;ans=0; for(int i=1;i<=n;i++){ scanf("%d",&st[i]); if(st[i]){ add(s,i+n,1); add(i+n,s,0); } } for(int i=1;i<=n;i++){ scanf("%d",&re[i]); if((!re[i]&&st[i])||(!st[i])){ ans++; add(i,d,1); add(d,i,0); }//需要床 } for(int i=1;i<=n;i++){ if(st[i]&&!re[i]){ add(i+n,i,1); add(i,i+n,0); } for(int j=1;j<=n;j++){ scanf("%d",&kn); if(kn){ add(i+n,j,1); add(j,i+n,0); } } } if(dinic()) printf("^_^ "); else printf("T_T "); } return 0; }
感悟:我是写的网络流。真的感觉代码能力太差了,先是dinic打错,然后发现建图建错,最后初始化初始错,还是不要盲目压行了,免得找不到错还破坏了对原始代码的记忆。