首页 > 代码库 > hdu 3605 /状态合并最大流
hdu 3605 /状态合并最大流
题意:N个人去m个星球,给出n个人可以去哪些星球的01矩阵。求是否能满足所有人都去。(n到10万,m<=10)
一看,起先一瞬间就建图,准备秒了,人向星球连边,直接最大流判断是否为n,提交超时。。。是啊,10W*10=100W条边,铁定超时。。
后来经牛提示:注意,m<10! 人的可以去星球,一共最多有10个,那只有 2^10次种情况,就是说x部与Y部连线情况很多点是一样的(所给的01矩阵,最多10W行,10列,必然有很多行是一样的)。所以X部只留1024个点,这些点中,点i含j个人的状态,者源点向其连边j,该点向可以去的连边,流量inf.
#include<iostream> #include<queue> #include<cstdio> #include<cstring> #include<string> using namespace std; const int inf=0x3f3f3f3f; const int maxv=2000,maxe=200000; int nume=0;int head[maxv];int e[maxe][3]; void inline adde(int i,int j,int c) { e[nume][0]=j;e[nume][1]=head[i];head[i]=nume; e[nume++][2]=c; e[nume][0]=i;e[nume][1]=head[j];head[j]=nume; e[nume++][2]=0; } int ss,tt,n,m; int vis[maxv];int lev[maxv]; bool bfs() { for(int i=0;i<tt+1;i++) vis[i]=lev[i]=0; queue<int>q; q.push(ss); vis[ss]=1; while(!q.empty()) { int cur=q.front(); q.pop(); for(int i=head[cur];i!=-1;i=e[i][1]) { int v=e[i][0]; if(!vis[v]&&e[i][2]>0) { lev[v]=lev[cur]+1; vis[v]=1; q.push(v); } } } return vis[tt]; } int dfs(int u,int minf) { if(u==tt||minf==0)return minf; int sumf=0,f; for(int i=head[u];i!=-1&&minf;i=e[i][1]) { int v=e[i][0]; if(lev[v]==lev[u]+1&&e[i][2]>0) { f=dfs(v,minf<e[i][2]?minf:e[i][2]); e[i][2]-=f;e[i^1][2]+=f; sumf+=f;minf-=f; } } if(!sumf) lev[u]=-1; return sumf; } int dinic() { int sum=0; while(bfs())sum+=dfs(ss,inf); return sum; } int contain[15];int mark[1025]; void read_build() { int tx; for(int i=0;i<n;i++) { int tkind=0; for(int j=0;j<m;j++) { scanf("%d",&tx); if(tx==1) tkind=tkind|(tx<<(m-j-1)); //二进制压缩状态,或者开10维数组判重也方便。 } mark[tkind]++; } for(int i=0;i<=1024;i++) { if(mark[i]!=0) adde(ss,i,mark[i]); } for(int i=0;i<=1024;i++) { if(mark[i]!=0) { int ti=i;int cwei=0; while(ti!=0) { if(ti%2==1) adde(i,m-1-cwei+1024,inf); ti=ti/2; cwei++; } } } for(int i=0;i<m;i++) //每个星球人数 { scanf("%d",&contain[i]); } for(int i=0;i<m;i++) //星球 { adde(i+1024,tt,contain[i]); } /* for(int i=0;i<=n*m+1;i++) for(int j=head[i];j!=-1;j=e[j][1]) { printf("%d->%d:%d\n",i,e[j][0],e[j][2]); }*/ } void init() { nume=0; ss=1050;tt=ss+1; for(int i=0;i<=tt;i++) { head[i]=-1; contain[i]=mark[i]=0; } } int main() { while(~scanf("%d%d",&n,&m)) { init(); read_build(); int ans=dinic(); if(ans==n)printf("YES\n"); else printf("NO\n"); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。