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

• Re:求神牛指点迷津 为什么会WA...实在想不出来了 (2702) qzez_jz 2017-01-24 14:52:22