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 |
求错误!!!!#include<iostream> #include<queue> #include<cmath> using namespace std; #define MAXN 200 queue<int> qu; double map[MAXN][MAXN]; int d[MAXN]; int end; double minm(double a,double b){return a<b?a:b;} bool bfs(int s) { memset(d,-1,sizeof(d)); while(!qu.empty())qu.pop(); qu.push(s); int i; d[s]=0; while(!qu.empty()) { int u=qu.front(); qu.pop(); for(i=0;i<=end;i++) { if(d[i]==-1&&map[u][i]>0) { d[i]=d[u]+1; qu.push(i); } } } if(d[end]<0)return 0; return 1; } double dinic(int t,double sum) { if(t==end)return sum; int i; double s=sum; for(i=0;i<=end;i++) { if(d[i]==d[t]+1&&map[t][i]>0) { double a=dinic(i,minm(sum,map[t][i])); map[t][i]-=a; map[i][t]+=a; sum-=a; } } return s-sum; } int main() { int tt,n,m,l,i,x,y; double c; scanf("%d",&tt); while(tt--) { memset(map,0,sizeof(map)); scanf("%d%d%d",&n,&m,&l); int s=0,t=n+m+1; for(i=1;i<=n;i++) { scanf("%lf",&c); map[s][i]=log(c); } for(i=1;i<=m;i++) { scanf("%lf",&c); map[i+n][t]=log(c); } for(i=1;i<=l;i++) { scanf("%d%d",&x,&y); map[x][y+n]=1000000; } end=t; double res=0; while(bfs(0))res+=dinic(0,100000000); printf("%.4lf\n",exp(res)); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator