uva 10746 - Crime Wave - The Sequel（最小费用流+精度）！！没提交对-求助

#include<cstdlib>#include<iostream>#include<cstdio>#include<cmath>#include<cstring>#include <algorithm>#include<queue>#include<set>#define LL long long#define inf 0x7fffffff#define E 1e-7#define M 100#define N 105using namespace std;int n,m;double cost[N][N],d[N];int cap[N][N];int p[N];bool inq[N];int s,t;int num;double getflow(int s,int t){  queue<int> q;  double c=0;  int f=0;  for(;;)    {      for(int i=1;i<=t;i++)      d[i]=inf;      memset(inq,0,sizeof(inq));      d[s]=0;      q.push(s);      while(!q.empty())        {          int u=q.front();          q.pop();          inq[u]=0;          for(int i=1; i<=num; i++)            if(cap[u][i]&&d[i]-d[u]-cost[u][i]>-E)              {                d[i]=d[u]+cost[u][i];                p[i]=u;                if(!inq[i])                  {                    q.push(i);                    inq[i]=1;                  }              }        }      int a=inf;      for(int i=t; i!=s; i=p[i])        {          a=min(a,cap[p[i]][i]);        }      for(int i=t; i!=s; i=p[i])        {          cap[p[i]][i]-=a;          cap[i][p[i]]+=a;        }      f+=a;      c+=d[t]*(double)a;      if(f==n)      break;    }  return c;}int main(){#ifndef ONLINE_JUDGE  freopen("ex.in","r",stdin);#endif  while(scanf("%d%d",&n,&m))    {      if(!n&&!m)        break;        memset(cap,0,sizeof(cap));        memset(cost,0,sizeof(cost));        for(int i=1;i<=n;i++)        for(int j=1;j<=m;j++)        {            scanf("%lf",&cost[i][j+n]);            cost[j+n][i]=-cost[i][j+n];            cap[i][j+n]=1;        }        for(int i=1;i<=n;i++)        cap[0][i]=1;        num=m+n+1;        for(int i=1;i<=m;i++)        cap[i+n][num]=1;        s=0;t=num;        double ans=getflow(s,t);        printf("%.2lf\n",ans/n);    }  return 0;}