| ||||||||||
Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Re:求神牛指点迷津 为什么会WA...实在想不出来了In Reply To:求神牛指点迷津 为什么会WA...实在想不出来了 Posted by:gzx512373456 at 2012-11-07 22:38:28 > #include"stdio.h" > #include"string.h" > #include"math.h" > #include"queue" > #include"iostream" > #define inf 2000000000 > #define minn(x,y) x<y? x:y > #define maxN 2005 > #define maxM 2000105 > using namespace std; > struct pp > { > int u,v,flow,next; > }a[maxM<<1]; > int n,m,c,st,end,N; > int d[maxN],num[maxN],head[maxN]; > int b[55][12],w[60000][3]; > void addedge(int u,int v,int f) > { > a[c].u=u; > a[c].v=v; > a[c].flow=f; > a[c].next=head[u]; > head[u]=c++; > a[c].u=v; > a[c].v=u; > a[c].flow=0; > a[c].next=head[v]; > head[v]=c++; > } > int dfs(int u,int flow) > { > int i,v,pos=N,temp=flow; > if(u==N) return flow; > for(i=head[u];i!=-1;i=a[i].next) > { > v=a[i].v;//printf("%d\n",i); > if(d[u]==d[v]+1 && a[i].flow) > { > int f=dfs(v,minn(temp,a[i].flow)); > temp-=f; > a[i].flow-=f; > a[i^1].flow+=f; > if(!temp || d[st]>=N) return flow-temp; > } > if(a[i].flow && d[v]<pos) pos=d[u]; > } > if(temp==flow) > { > num[d[u]]--; > if(!num[d[u]]) d[st]=N; > else > { > d[u]=pos+1; > num[d[u]]++; > } > } > return flow-temp; > } > int SAP() > { > int ans=0,i; > for(i=0;i<=N;i++) d[i]=num[i]=0; > while(d[st]<N) > ans+=dfs(st,inf); > return ans; > } > int main() > { > int i,j,k,u,v,f,ca,flag; > char s1[100],s2[100]; > while(scanf("%d%d",&m,&n)!=EOF) > { > N=n*2+1; > st=0;end=N; > c=0; > k=m*2; > for(i=0;i<=N;i++) head[i]=-1; > for(j=1;j<=n;j++) > { > for(i=0;i<=k;i++) > scanf("%d",&b[j][i]); > flag=1; > for(i=1;i<=m;i++) if(b[j][i]==1) flag=0; > if(flag) addedge(0,j,inf); > flag=1; > for(i=m+1;i<=k;i++) if(b[j][i]==0) flag=0; > if(flag) addedge(j+n,N,inf); > } > for(i=1;i<=n;i++) > { > addedge(i,i+n,b[i][0]); > for(j=1;j<=n;j++) > { > if(i==j) continue; > flag=1; > for(u=1;u<=m;u++) > if(b[i][u+m]+b[j][u]==1) flag=0;; > if(flag) addedge(i+n,j,inf); > } > } > //for(i=0;i<c;i+=2) printf("%d %d %d %d\n",a[i].u,a[i].v,a[i].flow,a[i].next); > int ans=SAP(); > k=0; > for(i=1+n;i<N;i++) > for(j=head[i];j!=-1;j=a[j].next) > { > if(a[j].v==N||a[j].v==i-n||a[j].flow==inf) continue; > w[++k][0]=i-n; > w[k][1]=a[j].v; > w[k][2]=inf-a[j].flow; > } > printf("%d %d\n",ans,k); > for(i=1;i<=k;i++) > { > printf("%d %d %d\n",w[i][0],w[i][1],w[i][2]); > } > } > return 0; > } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator