Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
 User ID: Password:
Register

## Re:求神牛指点迷津 为什么会WA...实在想不出来了

Posted by qzez_jz at 2017-01-24 14:52:22 on Problem 3436
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:
User ID:
Password:
Title:

Content:

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator