判断是否满流,,,人数给了100000,一看普通建图肯定不行,卡了几天了,,
看了网上说把状态相同(选择星球相同)的人合并,用二进制,最多有2^10种状态,
#include<stdio.h> #include<string.h> #include<queue> #define N 100100 #define inf 0x3fffffff using namespace std; int dis[N],gap[10],num,head[N],start,end,ans; struct edge { int st,ed,next,flow; }E[N*10]; void addedge(int x,int y,int flow) { E[num].st=x;E[num].ed=y;E[num].flow=flow;E[num].next=head[x];head[x]=num++; E[num].st=y;E[num].ed=x;E[num].flow=0; E[num].next=head[y];head[y]=num++; } int dfs(int u,int minflow) { if(u==end)return minflow; int i,v,f,flow=0,min_dis=ans-1; for(i=head[u];i!=-1;i=E[i].next) { v=E[i].ed; if(E[i].flow>0) { if(dis[v]+1==dis[u]) { f=dfs(v,E[i].flow>minflow-flow?minflow-flow:E[i].flow); E[i].flow-=f; E[i^1].flow+=f; flow+=f; if(dis[start]>=ans)return flow; if(flow==minflow)break; } min_dis=min_dis>dis[v]?dis[v]:min_dis; } } if(flow==0) { if(--gap[dis[u]]==0) dis[start]=ans; dis[u]=min_dis+1; ++gap[dis[u]]; } return flow; } int isap() { memset(dis,0,sizeof(dis)); memset(gap,0,sizeof(gap)); int maxflow=0; gap[0]=ans; while(dis[start]<ans) maxflow+=dfs(start,inf); return maxflow; } int main() { int n,m,i,j,x,bit[11],cont[1025]; bit[0]=1; for(i=1;i<=10;i++) bit[i]=bit[i-1]*2; while(scanf("%d%d",&n,&m)!=EOF) { memset(head,-1,sizeof(head)); num=0; memset(cont,0,sizeof(cont)); for(i=1;i<=n;i++) { int temp=0;//所处的状态 for(j=0;j<m;j++) {scanf("%d",&x);temp+=x*bit[j];} cont[temp]++; } start=0;end=1024+m+1;ans=end+1; for(i=0;i<1024;i++) { if(cont[i]==0)continue; addedge(start,i+1,cont[i]); for(j=0;j<10;j++) if(i&bit[j] ) addedge(i+1,1024+j+1,inf); } for(i=1;i<=m;i++) { scanf("%d",&x); addedge(i+1024,end,x); } if(isap()==n)printf("YES\n"); else printf("NO\n"); } return 0; }