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

求错误!!!!

Posted by ShenZhiBM at 2010-09-18 11:41:30 on Problem 3308
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


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