世界真的很大 这道题在考试时做的时候是愣是觉得是一道水题，随随便便ac吧，这样，，，然后就wa了9个点，，，，原因实在太zz了就不分享了，但这道题是真的不难的，关乎于二分图匹配及基础的匈牙利算法。 description： input： output： 读完题大概就该往图论那边猜了，一个人只能睡一张床，人不能睡在别人身上，就是说一人一床匹配，床也不能坐在床身上，把床和人分开的话，就是一张二分图，在满足条件的情况下，跑一遍匈牙利算法，求出满足条件的最大匹配数，看是不是和住宿人数相等就行了。 首先是条件，即建边。人和床建双向边，一共有两种情况，即人是在校生还是来探访的，在校生如果回家就不管了，如果不回家，就可以睡自己的床，建一条边，来探访的对自己朋友的床建边，但不能对同为探访者建边，因为他没有床，代码：
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { scanf("%d",&x); if(whe[i]&&idf[i]) continue ; if(x&&idf[j]!=0) add(i,n+j),add(n+j,i); if(j==i&&idf[i]) add(i,n+j),add(n+j,i); }接下来在建好的图上跑一遍匈牙利算法就行了，这里浅谈一下。 匈牙利算法是用于求二分图的最大匹配数的，虽然说dinic几乎能做匈牙利的所有题，但是毕竟好写，只有一个dfs。 举个例子： 这是一张二分图。 从一号点开始，找到一个没有被匹配的点A，将1与A互相记为一个匹配，退出，继续从e 2开始，重复以上步骤，2就找到了B： 接下来从3开始，找到了A，但是A已经被匹配了，就从A开始找增广路，我管这个叫协调，看1能不能找到一个新的匹配来把A空出来给3，1发现自己还可以和B匹配，就去和B协调，看B能不能让B的匹配，2，找到一个新的匹配从而把B空出来和1匹配，从而把A空出来和3匹配。发现2还可以和C匹配，就完美了，记录新的匹配。 加入4，从4开始找到C，C去找2看2能不能空出来，2去找B，发现B已经被协调过了，没法再协调了，不然又会让3落单，这时4就无法找到自己的匹配了，记录，这张二分图的最大匹配数就是3（绿色线） dfs的代码如下：
int dfs(int u) { for(int i=head[u];i;i=ed[i].last) { int v=ed[i].v; if(book[v]==0) { book[v]=1; if(match[v]==0||dfs(match[v])) { match[u]=v; match[v]=u; return 1; } } } return 0; }这道题的完整代码：
#include<stdio.h> #include<cstring> using namespace std; struct edge { int v,last; }ed[100010]; int head[100010],book[100010],match[100010],idf[100010],whe[100010]; int num=0,n,tot=0,tt,x,cnt=0; void add(int u,int v) { num++; ed[num].v=v; ed[num].last=head[u]; head[u]=num; } int dfs(int u) { for(int i=head[u];i;i=ed[i].last) { int v=ed[i].v; if(book[v]==0) { book[v]=1; if(match[v]==0||dfs(match[v])) { match[u]=v; match[v]=u; return 1; } } } return 0; } int main() { scanf("%d",&tt); while(tt--) { num=0,tot=0; memset(head,0,sizeof(head)); memset(idf,0,sizeof(idf)); memset(whe,0,sizeof(whe)); memset(match,0,sizeof(match)); scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&idf[i]); for(int i=1;i<=n;i++) scanf("%d",&whe[i]); for(int i=1;i<=n;i++) if(idf[i]==1&&whe[i]==0) tot++; for(int i=1;i<=n;i++) if(idf[i]==0) tot++; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { scanf("%d",&x); if(whe[i]&&idf[i]) continue ; if(x&&idf[j]!=0) add(i,n+j),add(n+j,i); if(j==i&&idf[i]) add(i,n+j),add(n+j,i); } int ans=0; for(int i=1;i<=2*n;i++) { memset(book,0,sizeof(book)); if(!match[i]) if(dfs(i))ans++; } if(ans!=tot) printf("T_T\n"); else printf("^_^\n"); } }嗯，就是这样。
