剛學(xué)了匈牙利正好練練手（我不會(huì)說(shuō)一開(kāi)始我寫(xiě)錯(cuò)了）（怕不是寒假就講了可是我不會(huì)）

把人看做左部點(diǎn)，床看作右部點(diǎn)

建圖：（！！在校相當(dāng)于有床，不在校相當(dāng)于沒(méi)有床 但是要來(lái)學(xué)校）

　　1.在校的 不走的人 自己和自己的床連邊；

　　2.不在校的人或在校不回家的人 和 認(rèn)識(shí)的 并且?在校的人 的床 連邊；

于是統(tǒng)計(jì)一下需要幾張床，再跑匈牙利算法、、、看看夠不夠。

#include<cstdio> #include<iostream> #include<cstring> #define R register int using namespace std; inline int g() {R ret=0; register char ch; while(!isdigit(ch=getchar()));do ret=ret*10+(ch^48); while(isdigit(ch=getchar())); return ret; } int t,n,cnt,ans,tot; int vr[10010],nxt[10010],fir[101],pre[101]; inline void add(int u,int v) {vr[++cnt]=v,nxt[cnt]=fir[u],fir[u]=cnt;} bool vis[101],h[101],s[101]; bool dfs(int u) {for(R i=fir[u];i;i=nxt[i]) {R v=vr[i];if(vis[v]) continue; vis[v]=true;if(!pre[v]||dfs(pre[v])) {pre[v]=u; return true;}} return false; } signed main() {t=g();while(t--) { cnt=tot=ans=0;memset(pre,0,sizeof(pre)),memset(fir,0,sizeof(fir)),memset(nxt,0,sizeof(nxt)),memset(vr,0,sizeof(vr));n=g(); for(R i=1;i<=n;++i) s[i]=g();for(R i=1;i<=n;++i) {h[i]=g(); if(!h[i]&&s[i]) add(i,i+n),add(i+n,i);}for(R i=1;i<=n;++i) for(R j=1,x;j<=n;++j) {x=g(); if(x&&i!=j) {if(s[j]&&((s[i]&&!h[i])||!s[i])) add(i,j+n),add(j+n,i);if(s[i]&&((s[j]&&!h[j])||!s[j])) add(j,i+n),add(i+n,j);}}for(R i=1;i<=n;++i) if(!s[i]||(s[i]&&!h[i])) ++tot;for(R i=1;i<=n;++i) if(!s[i]||(s[i]&&!h[i])) {memset(vis,0,sizeof(vis)); ans+=dfs(i);} ans==tot?printf("^_^\n"):printf("T_T\n");} }

然而有種更厲害的建圖，但是我不會(huì)。。。哪位大佬給講講QAQ，如下：

#include<cstdio> #include<iostream> #include<cstring> #define R register int using namespace std; inline int g() {R ret=0; register char ch; while(!isdigit(ch=getchar()));do ret=ret*10+(ch^48); while(isdigit(ch=getchar())); return ret; } int t,n,cnt,ans,tot; int vr[2510],nxt[2510],fir[51],pre[51]; inline void add(int u,int v) {vr[++cnt]=v,nxt[cnt]=fir[u],fir[u]=cnt;} bool vis[51],h[51],s[51]; bool dfs(int u) {for(R i=fir[u];i;i=nxt[i]) {R v=vr[i];if(vis[v]) continue; vis[v]=true;if(!pre[v]||dfs(pre[v])) {pre[v]=u; return true;}} return false; } signed main() {t=g();while(t--) { cnt=tot=ans=0;memset(pre,0,sizeof(pre)),memset(fir,0,sizeof(fir)),memset(nxt,0,sizeof(nxt)),memset(vr,0,sizeof(vr));n=g(); for(R i=1;i<=n;++i) s[i]=g();for(R i=1;i<=n;++i) {h[i]=g(); if(!h[i]&&s[i]) add(i,i);}for(R i=1;i<=n;++i) for(R j=1,x;j<=n;++j) {x=g(); if(x&&s[j]) add(i,j);}for(R i=1;i<=n;++i) if(!s[i]||(s[i]&&!h[i])) ++tot;for(R i=1;i<=n;++i) if(!s[i]||(s[i]&&!h[i])) {memset(vis,0,sizeof(vis)); ans+=dfs(i);} ans==tot?printf("^_^\n"):printf("T_T\n");} }

---

2019.04.14

轉(zhuǎn)載于:https://www.cnblogs.com/Jackpei/p/10707186.html

總結(jié)

以上是生活随笔為你收集整理的BZOJ 1433 Luogu P2055 [ZJOI2009]假期的宿舍 匈牙利算法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。