| ||||||||||
| 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