hdu 3605 /状态合并最大流-白红宇

hdu 3605 /状态合并最大流

阅读量：7036 次

发布时间：2019-06-28

本文共 1469 字，大约阅读时间需要 4 分钟。

题意：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
    
     #include
     
      #include
      
       #include
       
        #include
        
         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

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

%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;}

转载于:https://www.cnblogs.com/yezekun/p/3925769.html

你可能感兴趣的文章