欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【费用流】hdu5988 Coding Contest

程序员文章站 2022-05-22 10:50:13
...

从源点向每个点连接容量为该点人数,费用为1的边,

把原图中的每条边拆成两条,一条容量为1,费用为1,另一条容量为ci-1,费用为1-pi

从每个点向汇点连接容量为该点面包数量,费用为1的边。

跑的费用流为按照乘积跑个最大费用流。

可以取个对数,乘法变成加法,

可以再取个负数,最大费用变成最小费用。

别忘了最后还原回来。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<cmath>
using namespace std;
#define E 2.71828182845904523536
#define EPS 0.00000001
#define MAXN 201
#define MAXM 25001
#define INF 2147483647
int S,T;
int en,u[MAXM],v[MAXM],first[MAXN],__next[MAXM],cap[MAXM];
double cost[MAXM];//__next Array
bool inq[MAXN];
double d[MAXN];/*spfa*/
int p[MAXN]/*spfa*/,a[MAXN]/*????*/;
queue<int>q;
void Init_MCMF(){memset(first,-1,sizeof(first));en=0;}
void AddEdge(const int &U,const int &V,const int &W,const double &C)
{
    u[en]=U; v[en]=V; cap[en]=W; cost[en]=C;
    __next[en]=first[U]; first[U]=en++;
    u[en]=V; v[en]=U; cap[en]=0; cost[en]=-C;
    __next[en]=first[V]; first[V]=en++;
}
bool Spfa(int &Flow,double &Cost)
{
    memset(d,0x7f,sizeof(d));
    memset(inq,0,sizeof(inq));
    d[S]=0; inq[S]=1; p[S]=0; a[S]=INF; q.push(S);
    while(!q.empty())
      {
          int U=q.front(); q.pop(); inq[U]=0;
          for(int i=first[U];i!=-1;i=__next[i])
            if(cap[i] && d[v[i]]-(d[U]+cost[i])>EPS)
              {
                d[v[i]]=d[U]+cost[i];
                p[v[i]]=i;
                a[v[i]]=min(a[U],cap[i]);
                if(!inq[v[i]]) {q.push(v[i]); inq[v[i]]=1;}
              }
      }
    if(d[T]-2000000000.0>EPS) return 0;
    Flow+=a[T]; Cost+=d[T]*(double)a[T]; int U=T;
    while(U!=S)
      {
          cap[p[U]]-=a[T]; cap[p[U]^1]+=a[T];
          U=u[p[U]];
      }
    return 1;
}
double Mincost()
{
    int Flow=0;
	double Cost=0;
    while(Spfa(Flow,Cost));
    return Cost;
}
int Zu,n,m;
int main(){
//	freopen("g.in","r",stdin);
	int x,y,z;
	double p;
	scanf("%d",&Zu);
	for(int zu=1;zu<=Zu;++zu){
		Init_MCMF();
		scanf("%d%d",&n,&m);
		S=n+1; T=n+2;
		for(int i=1;i<=n;++i){
			scanf("%d%d",&x,&y);
			AddEdge(S,i,x,0);
			AddEdge(i,T,y,0);
		}
		for(int i=1;i<=m;++i){
			scanf("%d%d%d%lf",&x,&y,&z,&p);
			if(z>0){
				AddEdge(x,y,1,0);
				AddEdge(x,y,z-1,-log(1.0-p));
			}
		}
		printf("%.2lf\n",1.0-pow(E,-Mincost()));
	}
	return 0;
}