做发型的网站,下载百度安装,备份管理wordpress,湖州市建设局网站正题
链接#xff1a; https://www.luogu.org/record/show?rid7930976 大意
有n个人#xff0c;有的在学校有床有的没有#xff0c;有的在家有的没有。现在如果有人回家了那么他就会去看望他的朋友#xff0c;回家的就会空出自己的床位。每个人可以睡和自己是直接朋友关…正题
链接 https://www.luogu.org/record/show?rid7930976 大意
有n个人有的在学校有床有的没有有的在家有的没有。现在如果有人回家了那么他就会去看望他的朋友回家的就会空出自己的床位。每个人可以睡和自己是直接朋友关系或自己的床要求给本来有床的并且不在家的和来看望其的朋友分配床位。 解题思路
将人和床建立二分图我们假设每个在家的人都有床这样不用看望朋友的就可以睡自己床然后将除了没有床且不再家的人都作为左边点然后将在学校的床作为右边点进行最大匹配。 代码
#includecstdio
#includecstring
#includealgorithm
using namespace std;
struct line{int to,next,w;
}a[10010];
int n,m,x,y,d[110],tot,state[110],school[110],num;
int head,tail,ls[110],s,e,ans,t,home[110],nn,qn;
bool ok[110],lxx[110][110];
void addl(int x,int y,int w)
{a[tot].toy;a[tot].nextls[x];a[tot].ww;ls[x]tot;a[tot].tox;a[tot].nextls[y];a[tot].w0;ls[y]tot;
}
bool bfs()
{head0;tail1;memset(d,-1,sizeof(d));d[s]0;state[1]s;do{head;int xstate[head];for (int qls[x];q;qa[q].next){int ya[q].to;if (a[q].w0 d[y]-1){d[y]d[x]1;state[tail]y;if (ye) return true;}}}while (headtail);return false;
}
int dinic(int x,int flow)
{int rest0,k;if (xe) return flow;for (int qls[x];q;qa[q].next){int ya[q].to;if (a[q].w0 d[y]d[x]1){rest(kdinic(y,min(a[q].w,flow-rest)));a[q].w-k;a[q^1].wk;if (restflow) return flow;}}if (!rest) d[x]0;return rest;
}
int main()
{scanf(%d,t);for (int ti1;tit;ti){memset(ls,0,sizeof(ls));e105;s104;tot2;num0;scanf(%d,n);for (int i1;in;i){scanf(%d,school[i]);if(school[i]) addl(in,e,1);//床}for (int i1;in;i){scanf(%d,home[i]);if (!school[i]||(school[i]!home[i])) addl(s,i,1),num;//需要匹配的人}for (int i1;in;i){for (int j1;jn;j){scanf(%d,x);if (x||ij)addl(i,jn,1);//和自己或直接朋友的床匹配}}ans0;while (bfs()) ansdinic(s,2147483647);if (ansnum) printf(^_^\n);else printf(T_T\n);}
} 小技巧
其实有些时候可以将本来不需要的在其他地方分配掉可能可以降低难度
